數(shù)據(jù)結(jié)構(gòu)第11章排序

1、1排序的基本概念插入排序交換排序選擇排序歸并排序基數(shù)排序各種方法的比較第11章 排序什么是排序(Sorting)？簡單地說，排序就是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律排列起來（遞增或遞減）。排序是計算機(jī)中經(jīng)常遇到的操作。排序的概念數(shù)據(jù)表(Data List) 待排序的記錄的有限集合。 關(guān)鍵字(Key) 作為排序依據(jù)的各記錄中的屬性域。數(shù)據(jù)表： R1 ，R2 ， R3 ， Rn 關(guān)鍵字序列： k1 ， k2 ， k3 ， kn 排序(Sorting)使一組任意排列的數(shù)據(jù)表變成一組按關(guān)鍵字線性有序（遞增或遞減）的數(shù)據(jù)表。數(shù)據(jù)表： R1 ，R2 ， R3 ， Rn 關(guān)鍵字序列： k1 ， k2 ， k

2、3 ， kn 其中：遞增次序 ： k1 k2 k3 kn 或 遞減次序 ： k1 k2 k3 kn 排序前：排序后：排序的概念例：5，2，8，5* 排序后為：2，5，5*，8 是穩(wěn)定排序 排序后為：2，5*，5，8 是不穩(wěn)定排序排序的分類排序算法的穩(wěn)定性 關(guān)鍵字相同的記錄在排序過程中保持前后次序不變的排序稱穩(wěn)定排序，否則稱不穩(wěn)定排序。內(nèi)排序與外排序 *內(nèi)排序是指在排序過程中記錄全部存放在內(nèi)存的排序； *外排序是指在排序過程中數(shù)據(jù)量太大，不能同時存放在內(nèi)存，在排序過程中不斷進(jìn)行內(nèi)、外存之間數(shù)據(jù)交換的排序。5數(shù)據(jù)表的存儲方式 *順序存儲方式通過移動記錄的相對存儲位置實(shí)現(xiàn)排序。排序的分類*鏈?zhǔn)酱鎯Ψ?/p>

3、式通過各結(jié)點(diǎn)修改指針實(shí)現(xiàn)排序30 11 44 77 22 8811 22 30 44 77 88排序前排序后h30 11 44 77 22h30 11 44 77 22 排序前排序后6排序的時間效率: 通常用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。排序的空間效率：在算法執(zhí)行時所需的附加存儲空間多少來衡量。排序算法分析 為簡單起見，數(shù)據(jù)的存儲結(jié)構(gòu)采用順序方式存儲，同時假定關(guān)鍵字是整數(shù)。記錄存儲數(shù)據(jù)類型如下：typedef int KeyTypetypedef struct KeyType key; /*存放關(guān)鍵字*/ InfoType data;/*存放其他數(shù)據(jù)項(xiàng)*/ RecType; /

4、*記錄數(shù)據(jù)類型*/RecRype Rn+1; /* R0Rn存放n個記錄*/ 按關(guān)鍵字遞增次序排序7插入排序(Insert Sorting) 基本原理 : 將一個待排序的記錄, 按其關(guān)鍵字大小, 插入到前面已經(jīng)排好序的一組記錄的適當(dāng)位置上, 直到記錄全部插入為止。 排序方法直接插入排序 (Insert Sort) 希爾排序 (Shell Sort)8基本思想 : 將第i個記錄插入在前i-1個有序的記錄中，使前i個記錄有序。直接插入排序 (Insert Sort)k1 ， k2 ， ki-1 ，ki有序k1 ， k2 ， ki ki-1 有序例：10，20，30，40，50，2510，20，25

5、，30，40，509主要操作3033442211 1 2 3 4 50 1 2 3 4 5 33221144304411 1 2 3 4 5 temp442211333030443333304433333030222211主要操作 步驟：*Ri 暫存temp , *將比其大的所有記錄依次后移 *temp ( Ri)插入。監(jiān)視哨作用：*暫存Ri *檢測越界R0R011304410 49 38 65 97 76 13 27 490 1 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 49第一趟第二趟 38 49 65 97 76 13 27 49493838493865

6、6565第三趟 38 49 65 97 76 13 27 49第四趟 38 49 65 97 76 13 27 49第五趟 38 49 65 76 97 13 27 49第六趟 13 38 49 65 76 97 27 49第七趟 13 27 38 49 65 76 97 499797977676977613139776654938134927279776654938274997766549主要步驟：*Ri 暫存0*將比其大的所有記錄依次后移*R0 寫入第i趟： （1）R0=Ri （2）j初值？ （3）若Rj.keyR0.key Rj后移 （4）j下一個（前移） （5）重復(fù)（3）（4）直到？

7、（6）R?=R0i的初值？ 終值？11第i趟： （1）R0=Ri （2）j初值？ （3）若Rj.keyR0.key Rj后移 （4）j下一個（前移） （5）重復(fù)（3）（4）直到？ （6）R?=R0i的初值？ 終值？insertsort(rectype R ,n) for(i=?;id1 d2 d2 . (通常d1=n/2 di+1=di/2),每趟將數(shù)據(jù)表分成di組, 分別對各組進(jìn)行直接插入排序, 直到最后全部記錄在一組為止。15n=10gap=5 49 38 65 97 76 13 27 49 55 044976389765134927550449133827654955970476gap=

8、355270449653876499738765513042765494997gap=2gap=11327554997766538044904491338275549657697659776043827497665380449注:希爾排序開始時增量大, 分組多, 各組含記錄較少,故各組插入快. 后來雖然增量逐漸減小, 各組含記錄增多, 但各組已基本有序, 所以插入速度仍較快.*每趟從Ri開始處理, i=?*Ri要插入前面有序的子序列中, 子序列中每個記錄間隔gap.*每趟gap=gap/2 直到?16*每趟從Ri開始處理, i=?*Ri要插入前面有序的子序列中, 子序列中每個記錄間隔gap。*

9、每趟gap=gap/2 直到?shellsort(rectype R , int n) gap=n/2; while(?) for(i=?;i0 & Rj.keytemp.key) Rj+gap=Rj; j=j-gap; R?=temp; gap=gap/2; 希爾排序的算法穩(wěn)定性:不穩(wěn)定的排序。 （關(guān)鍵字相同的記錄會交換次序）希爾排序算法分析時間性能: T(n)= O(nlog2n)空間性能:在排序過程中，只需附加一個存儲單元暫存當(dāng)前處理記錄。 S(n)=O(1)18交換排序 ( Exchange Sort ) 基本原理：兩兩比較待排序記錄的關(guān)鍵字,若發(fā)生逆序(即排列順序與排序后的次序正好相

10、反)，則交換之。直到所有記錄都排好序?yàn)橹?。交換排序方法冒泡排序(Bubble Sort)快速排序(Quick Sort)19基本思想：在待排序子序列 中，兩兩比較相鄰記錄的關(guān)鍵字，若逆序，則交換。冒泡排序 (Bubble Sort)關(guān)鍵字子序列: ki , ki+1 , knkn-1 與kn , kn-2與kn-1 ki 與ki+1 進(jìn)行比較若逆序，則交換。2055221133442211335544113333445522113344334455221133441155115511221122逆序逆序逆序正序主要操作 由于關(guān)鍵字小的記錄不斷上浮，象小氣泡一樣，故稱為起泡排序。注：在一趟排序中

11、，將關(guān)鍵字最小的記錄頂?shù)降谝晃弧?133445522111 2 3 4 53344552211334455221133223322223333553344552211551155115511445544554455逆序逆序逆序正序從前向操作注：將子序列中最大記錄沉到最后一個221 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 49第一趟 49 38 65 97 76 13 27 494938384965493897496576657697137697139713972727972797499749第二趟 38 49 65 76 13 27 49 97第三趟 38

12、49 65 13 27 49 76 97第四趟 38 49 13 27 49 65 76 97第五趟 38 13 27 49 49 65 76 97第六趟 13 27 38 49 49 65 76 973849386576496513761376132727762776494976493849381338271365381338381313491365134913381365272765134927274913382727654949652749492738273849主要步驟：兩兩相鄰記錄比較，若逆序，則交換。多少趟？注：當(dāng)某趟沒有交換時，沒有必要進(jìn)行下一趟。9749497649652749

13、492738493827如何解決？設(shè)置一個標(biāo)志flag每趟：*初始時flag=0 *若有交換flag=1當(dāng)本趟結(jié)束時，若flag為1，則需要進(jìn)行下一趟。 若flag為0，則排序結(jié)束。23每趟： （1）j初值為1，終值i=? （2）flag=false （3）若Rj.keyRj+1.key Rj與Rj+1交換 flag=true （4）重復(fù)（3） （5）若flag=？,則結(jié)束排序。每趟進(jìn)行比較的次數(shù)依次遞減，第一趟 i的初值？ 終值？bubblesort( rectype R, int n) flag=?; i=?; while(? ) flag=0; for(j=0; jRj+1.key) t

14、emp=Rj; Rj=Rj+1; Rj+1=temp; flag=1; i?; 冒泡排序的算法24冒泡排序的算法分析時間性能：冒泡排序算法由兩重循環(huán)組成，外循環(huán)的次數(shù)主要是由各趟有無交換而決定；內(nèi)循環(huán)表明完成一趟排序所需進(jìn)行的記錄關(guān)鍵字間的比較和記錄的交換。*最好情況：初始時按關(guān)鍵字遞增有序（正序） 比較次數(shù): C=n -1 (僅需一趟排序） 移動次數(shù): M=0 (這一趟沒有逆序） O(n)*最壞情況：初始時關(guān)鍵字遞減有序（逆序）O(n2)*平均情況： T(n)=O(n2)穩(wěn)定性:穩(wěn)定的排序。 （關(guān)鍵字相同的記錄不會交換次序）冒泡排序的算法分析時間性能: T(n)=O(n2) 但在數(shù)據(jù)表基本有

15、序的情況下效率比較高空間性能:排序在排序過程中，只需附加一個存儲單元用于交換。 S(n)=O(1)26快速排序 (Quick Sort)基本思想是任取待排序子序列中的一個記錄 (例如取第一個) 作為基準(zhǔn), 按照該記錄關(guān)鍵字的大小, 將整個子序列劃分為左右兩個子序列： 左側(cè)所有記錄的關(guān)鍵字都小于基準(zhǔn)記錄的關(guān)鍵字右側(cè)所有記錄的關(guān)鍵字都大于或等于基準(zhǔn)記錄的關(guān)鍵字klow , klow+1 , , khighklow , klow+1, klow , khigh基準(zhǔn)記錄則排在這兩個子序列中間(這也是該記錄的最終排序的位置)。然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的記錄都排在相應(yīng)位置上為止。小

16、大272125493516081 2 3 4 5 6pivot213525164908temp暫存基準(zhǔn)212549351608212108082525161649492121基本思想：將后面所有關(guān)鍵字小于基準(zhǔn)關(guān)鍵字的記錄移到前面，將前面所有關(guān)鍵字大小基準(zhǔn)關(guān)鍵字的記錄移動后面。反復(fù)交替操作： *從后向前找到第一個關(guān)鍵字小于基準(zhǔn)的記錄與基準(zhǔn)交換， *從前向后找到第一個關(guān)鍵字大于基準(zhǔn)的記錄與基準(zhǔn)交換。21210821252521281 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 49第一趟temp49pivotji276527651313979749 27 38 13

17、76 97 65 4949反復(fù)交替操作： *從后向前找到第一個關(guān)鍵字小于基準(zhǔn)的記錄前移 *從前向后找到第一個關(guān)鍵字大于基準(zhǔn)的記錄后移設(shè)置指針j（從后向前掃描）設(shè)置指針i（從前向后掃描）劃 分在Rlow.high劃分的主要步驟：（1）初值？（2）temp=Rlow（3）從后向前：當(dāng)Rj=temp時，j-;（4）Rj前移？（5）從前向后：當(dāng)Ritemp時，j-;（4）Rj前移？（5）從前向后：當(dāng)Ritemp.key) j-; if( ?) R?=Rj;i+; while(? & Ri.keytemp.key) i+; if(?) R?=Ri;j-; return ?;301 2 3 4 5 6 7

18、 8 初始 49 38 65 97 76 13 27 49第一趟pivot 27 38 1376 97 65 49 49快速排序49132738769749 654965Rs.t快速排序主要步驟：(遞歸）（1）在Rs.t進(jìn)行劃分，確定基準(zhǔn)的位置k（2）在Rs.?進(jìn)行快速排序（3）在R?.t進(jìn)行快速排序遞歸出口？31主要步驟：(遞歸） Rs.t （1）在Rs.t進(jìn)行劃分，確定基準(zhǔn)的位置i（2）在Rs.?進(jìn)行快速排序（3）在R?.t進(jìn)行快速排序遞歸出口？快速排序的算法quicksort( R,s,t)rectype R ;int s,t; if( ?) i=partition(R,s,t); /*

19、劃分并確定基準(zhǔn)位置*/ quicksort(R,s,?); /*遞歸處理左序列*/ quicksort(R,?,t); /*遞歸處理右序列*/ 32時間性能：取決于每一次劃分的結(jié)果?？焖倥判虻乃惴ǚ治?最壞情況：每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的結(jié)果只是一個區(qū)間，則排序必須做n-1趟，每一趟中需做n-i次比較，所以最大比較次數(shù)為：33用第一個對象作為基準(zhǔn)對象快速排序退化的例子 08 16 21 25 25* 49081 2 3 4 5 6 pivot初始16 16 21 25 25* 49 08i = 121 21 25 25* 49 16i = 2 0825

20、 25 25* 49 21i = 3 16 08 25* 4925*25i = 4 21 16 084925*i = 525 21 16 08快速排序的算法分析*最好情況：每次所取的基準(zhǔn)都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左右兩個無序子區(qū)間的長度大致相等。 設(shè)C(n)表示對長度為n 的序列進(jìn)行快速排序所需的比較次數(shù)，它等于劃分所需的比較次數(shù)n-1，加上平分后左右兩個無序子區(qū)間進(jìn)行快速排序所需的比較次數(shù)。假設(shè)數(shù)據(jù)長度n=2k k=log2n快速排序的算法分析穩(wěn)定性:不穩(wěn)定的排序。 （關(guān)鍵字相同的記錄會交換次序）時間性能: 最壞時間T(n)=O(n2) 最好時間T(n)=O(nlog2

21、n） 已證明，平均時間T(n)=O(nlog2n)空間性能:排序算法是利用遞歸實(shí)現(xiàn)的，排序過程中需附加?？臻g用于存儲遞歸各層信息，則 S(n)=O(log2n)36選擇排序(Selection Sort)基本原理: 在待排序的子序列中, 選擇關(guān)鍵字最小(或最大)的記錄, 存放在已排序的子序列中。 排序方法直接選擇排序(Straight Select Sort) 堆排序(Heap Sort)37基本思想 :在子序列中選擇具有最小(或最大)關(guān)鍵字的記錄, 若它不是這子序列中的第一位，則將它調(diào)入到第一位上。直接選擇排序 (Straight Select Sort)ki ， ki+1 ， ，knkd

22、， k2 ， k1 ki-1 最小(或最大)例：30，20，50，10，40，7010，20，50，30，40，70kd381 2 3 4 5 6 7 8 初始 49 65 38 97 76 13 27 49第一趟 49 65 38 97 76 13 27 49131349第六趟 13 27 38 49 49 97 65 76第二趟 13 65 38 97 76 49 27 49第三趟 13 27 38 97 76 49 65 49第四趟 13 27 38 97 76 49 65 49第五趟 13 27 38 49 76 97 65 49第七趟 13 27 38 49 49 65 97 762

23、7652749389749497649656597766797主要步驟:在子序列中選擇關(guān)鍵字最小的記錄交換到子序列的第一位.第i趟子序列的區(qū)間?第i趟:(1)從Ri Rn中選擇最小關(guān)鍵字的記錄Rk;(2)若k!=i, 則Ri與Rk交換.39直接選擇排序的算法第i趟:(1)從RiRn中選擇最小關(guān)鍵字的記錄Rk;(2)若k!=i, 則Ri與Rk交換.selectsort ( rectype R , int n ) for ( int i = ?; i ?; i+ ) k = i; /選擇具有最小排序碼的對象 for ( j =?; j n; j+) if ( Rj.key Rk.key ) k =

24、 ?; /當(dāng)前具最小排序碼的對象 if ( ? ) /對換到第 i 個位置 temp=Ri; Ri=Rk; Rk=temp; 直接選擇排序算法分析時間性能：直接選擇排序算法由兩重循環(huán)組成，外循環(huán)為n-1趟排序；內(nèi)循環(huán)表明完成一趟排序所需進(jìn)行的記錄關(guān)鍵字間的比較和記錄的后移。O(n2)*時間效率： T(n)=O(n2)*比較次數(shù):直接選擇排序的比較次數(shù)與初始狀態(tài)無關(guān). 第i趟選擇關(guān)鍵字最小的記錄要比較n-i次, 則總的比較次數(shù)為:*移動次數(shù):最好情況是每趟關(guān)鍵字最小的記錄總是子序列中第一位,不需要交換,M=0;最壞情況是每趟都需要將關(guān)鍵字最小的記錄交換到子序列的第一,M=3(n-1). 則平均移

25、動次數(shù)為O(n).直接選擇排序的算法分析穩(wěn)定性:不穩(wěn)定的排序。 （關(guān)鍵字相同的記錄會交換次序）時間性能: T(n)=O(n2)空間性能:需附一個存儲單元用于交換，則 S(n)=O(1)42堆的定義： n個關(guān)鍵字序列k1, k2, . ,kn稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：堆排序 (Heap Sort)ki k2iki k2i+1注：若將序列看成按層次編號的完全二叉樹，根據(jù)二叉樹的性質(zhì),即ki 的左右孩子正好分別為k2i 和k2i+1，因此,堆也可以說是滿足如下性質(zhì)的完全二叉樹:樹中任一分支結(jié)點(diǎn)的值均大于或等于它的孩子結(jié)點(diǎn)的孩子的值.(1 i n/2 )大根堆ki k2iki k2i+1或小根堆

26、43例: ( 96, 83, 27, 38, 11, 9 )96832738119大根堆例: ( 10, 15, 56, 25, 30, 70 )101556253070小根堆注:在大根堆中根(第一個)為最大值. 在小根堆中根(第一個)為最小值.例: (42,13,91,23,24,16,5,88)421391232416588不是根堆若將序列構(gòu)造成堆,就可以確定出序列中的最大( 或最小 )元素. ?構(gòu)造4442139188241605234213918824160523421391232416058842 13 91 23 24 16 05 881 2 3 4 5 6 7 823912388

27、1323882388238891911388132313234288912324160513424291914291429142依次調(diào)整每一個分支結(jié)點(diǎn),使其大于兩個孩子結(jié)點(diǎn).注: 這種方法叫“篩選法”, 要求在其子樹中每個分支結(jié)點(diǎn)都滿足條件的情況下進(jìn)行,因此,要依次逆序調(diào)整每個分支結(jié)點(diǎn).881388132323138845“篩選法”的算法主要步驟: (在Rlow.high中調(diào)整分支結(jié)點(diǎn)Rlow)(1)確定兩個孩子中的大孩子Rj(2)若RiRj 則交換Ri與Rj, i=j 重復(fù)(1)(2) 直到? (由于有可能影響子樹)sift(rectype R,int low, int high) i=lo

28、w; j=2*i; temp=Ri; while( ? ) while (? & Rj.key雙親,則交換*/ i=j; j=?; /*去調(diào)整子樹*/ else break; R?=temp; 堆 排 序堆排序是一種樹型選擇排序?；舅枷?將待排序的子序列k1, k2, . ,ki 構(gòu)造成堆, 從而選擇出關(guān)鍵字最大(或最小)記錄.堆排序分為兩個步驟： 1、根據(jù)初始狀態(tài)，形成初始堆。 2、通過一系列的記錄交換和重新調(diào)整 進(jìn)行排序。4749386597761327491 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 499797656538temp3897494949

29、9776493838 97 76 65 49 49 13 27 389738第一趟3876654949132738重建堆只需調(diào)整根結(jié)點(diǎn)76383849第二趟 76 49 65 38 49 13 27 97277648274965384913276527第三趟 65 49 27 38 49 13 76 97136513492738491349134913第四趟49 49 27 38 13 65 76 971349134927381349131338第五趟 49 38 27 13 49 65 76 971349133827131338第六趟 38 13 27 49 49 65 76 9738272

30、73827第七趟 27 13 38 49 49 65 76 971327主要步驟：（1）將R1.n初建堆。（2） 重復(fù)如下操作： （子序列R1.i) *子序列中第一個記錄與最后一個交換 *重建堆49主要步驟：（1）將R1.n初建堆。（2） 重復(fù)如下操作： （子序列R1.i) *子序列中第一個 記錄與最后一個 交換 *重建堆堆排序的算法heapsort(rectype R,int n) for( i=n/2; i0; i-) sift(R,i,n); /*初建軍堆*/ for(i=?;?;i-) temp=R1; R1=Ri; Ri=temp; /*子序列首尾交換*/ sift(R,1,i-1)

31、; /*重建堆*/ 堆排序算法分析時間性能：堆排序算法分兩部分，一是整個序列初建堆；二是n-1趟的交換和重建堆。O(n)*時間效率： T(n)= O(nlog2n)*重建堆:每次重建堆時, 僅需調(diào)整根結(jié)點(diǎn),最多比較log2n, 則n-1次重建堆時間效率為O(nlog2n) 。*初建堆:若n個結(jié)點(diǎn)的堆構(gòu)成的完全二叉樹的深度為k,則有2k-1 n 2k。 在第 i 層上的分支結(jié)點(diǎn)數(shù)至多為 2i (i = 1, , k-1), 且調(diào)整時最多比較 2 (k-i)。堆排序的算法分析穩(wěn)定性:不穩(wěn)定的排序。 （關(guān)鍵字相同的記錄會交換次序）時間性能: T(n)= O(nlog2n)空間性能:需附一個存儲單元用

32、于交換，則 S(n)=O(1)52歸并排序 (Merge Sort)基本思想:通過對兩個有序記錄序列的合并來實(shí)現(xiàn)排序。所謂歸并是指將若干個已排好序的子序列合并成一個有序的子序列。這里是將兩個有序的子序列合并成一個有序的子序列稱二路歸并。klow , kmid , kmid , , khighklow , , khigh有序有序有序例：30，40，50，11，33，55 ，7711，30， 33， 40，50，55，77532125493516081 2 3 4 5 6 75521254935160855主要操作:掃描兩個子序列,將關(guān)鍵字小的記錄依次歸并。設(shè)指針i掃描第一個子序列設(shè)指針j掃描第二

33、個子序列 j i主要步驟:Rlow.mid.high(1)i,j初值?(2)若Ri.keyRj.key 則歸并Ri; i后移; 否則歸并Rj; j 后移;(3)重復(fù)(2) 直到?(4)剩余? RR154主要步驟:Rlow.mid.high(1)i,j初值?(2)若RiRj 則歸并Ri; i后移; 否則歸并Rj; j 后移;(3)重復(fù)(2) 直到?(4)剩余? 二路歸并算法merge ( R, low, mid, high )rectype R;int low,mid,high; rectype R1; i =low; j = mid, k = 0;R1=malloc( ); while ( i

34、 =mid & j =high ) if ( Ri.key = Rj.key ) /*兩兩比較*/ R1k = Ri; i+; k+; /*歸并Ri*/ else R1k = Rj; j+; k+; /*歸并Rj*/ while ( i=mid ) R1k = Ri; i+; k+; /*前序列有剩余*/ while ( j=high ) R1k = Rj; j+; k+; /*前序列有剩余*/ for(k=0,i=low;i=high;k+,i+) Ri=R1k;554938659776132749881638 4965 97 13 76 27 49 16 88 38 49 65 97 13

35、 27 49 76 13 27 38 49 49 65 76 97 16 88 16 88 13 16 27 38 49 49 65 76 88 97 4938659776132749881638 49 65 97 13 76 27 49 16 88 38 49 65 97 13 27 49 76 16 88 13 27 38 49 49 65 76 97 16 88 歸并排序 二路歸并：將相鄰的的兩個有序的序列合并成一個有序的序列。 設(shè)每趟子序列的長度為length。初始狀態(tài)：每個子序列的長度為length=1(只含一個記錄）。初始每一趟歸并排序：兩兩等長的子序列合并，最后的剩余不完整子序列

36、？兩種情況：（1）剩余一個子序列（2）兩個不完整序列56每一趟歸并排序：兩兩等長的子序列合并，最后的剩余不完整子序列？兩種情況：（1）剩余一個子序列（2）兩個不完整序列一趟歸并算法mergepass ( R, length, n )rectype ;int length, n; i = 0; for ( i=0;i+2*length-1n;i=i+2*length) /* 歸并兩個等長的子序列*/ merge( R, i, i+length-1, i+2*length-1); if ( i+length-1n ) merge(R, i, i+length-1, n-1); /*剩余兩個不完整的

37、子序列*/ 57mergesort ( rectype R , int n ) length = 1; while ( length n ) mergepass ( R, length, n ); length= 2*length;(二路)歸并排序的算法主要思想：在R和R1兩個數(shù)據(jù)表中一趟一趟交替歸并。每一趟歸并后，子序列的長度擴(kuò)大一倍，即length=2*length 其初值length=1歸并排序算法分析時間性能：每一趟歸并需將一個數(shù)據(jù)表的所有記錄歸并到另一個數(shù)據(jù)表中，則一趟歸并的時間效率為O(n)。歸并排序共需約log2n趟，則總的時間效率為 T(n)=O(nlog2n) 空間性能:需附

38、一個數(shù)據(jù)表存儲空間用于交替歸并，則 S(n)=O(n)穩(wěn)定性:穩(wěn)定的排序。 （關(guān)鍵字相同的記錄不會交換次序）基數(shù)排序(Radix Sort)多關(guān)鍵字排序示例 *每張撲克牌有兩個“關(guān)鍵字”:花色和面值 (它們之間有次序的優(yōu)先)。 *可以先對花色排序，或先對面值排序多關(guān)鍵字有序:在數(shù)據(jù)表 R1,R1,., Rn中，每個記錄Ri含d個關(guān)鍵字(Ki1,Ki2,., Kid)。若對序列中的任意兩個記錄Ri和Rj都有 (Ki1,Ki2,., Kid) (Kj1,Kj2,., Kjd) 則稱序列對關(guān)鍵字(Ki1,Ki2,., Kid)有序，且K1稱為最高位關(guān)鍵字，Kd稱為最低位關(guān)鍵字?；?數(shù) 排 序基本原理

39、:采用“分配”和“收集”兩種運(yùn)算, 用對多關(guān)鍵字進(jìn)行排序的思想實(shí)現(xiàn)對單關(guān)鍵字進(jìn)行排序。此時可將單關(guān)鍵字K看成是一個子關(guān)鍵字組：(Ki1,Ki2,., Kid)排序過程：設(shè)關(guān)鍵字共有d位，讓j= d, d-1,.,1, 依次執(zhí)行d次“分配”與“收集”。546732414477543233634587例:324154323363546744774587543232413363546744774587324133635432546744774587324133634477458754325467個位十位百位千位61基數(shù)排序的基本要求(1)確定所有關(guān)鍵字的最大位數(shù)d.(2)將各關(guān)鍵字按最大位補(bǔ)齊. (

40、數(shù)字前補(bǔ)0, 字符串后補(bǔ)空格)(3)確定進(jìn)制r. (數(shù)字r=10,16, 字符r=26)(4)利用單鏈表鏈接所有記錄.(5)附加r個鏈?zhǔn)疥?duì)列.typedef struct node keytype datad; datatype other; struct node ;RecType;RecType *headMAXR,*tailMAXR;62head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0 tail1 tail2 tail3 tail4 tail5 tail6 tail7 tail8 tail9 546732414477543233634587L546732414477543233634587543233635467447745873241L分配收集第一趟排序63head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0 tail1 tail2 tail3 tail4 tail5 tail6 tail7 tail8 tail9 324154323363546744774587L32414477543233634587324133635467447745875432L分配收集第二