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

1、數(shù)據(jù)構(gòu)造講義 - 歸并與基數(shù)排序SunLl歸并將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，叫l(wèi)2-路歸并排序l設(shè)初始序列含有n個(gè)記錄，那么可看成n個(gè)有序的子序列，每個(gè)子序列長度為1。l兩兩合并，得到n/2個(gè)長度為2或1的有序子序列。l再兩兩合并，如此反復(fù)，直至得到一個(gè)長度為n的有序序列為止。順序比較兩者的相應(yīng)元素，小者移入另一表中，反復(fù)順序比較兩者的相應(yīng)元素，小者移入另一表中，反復(fù)如此，直至其中任一表都移入另一表為止。如此，直至其中任一表都移入另一表為止。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初始關(guān)鍵字： 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時(shí)間復(fù)雜度：lT(

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

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

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

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

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

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