第1章排序-歸并與基數(shù)排序ppt課件

1、數(shù)據(jù)構造講義 - 歸并與基數(shù)排序SunLl歸并將兩個或兩個以上的有序表組合成一個新的有序表，叫l(wèi)2-路歸并排序l設初始序列含有n個記錄，那么可看成n個有序的子序列，每個子序列長度為1。l兩兩合并，得到n/2個長度為2或1的有序子序列。l再兩兩合并，如此反復，直至得到一個長度為n的有序序列為止。順序比較兩者的相應元素，小者移入另一表中，反復順序比較兩者的相應元素，小者移入另一表中，反復如此，直至其中任一表都移入另一表為止。如此，直至其中任一表都移入另一表為止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 4491365

2、9776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7130 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2

3、 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B

4、表的元素表的元素都已移入都已移入 C 表，表，只需將只需將 A 表的剩表的剩余部分移入余部分移入 C 表表即可。即可。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B 表的元素表的元素都已移入都已移入 C 表，表，只需將只需將 A 表的剩表的剩余部分移入余部分移入 C 表表即可。即可。97初始關鍵字： 49 38 65 97 76 13 27一趟歸并后： 38 49 65 97 13 76 27二趟歸并后： 38 49 65 97 13 27 76三趟歸并后： 13 27 38 49 65 76 97l時間復雜度：lT(

5、n)=O(nlogn)l空間復雜度：lS(n)=O(n)l它是一個穩(wěn)定的排序方法。l多關鍵字排序例 對52張撲克牌按以下次序排序：23A23A23A23A兩個關鍵字：花樣 面值23A并且“花樣位置高于“面值l最高位優(yōu)先法最高位優(yōu)先法MSD)：先對最高位關鍵字：先對最高位關鍵字k1如花樣排序，將序列分成假設干子序列，如花樣排序，將序列分成假設干子序列，每個子序列有一樣的每個子序列有一樣的k1值；然后讓每個子序列值；然后讓每個子序列對次關鍵字對次關鍵字k2如面值排序，又分成假設干如面值排序，又分成假設干更小的子序列；依次反復，直至就每個子序列更小的子序列；依次反復，直至就每個子序列對最低位關鍵字對

6、最低位關鍵字kd排序；最后將一切子序列依排序；最后將一切子序列依次銜接在一同成為一個有序序列。次銜接在一同成為一個有序序列。l最低位優(yōu)先法最低位優(yōu)先法(LSD)：從最低位關鍵字：從最低位關鍵字kd起進起進展排序，然后再對高一位的關鍵字排序，展排序，然后再對高一位的關鍵字排序，依次反復，直至對最高位關鍵字依次反復，直至對最高位關鍵字k1排序后，便排序后，便成為一個有序序列。成為一個有序序列。l按按MSD排序，必需將序列逐層分割排序，必需將序列逐層分割成假設干子序列，然后對各子序列成假設干子序列，然后對各子序列分別排序。分別排序。l按按LSD排序，不用分成子序列，對排序，不用分成子序列，對每個關鍵

7、字都是整個序列參與排序；每個關鍵字都是整個序列參與排序；并且可不經(jīng)過關鍵字比較，而經(jīng)過并且可不經(jīng)過關鍵字比較，而經(jīng)過假設干次分配與搜集實現(xiàn)排序。假設干次分配與搜集實現(xiàn)排序。l基數(shù)排序：借助“分配和“搜集對單邏輯關鍵字進展排序的一種方法。l鏈式基數(shù)排序：用鏈表作存儲構造的基數(shù)排序。例初始形狀：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟搜集：505008109930063

8、269278083184589二趟搜集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟搜集：008063083109184269278505589930三趟搜集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟搜集：l設置10個隊列，fi和ei分別為第i個隊列的頭指針和

9、尾指針。l第一趟分配對最低位關鍵字個位進展，改動記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關鍵字的個位一樣。l第一趟搜集是改動一切非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表。l反復上述兩步，進展第二趟、第三趟分配和搜集，分別對十位、百位進展，最后得到一個有序序列。l時間復雜度：l分配：T(n)=O(n)l搜集：T(n)=O(rd)、lT(n)=O(d(n+rd)l其中：n記錄數(shù)， d關鍵字數(shù)， rd關鍵字取值范圍(如十進制為10) 。l空間復雜度：lS(n)=2rd個隊列指針+n個指針域空間。 平均時間平均時間 最差最差 最正

10、確最正確 輔助空間輔助空間 穩(wěn)定穩(wěn)定性性直接插入直接插入 O(n2) O(n2) O(n) O(1) O(n2) O(n2) O(n) O(1) 穩(wěn)定穩(wěn)定起泡排序起泡排序 O(n2) O(n2) O(n) O(1) O(n2) O(n2) O(n) O(1) 穩(wěn)定穩(wěn)定直接選擇直接選擇 O(n2) O(n2) O(n2) O(1) O(n2) O(n2) O(n2) O(1) 不穩(wěn)定不穩(wěn)定希爾排序希爾排序 O(n1.5) O(1) O(n1.5) O(1) 不穩(wěn)定不穩(wěn)定快速排序快速排序 O(nlog2n) O(n2) O(nlog2n) O(n2) 同平均同平均 O(log2n) O(log2n) 不穩(wěn)定不穩(wěn)定堆排序堆排序 O(nlog2n) O(nlog2n) 同平均同平均 同平均同平均 O(1) O(1) 不穩(wěn)定不穩(wěn)定歸并排序歸并排序 O(nl