【正文】 序表的長度均為 h， 執(zhí)行一次歸并，完成后 i加 2h， 準(zhǔn)備進(jìn)行下一次歸并； 算法描述： while (i≤n2h+1) { Merge (r, r1, i, i+h1, i+2*h1)。 i+=2*h。 } 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 歸并排序 關(guān)鍵問題⑵： 怎樣完成一趟歸并？ 設(shè)參數(shù) i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況： ②若 i＜ nh+1， 則表示仍有兩個(gè)相鄰有序表，一個(gè)長度為 h， 另一個(gè)長度小于 h， 則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。 20 60 5 31 44 55 65 i h i=4 n2h+1=4 nh+1=6 n2h+1 nh+1 h 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 歸并排序 關(guān)鍵問題⑵： 怎樣完成一趟歸并？ 設(shè)參數(shù) i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況： ②若 i＜ nh+1， 則表示仍有兩個(gè)相鄰有序表，一個(gè)長度為 h， 另一個(gè)長度小于 h， 則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。 算法描述： if (i＜ nh+1) Merge (r, r1, i, i+h1, n)。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 歸并排序 關(guān)鍵問題⑵： 怎樣完成一趟歸并？ 設(shè)參數(shù) i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況： ③ 若 i≥ nh+1， 則表明只剩下一個(gè)有序表 ， 直接將該有序表送到 r1的相應(yīng)位置 ， 完成后退出一趟歸并 。 i i=9 nh+1=8 nh+1 h 20 60 5 31 44 55 65 15 28 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 歸并排序 關(guān)鍵問題⑵： 怎樣完成一趟歸并？ 設(shè)參數(shù) i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況： ③ 若 i≥ nh+1， 則表明只剩下一個(gè)有序表 ， 直接將該有序表送到 r1的相應(yīng)位置 ， 完成后退出一趟歸并 。 算法描述： if (i=nh+1) for (k=i。 k=n。 k++) r1[k]=r[k]。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) void MergePass (int r[ ], int r1[ ], int n, int h) { i=1。 while (i≤ n2h+1) //情況 1 { Merge (r, r1, i, i+h1, i+2*h1)。 i+=2*h。 } if (i＜ nh+1) Merge (r, r1, i, i+h1, n)。 //情況 2 else for (k=i。 k=n。 k++) //情況 3 r1[k]=r[k]。 } 一趟歸并排序算法 歸并排序 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 解決方法： 開始時(shí)，有序序列的長度 h=1， 結(jié)束時(shí)，有序序列的長度 h=n， 用有序序列的長度來控制排序的結(jié)束。 歸并排序 關(guān)鍵問題⑶： 如何控制二路歸并的結(jié)束？ 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 算法描述： void MergeSort (int r[ ], int r1[ ], int n ) { h=1。 while (hn) { MergePass (r, r1, n, h)。 h=2*h。 MergePass (r1, r, n, h)。 h=2*h。 } } 歸并排序 關(guān)鍵問題⑶： 如何控制二路歸并的結(jié)束？ 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 二路歸并排序算法的性能分析 歸并排序 時(shí)間性能： 一趟歸并操作是將 r[1]~r[n]中相鄰的長度為 h的有序序列進(jìn)行兩兩歸并 ， 并把結(jié)果存放到 r1[1]~r1[n]中 ，這需要 O(n)時(shí)間 。 整個(gè)歸并排序需要進(jìn)行 趟 ，因此 ， 總的時(shí)間代價(jià)是 O(nlog2n)。 這是歸并排序算法的 最好 、 最壞 、 平均 的時(shí)間性能 。 空間性能： 算法在執(zhí)行時(shí) ， 需要占用與原始記錄序列同樣數(shù)量的存儲空間 ， 因此空間復(fù)雜度為 O(n)。 ? ? n 2 log第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 各種排序方法的比較 對排序算法應(yīng)該從以下幾個(gè)方面綜合考慮： ⑴ 時(shí)間復(fù)雜性； ⑵ 空間復(fù)雜性； ⑶ 穩(wěn)定性； ⑷ 算法簡單性； ⑸ 待排序記錄個(gè)數(shù) n的大?。? ⑹ 記錄本身信息量的大??； ⑺ 關(guān)鍵碼的分布情況 。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 時(shí)間復(fù)雜度比較 各種排序方法的比較 排序方法 平均情況 最好情況 最壞情況 直接插入排序 O(n2) O(n) O(n2) 希爾排序 O(nlog2n) O() O(n2) 起泡排序 O(n2) O (n) O(n2) 快速排序 O(nlog2n) O(nlog2n) O(n2) 簡單選擇排序 O(n2) O(n2) O(n2) 堆排序 O(nlog2n) O(nlog2n) O (nlog2n) 歸并排序 O(nlog2n) O(nlog2n) O(nlog2n) 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 空間復(fù)雜度比較 各種排序方法的比較 排序方法 輔助空間 直 接 插 入 排 序 O(1) 希 爾 排 序 O(1) 起 泡 排 序 O(1) 快 速 排 序 O(log2n) ~O(n) 簡 單 選 擇 排 序 O(1) 堆排序 O(1) 歸 并 排 序 O(n) 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 穩(wěn)定性比較 所有排序方法可分為兩類 ， （ 1） 一類是穩(wěn)定的 ， 包括直接插入排序 、 起泡排序 、直接選擇排序和歸并排序； （ 2） 另一類是不穩(wěn)定的 ， 包括希爾排序 、 快速排序和堆排序 。 各種排序方法的比較 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 算法簡單性比較 從算法簡單性看 ， （ 1） 一類是簡單算法 ， 包括直接插入排序 、 直接選擇排序和起泡排序 ， （ 2） 另一類是改進(jìn)后的算法 ， 包括希爾排序 、 堆排序 、 快速排序和歸并排序 ， 這些算法都很復(fù)雜 。 各種排序方法的比較 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 待排序的記錄個(gè)數(shù)比較 從待排序的記錄個(gè)數(shù) n的大小看 ， n越小 ， 采用簡單排序方法越合適 ， n越大 ， 采用改進(jìn)的排序方法越合適 。 因?yàn)?n越小 ， O(n2)同 O(nlog2n)的差距越小 ，并且輸入和調(diào)試簡單算法比輸入和調(diào)試改進(jìn)算法要少用許多時(shí)間 。 各種排序方法的比較 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 記錄本身信息量比較 記錄本身信息量越大，移動記錄所花費(fèi)的時(shí)間就越多，所以對記錄的移動次數(shù)較多的算法不利。 排序方法 最好情況 最壞情況 平均情況 直接插入排序 O(n) O(n2) O(n2) 起泡排序 0 O(n2) O(n2) 直接選擇排序 0 O(n) O(n) 各種排序方法的比較 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 關(guān)鍵碼的分布情況比較 當(dāng)待排序記錄按關(guān)鍵碼有序時(shí)，插入排序和起泡排序能達(dá)到 O(n)的時(shí)間復(fù)雜度；對于快速排序而言，這是最壞的情況，此時(shí)的時(shí)間性能蛻化為 O(n2)；選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。 各種排序方法的比較