知識點歸并排序和基數(shù)排序ppt課件

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)10.5 歸歸 并并 排排 序知識點三）序知識點三）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 歸并的含義是將兩個或兩個以上的有序表組合成一個新的有序表。 歸并排序可分為兩路歸并排序,或多路歸并排序，既可用于內(nèi)排序，也可用于外排序。這里僅對內(nèi)排序的兩路歸并方法進(jìn)行討論。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)兩路歸并排序算法思路：兩路歸并排序算法思路：假設(shè)初始序列含有個記錄，首先把個記假設(shè)初始序列含有個記錄，首先把個記錄看成個長度為的有序序列，進(jìn)行兩兩錄看成個長度為的有序序列，進(jìn)行兩兩歸并，得到歸并，得到 個長度為的關(guān)鍵字有序個長度為的關(guān)鍵字有序序列，再兩兩歸并直到所有記錄歸并成一個序列，再兩兩歸并直到所有記錄歸并成一個長度為

2、的有序序列為止。長度為的有序序列為止。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有有 序序 序序 列列 Ri.n有序子序列有序子序列 Ri.m有序子序列有序子序列 Rm+1.n這個操作對順序表而言，是輕而易舉的。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例：已知關(guān)鍵字序列：例：已知關(guān)鍵字序列： 46,55,13,4246,55,13,42 歸并排序過程如下：歸并排序過程如下： 46 5513 42數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序

3、的記錄序列將有序的記錄序列 SRi.m 和和 SRm+1.n / 歸并為有序的記錄序列歸并為有序的記錄序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 將將SR中記錄由小到大地并入中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)if (i=m) TRk.n = SRi.m; / 將剩余的將剩余的 SRi.m 復(fù)制到復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的將剩余的 SRj.n 復(fù)制到復(fù)制到 TR數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)歸并

4、排序的算法歸并排序的算法如果記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應(yīng)該先分別對這兩部分進(jìn)行 2-路歸并排序。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)void Msort ( RcdT

5、ype SR, RcdType &TR1, int s, int t ) / 將將SRs.t 歸并排序為歸并排序為 TR1s.t if (s= =t) TR1s=SRs; else / Msort 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.t數(shù)據(jù)

6、結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)void MergeSort (SqList &L) / 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對 n 個記錄進(jìn)行歸并排序的時間復(fù)雜度為(nlogn)。即： 每一趟歸并的時間復(fù)雜度為 O(n)， 總共需進(jìn)行 log2n 趟。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)10.6 基基 數(shù)數(shù) 排排 序序數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基數(shù)排序是一種借助“多關(guān)鍵字排序的思想來實現(xiàn)“單關(guān)鍵字排序的內(nèi)部排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序 n 個記錄的序列個記錄的序

7、列 R1, R2, ，Rn對關(guān)鍵字對關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是指：有序是指： 其中其中: K0 : K0 被稱為被稱為 “ “最主位關(guān)鍵字最主位關(guān)鍵字Kd-1 被稱為被稱為 “最次位關(guān)鍵字最次位關(guān)鍵字 對于序列中任意兩個記錄 Ri 和 Rj(1ijn) 都滿足下列(詞典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 實現(xiàn)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)先最低位優(yōu)先LSDLSD法法最高位優(yōu)先最高位優(yōu)先MSDMSD法法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 最高位優(yōu)先最高位優(yōu)先MSDMSD法法: :先對先對K0K0進(jìn)行排序，并按進(jìn)行排序

8、，并按 K0 K0 的不同值將記錄序列分成若干子序列之的不同值將記錄序列分成若干子序列之后，分別對后，分別對 K1 K1 進(jìn)行排序，進(jìn)行排序，.， 依次類推，直至最后對最次位依次類推，直至最后對最次位關(guān)鍵字排序完成為止。關(guān)鍵字排序完成為止。最低位優(yōu)先最低位優(yōu)先LSDLSD法法: :先對先對 Kd-1 Kd-1 進(jìn)行排序，然后對進(jìn)行排序，然后對 Kd-2 Kd-2 進(jìn)行排序，依次類推，直至進(jìn)行排序，依次類推，直至對最主位關(guān)鍵字對最主位關(guān)鍵字 K0 K0 排序完成為止。排序完成為止。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例如例如: :學(xué)生記錄含三個關(guān)鍵字學(xué)生記錄含三個關(guān)鍵字: :系別、班號和班內(nèi)的序列號，其中以系別為最

9、主位關(guān)系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。鍵字。 無序序列對對K2排序排序?qū)1排序排序?qū)0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下的排序過程如下:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二、鏈?zhǔn)交鶖?shù)排序二、鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時，可以采用“分配-搜集的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。對于數(shù)字型或字

10、符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-搜集的辦法進(jìn)行排序，稱作基數(shù)排序法。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例如：對下列這組關(guān)鍵字例如：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “搜集” 在一起； 然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“搜集” 在一起；最后按其“百位數(shù)重復(fù)一遍上述操作。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機(jī)

11、上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采在計算機(jī)上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為：用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： 待排序記錄以指針相鏈，構(gòu)成一個鏈表；待排序記錄以指針相鏈，構(gòu)成一個鏈表；“分配分配” ” 時，按當(dāng)前時，按當(dāng)前“關(guān)鍵字位所取值，將記錄分配到不同關(guān)鍵字位所取值，將記錄分配到不同的的 “ “鏈隊列鏈隊列” ” 中，每個隊列中記錄的中，每個隊列中記錄的 “ “關(guān)鍵字位關(guān)鍵字位” ” 一樣；一樣；“搜集時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈搜集時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表成

12、一個鏈表; ;對每個關(guān)鍵字位均重復(fù)對每個關(guān)鍵字位均重復(fù) 2) 2) 和和 3) 3) 兩步。兩步。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例如：p369367167239237230進(jìn)行第一次分配進(jìn)行第一次分配進(jìn)行第一次收集進(jìn)行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167 237367167237368239369 239 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)進(jìn)行第二次分配進(jìn)行第二次分配p230237239p230367167237368239f3 r3f6 r6230 237239 367 167 368367167368進(jìn)行第二次收集數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 進(jìn)行第三次收集之后便得到記錄的有序序列f1 r1

13、p230237239367167368進(jìn)行第三次分配進(jìn)行第三次分配f2 r2f3 r3 167230 237 239367 368p167230237239367368數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 基數(shù)排序的時間復(fù)雜度為O(d(n+rd)其中：分配為O(n) （n個數(shù)） 收集為O(rd)(rd為“基”) d為“分配-搜集的趟數(shù)d位）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)10.7 各種排序方法的綜合比較各種排序方法的綜合比較數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)排序方法排序方法平均情況平均情況最好情況最好情況最壞情況最壞情況直 接 插 入 排 序直 接 插 入 排 序O(n2)O(n)O(n2)希爾排序希爾排序O(nlog2n)O(n1.3)O(n2

14、)冒泡排序冒泡排序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ù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)關(guān)鍵碼的分布情況比較關(guān)鍵碼的分布情況比較當(dāng)待排序記錄按關(guān)鍵碼有序時，插入排序和冒泡排序能達(dá)當(dāng)待排序記錄按關(guān)鍵碼有序時，插入排序和冒泡排序能達(dá)到到O(n)O(n)的時間復(fù)雜度；對于快速

15、排序而言，這是最壞的情的時間復(fù)雜度；對于快速排序而言，這是最壞的情況，此時的時間性能蛻化為況，此時的時間性能蛻化為O(n2)O(n2)；選擇排序、堆排序和；選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)一、時間性能一、時間性能1. 平均的時間性能平均的時間性能基數(shù)排序基數(shù)排序時間復(fù)雜度為時間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時間復(fù)雜度為時間復(fù)雜度為 O(n2)O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡單選擇排序簡單選擇排序時間復(fù)雜度為時間

16、復(fù)雜度為 O(n):數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時當(dāng)待排記錄序列按關(guān)鍵字順序有序時3. 簡單選擇排序、堆排序和歸并排序的時間性簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。能不隨記錄序列中關(guān)鍵字的分布而改變。 直接插入排序和起泡排序能達(dá)到O(n)的時間復(fù)雜度， 快速排序的時間性能蛻化為O(n2) 。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二、空間性能二、空間性能指的是排序過程中所需的輔助空間大小1. 所有的簡單排序方法所有的簡單排序方法(包括：直接插入、包括：直接插入、起泡和簡單選擇起泡和簡單選擇) 和堆排序的空間復(fù)雜度和堆排序的空間復(fù)雜度為為O(1)；2. 快速排

17、序為快速排序為O(logn)，為遞歸程序執(zhí)行，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；過程中，棧所需的輔助空間；數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)3. 歸并排序所需輔助空間最多，其空間歸并排序所需輔助空間最多，其空間復(fù)雜度為復(fù)雜度為 O(n);4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊列首尾指針，鏈?zhǔn)交鶖?shù)排序需附設(shè)隊列首尾指針，則空間復(fù)雜度為則空間復(fù)雜度為 O(rd)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)三、排序方法的穩(wěn)定性能三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 2. 當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行LSD方方法排法排序時，必

18、須采用穩(wěn)定的排序方法。序時，必須采用穩(wěn)定的排序方法。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是穩(wěn)定的;若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是不穩(wěn)定的。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3. 對于不穩(wěn)定的排序方法，只要能舉出對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。一個實例說明即可。 4. 直接選擇排序、快速排序、堆排序和希爾直接選擇排序、快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。排序是不穩(wěn)定的排序方法。例如例如 : 對對 4, 3, 4, 2 進(jìn)行快速排序，進(jìn)行快速排序， 得到得到 2, 3, 4, 4 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)討論：直接選擇排序是否穩(wěn)定？討論：直接選擇排序是否穩(wěn)定？例如例如 : 對序列對序列5 ，8， 5， 2， 9 進(jìn)行直接選進(jìn)行直接選擇排序得到擇排序得到 2 ，8， 5， 5 ， 9不穩(wěn)定不穩(wěn)定數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)排序排序 插入排序直插排序、折半排序、希爾排序）插入排序直插排序、折半排序、希爾排序） 交換排序冒泡排序、快速排序）交換排序冒泡排序、