數(shù)據(jù)結(jié)構(gòu)--(9)課件

1、 9.1 排序基本概念 9.2 插入排序 9.3 交換排序 9.4 選擇排序 9.5 歸并排序 9.6 基數(shù)排序 9.7 內(nèi)部排序總結(jié) 9.8 有關(guān)排序算法的C語言源程序 9.9 多路歸并用于外排序的簡介第9章 排序返回主目錄第9章排序9.1 排序基本概念 排序（sorting）又稱分類, 意指把一批雜亂無章的數(shù)據(jù)序列重新排列成有序序列。按待排序的記錄的數(shù)量多少, 排序過程中涉及的存儲介質(zhì)不同, 排序方法分為兩大類: 內(nèi)部排序和外部排序。內(nèi)部排序是指待排序的記錄存放在計算機內(nèi)存之中; 外部排序是指待排序的記錄數(shù)量很大, 以至于內(nèi)存容納不下而存放在外存儲器之中, 排序過程需要訪問外存。 排序的依

2、據(jù)可以是記錄的主關(guān)鍵字, 也可以是次關(guān)鍵字, 甚至是若干數(shù)據(jù)項的組合。 為了討論方便, 把排序所依據(jù)的數(shù)據(jù)項統(tǒng)稱排序關(guān)鍵字, 簡稱關(guān)鍵字。 假設(shè)含有n個記錄的序列為R1, R2, , Rn , 其相應(yīng)的關(guān)鍵字序列為K1, K2, , Kn , 所謂排序就是將記錄按關(guān)鍵字非遞減(或非遞增)的順序重新排列起來。 在待排序的記錄中若有多個相同的關(guān)鍵字, 在用某種方法排序之后, 這些關(guān)鍵字相同的記錄相對先后次序不變, 則稱這種排序方法是穩(wěn)定的; 否則是不穩(wěn)定的。本章所介紹的內(nèi)部排序方法包括插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。 前四類排序是通過比較關(guān)鍵字的大小決定記錄先后次序,也稱為比較排

3、序。 基數(shù)排序是不經(jīng)關(guān)鍵字比較的排序方法。 為了討論方便, 在此把排序關(guān)鍵字假設(shè)為整型。 記錄的結(jié)構(gòu)定義為: struct node int key; /*排序關(guān)鍵字域*/ int oth; /*其它域, 根據(jù)需要自己設(shè)定*/ 9.2 插入排序 9.2.1 直接插入排序 直接插入排序（straight insertion sort）是一種最簡單的排序方法。 它的基本操作是將一個記錄插入到一個長度為m（假設(shè)）的有序表中, 使之仍保持有序, 從而得到一個新的長度為m1的有序表。 算法思路: 設(shè)有一組關(guān)鍵字K1, K2, , Kn , 排序開始就認為K1是一個有序序列; 讓K2插入上述表長為1的有序

4、序列, 使之成為一個表長為2的有序序列; 然后讓K3插入上述表長為2的有序序列, 使之成為一個表長為3的有序序列; 依次類推, 最后讓Kn插入上述表長為n-1的有序序列, 得一個表長為n的有序序列。 例9.1 設(shè)有一組關(guān)鍵字序列55, 22, 44, 11, 33, 這里n=5, 即有5個記錄。 如圖 9.1 所示。 請將其按由小到大的順序排序在具體實現(xiàn)Ki 向前邊插入時, 有兩種方法。 一種方法是讓Ki與K1, K2, 順序比較; 另一種方法是Ki與 Ki-1 , Ki-2 倒著比較。 這里選用后一種方法。 用一維數(shù)組r做存儲結(jié)構(gòu), n表示記錄個數(shù), MAXSIZE為常量， 且MAXSIZE

5、n。 則算法如下: 算法 9.1void stinsort (struct node rMAXSIZE, int n) for (i=2; i r0.key) rj+1=rj; j-; rj+1=r0; /*將r0即原ri記錄內(nèi)容, 插到rj后一位置*/ /*stinsort*/ 此算法外循環(huán)n-1次, 在一般情況下內(nèi)循環(huán)平均比較次數(shù)的數(shù)量級為(n), 所以算法總時間復(fù)雜度為(n2)。 由于比較過程中, 當(dāng)Kj 與K0相等時并不移動記錄, 因此直接插入排序方法是穩(wěn)定的。 直接插入排序也可用單鏈表做存儲結(jié)構(gòu)。 當(dāng)某結(jié)點i的關(guān)鍵字Kj與前邊有序表比較時,顯然先與K1 比較, 再與K2比較, , 即

6、從鏈表表頭結(jié)點開始向后逐一比較更合適。另外, 直接插入排序在原關(guān)鍵字序列基本有序或n值較小時, 它是一種最常用的排序方法, 它的時間復(fù)雜度接近于O(n)。 但是, 當(dāng)n值又較大時, 此方法就不再適用。 9.2.2 折半插入排序 當(dāng)直接插入排序進行到某一趟時, 對于ri.key來講, 前面i-1個記錄已經(jīng)按關(guān)鍵字有序。 此時不用直接插入排序的方法, 而改為折半查找, 找出ri.key應(yīng)插的位置, 然后插入。 這種方法就是折半插入排序（binary insertion sort）。算法如下: 算法 9.2 void binasort(struct node rMAXSIZE, int n) for

7、 (i=2; i=n; i+) ZK(r0=ri; l=1; h=i-1; while (l=h) mid= (l+h)/2; if(r0.key=l; j-) rj+1=rj; rl=r0; /*binasort*/ 9.2.3 希爾排序 希爾排序（shell sort）是D希爾（D.L.Shell）提出的“縮小增量”的排序方法。它的作法不是每次一個元素挨一個元素的比較, 而是初期選用大跨步（增量較大）間隔比較,使記錄跳躍式接近它的排序位置; 然后增量縮小; 最后增量為 1, 這樣記錄移動次數(shù)大大減少, 提高了排序效率。希爾排序?qū)υ隽啃蛄械倪x擇沒有嚴格規(guī)定。 算法思路: 先取一個正整數(shù)d1(

8、d1 n), 把全部記錄分成d1 個組, 所有距離為d1的倍數(shù)的記錄看成一組, 然后在各組內(nèi)進行插入排序; 然后取d2 (d2 =1), 即所有記錄成為一個組為止。一般選d1約為n/2, d1為 d1 /2, d3為d1 /2, , d1 =1。 例92 有一組關(guān)鍵字76, 81, 60, 22, 98, 33, 12, 79, 將其按由小到大的順序排序。 這里n=8, 取d1 =4, d2=2, d3 =1, 其排序過程如圖9.2所示。 算法實現(xiàn)見算法9.3。 算法 9.3 void shellsort(struct node rMAXSIZE, int n) k=n/2; /*k值代表前文

9、中的d值*/ while(k=1) for(i=k+1; ir0.key)& (j=0) rj+k=rj; j=j-k; rj+k=r0; ZK) k=k/2; ZK) /*shellsort*/ 此算法外層循環(huán)是增量由n/2逐步縮小到的循環(huán)。 for所構(gòu)成的循環(huán)是針對某一特定的增量k, 進行大跨步跳躍式的插入排序。 例如k=2時, 關(guān)鍵字分成二組, 見圖9.2的第2行, 其中第1組是76,12,98,60, 排序后的結(jié)果為12,60,76,98,插入操作如下: i=3 K1=76有序, K3 =12向前插; i=5 12,76有序, K5 =98不移動; i=7 12,76,98有序, K7

10、 =60向前插; 第2組是33,22,81,79, 排序后的結(jié)果為22,33,79,81, 插入操作如下: HT5”SS i=4 K2=33 有序, K2 =22向前插; i=6 22,33 有序, K6=81不移動; i=8 22,33,81有序, K8 =79向前插; 對整個文件來說, 排序結(jié)果實際上為: 12,22,60,33,76,79,98,81。 當(dāng)K=1時, 此算法就等同于直接插入排序方法。 由于前邊大增量的處理, 使關(guān)鍵字大體有序, 因此最后一趟排序移動的記錄少, 處理速度快。 希爾排序的分析是一個復(fù)雜的問題, 因為它的時間是所選定的“增量序列”的函數(shù), 這涉及到數(shù)學(xué)上一些尚未

11、解決的難題。 到目前為止, 沒有人找到一種最好的增量序列。有人在大量實驗基礎(chǔ)上推導(dǎo)出, 希爾排序的時間復(fù)雜度為O(n1.3）。如果對關(guān)鍵字序列6,7,51,2,52,8進行希爾排序, 可以看出希爾排序是不穩(wěn)定的。 9.3 交換排序 9.3.1 冒泡排序 冒泡排序(bubble sort)是一種人們熟知的、 最簡單的交換排序方法。 在排序過程中, 關(guān)鍵字較小的記錄經(jīng)過與其它記錄的對比交換, 像水中的氣泡向上冒出一樣, 移到序列的首部, 故稱此方法為冒泡排序法。 排序的算法思路是: (1) 讓j取n至2, 將rj.key與rj-1.key比較, 如果rj.keyi;j-)if (rj.keyrj-

12、1.key) x=rj;rj=ri; ri=x;tag=1;ZK) i+; while (tag=1 & in); /*bubblesort*/ 算法中tag為標(biāo)志變量, 當(dāng)某一趟處理過程中未進行過記錄交換時, tag值應(yīng)為0； 若發(fā)生過交換, 則tag值為1。 所以外循環(huán)結(jié)束條件是: 或者tag=0,已有序; 或者i=n, 已進行了n-1趟處理。 該算法的時間復(fù)雜度為O(n2)。但是, 當(dāng)原始關(guān)鍵字序列已有序時, 只進行一趟比較就結(jié)束, 此時時間復(fù)雜度為O(n)。 9.3.2 快速排序 快速排序由霍爾(Hoare)提出, 它是一種對冒泡排序的改正。 由于其排序速度快, 故稱快速排序(quic

13、k sort)。 快速排序方法的實質(zhì)是將一組關(guān)鍵字K1,K2,Kn 進行分區(qū)交換排序。 其算法思路是: （1）以第一個關(guān)鍵字K1為控制字, 將 K1, K2, Kn 分成兩個子區(qū), 使左區(qū)所有關(guān)鍵字小于等于K1, 右區(qū)所有關(guān)鍵字大于等于K1, 最后控制字居兩個子區(qū)中間的適當(dāng)位置。 在子區(qū)內(nèi)數(shù)據(jù)尚處于無序狀態(tài)。 （2）將右區(qū)首、尾指針(記錄的下標(biāo)號)保存入棧, 對左區(qū)進行與第（1）步相類似的處理, 又得到它的左子區(qū)和右子區(qū), 控制字居中。 （3）重復(fù)第（1）、 （2）步, 直到左區(qū)處理完畢。 然后退棧對一個個子區(qū)進行相類似的處理, 直到?？?。 由以上三步可以看出: 快速排序算法總框架是進行多趟的

14、分區(qū)處理; 而對某一特定子區(qū), 則應(yīng)把它看成又是一個待排序的文件, 控制字總是取子區(qū)中第一個記錄的關(guān)鍵字?，F(xiàn)在設(shè)計一個函數(shù)hoare, 它僅對某一待排序文件進行左、右子區(qū)的劃分, 使控制字居中; 再設(shè)計一個主體框架函數(shù)quicksort, 在這里多次調(diào)用hoare函數(shù)以實現(xiàn)對整個文件的排序。 例9.4 HT設(shè)有一組關(guān)鍵字46,56,14,43,95,19,18,72, 這里n=8。 試用快速排序方法由小到大進行排序。 1) 分區(qū)處理函數(shù)hoare 思路: 首先用兩個指針i、j分別指向首、尾兩個關(guān)鍵字, i=1,j=8。 第一個關(guān)鍵字46作為控制字, 該關(guān)鍵字所屬的記錄另存儲在一個x變量中。從文

15、件右端元素rj.key開始與控制字x.key相比較, 當(dāng)rj.key大于等于x.key時, rj不移動, 修改j指針, j-, 直到rj.keyx.key,把記錄ri移到文件右邊j所指向的位置; 再到文件右邊修改j指針, j-。 重復(fù)上面的步驟, 直到i=j, 此處就是控制字記錄x所在的位置。 至此將文件分成了左、 右兩個子區(qū), 其具體操作見圖9.4。 算法如算法 9.5（假設(shè)某區(qū)段文件, 指向第一個記錄的指針為l, 指向最后一個記錄的指針為h）。 算法 9.5 int hoare(struct node rMAXSIZE,int l,int h) i=1;j=h;x=ri; do while

16、(i=x.key) j-; if (ij) ri=rj;i+; while(ij) &(ri.key=x.key) i+; if (i=j) rj=ri; j-; while(ij); ri=x;return(i); /*hoare*/ 2） 快速排序主體框架算法 對一個文件, 令l=1,h=n, 調(diào)用hoare, 求出i; 然后右子區(qū)l=i+1,h=n, 入棧, 對左子區(qū)令l=1,h=i-1, 再次調(diào)用hoare, , 如此反復(fù), 直到全部文件記錄處理完畢。 圖9.5中第1行表示對例9.4的數(shù)據(jù)進行過一次分區(qū)處理之后的結(jié)果, 在此基礎(chǔ)上經(jīng)過多次調(diào)用hoare后, 最后得出第5行的結(jié)果。 下面

17、給出快速排序的遞歸算法和非遞歸算法。 非遞歸算法: 算法 9.6void quicksort1(struct node rMAXSIZE, int n) /*int sn2;輔助棧s*/ l=1;h=n;tag=1;top=0; do while (lh) i=hoare(r,l,h); top+;stop0=i+1; stop1=h;h=i-1; else l=stop0; h=stop1;top-; while (tag=1); /*quicksort1*/ 遞歸算法: 算法 9.7void quicksort2(struct node r,int l,int h) if(lh) i=ho

18、are(r,l,h); /*劃分兩個區(qū)*/quicksort2(r,l,i-1); /*對左分區(qū)快速排序*/quicksort2(r,i+1,h); /*對右分區(qū)快速排序*/ /*quicksort2*/ 在主程序調(diào)用非遞歸算法比較簡單易懂。 若要調(diào)用遞歸算法, 因函數(shù)的形參不同, 需做預(yù)處理。主程序的主要操作如下: 調(diào)用遞歸函數(shù) 調(diào)用非遞歸函數(shù) creat(r,n); creat(r,n); l=1;h=n; quicksort1(r,n); quicksort2(r,l,h); 輸出r; 輸出r; 3） 快速排序算法空間時間及穩(wěn)定性分析 快速排序的非遞歸算法引用了輔助棧, 它的深度為log

19、2n。 假設(shè)每一次分區(qū)處理所得的兩個子區(qū)長度相近, 那么可入棧的子區(qū)長度分別為: n/21, n/22, n/23, , n/2k, 又因為n/2k=1,所以k= log2n。分母中2的指數(shù)恰好反映出需要入棧的子區(qū)個數(shù), 它就是log2n, 也即棧的深度。 在最壞情況下, 比如原文件關(guān)鍵字已經(jīng)有序, 每次分區(qū)處理僅能得到一個子區(qū)。 可入的子區(qū)個數(shù)接近n, 此時棧的最大深度為n。 快速排序主體算法時間運算量約O(log2n), 劃分子區(qū)函數(shù)運算量約O(n), 所以總的時間復(fù)雜度為O(n log2n), 它顯然優(yōu)于冒泡排序O(n2)?？墒撬惴ǖ膬?yōu)勢并不是絕對的, 試分析, 當(dāng)原文件關(guān)鍵字有序時,快

20、速排序時間復(fù)雜度是O(n2),這種情況下快速排序不快。 而這種情況的冒泡排序是O(n),反而很快。在原文件記錄關(guān)鍵字無序時的多種排序方法中, 快速排序被認為是最好的一種排序方法。 例9.5 試對6, 7, 51, 2, 52, 8進行快速排序。 排序過程簡述如下: 67512528初始狀態(tài) 52 7 51 6 7 8 2 52 516 7 8 2 52 51 6 7 8 最后狀態(tài)9.4 選擇排序 9.4.1 簡單選擇排序 簡單選擇排序(simple selection sort)也是直接選擇排序。 此方法在一些高級語言課程中做過介紹, 是一種較為容易理解的方法。 對于一組關(guān)鍵字K1, K2,

21、Kn, 將其由小到大進行簡單排序的具體思路是: 首先從K1, K2, Kn中選擇最小值, 假如它是Kz, 則將Kz與K1對換; 然后從K2, K3, , Kn中選擇最小值Kz, 再將Kz與Kz對換; 如此進行選擇和調(diào)換n-2趟。 第(n-1)趟, 從Kn-1、 Kn中選擇最小值Kz, 將Kz與Kn-1對換, 最后剩下的就是該序列中的最大值, 一個由小到大的有序序列就這樣形成的。該算法的時間復(fù)雜度為O(n2)。 由此可見, 對于n個記錄的關(guān)鍵字, 需要處理n-1趟; 而在每趟之中, 又有一個內(nèi)循環(huán)。 圖9.6是一個有5個關(guān)鍵字3,4,1,5,2的簡單選擇排序過程的示意圖。 假設(shè)用變量z記下較小值

22、的下標(biāo), 則算法如算法 9.8。 算法 9.8 void sisort(struct node rMAXSIZE,int n) for (i=1;in;i+) z=i; for (j=i+1;j=n;j+) if (rj.keyrz.key) z=j; x=ri;ri=rz; rz=x; /*sisort*/ 9.4.2 堆排序 除了簡單選擇排序之外, 還有樹形選擇排序(錦標(biāo)賽排序)。 1964年威洛姆斯(J.Willioms)提出了進一步改正的排序方法, 即堆排序(heap sort)。 堆是n個元素的有限序列k1, k2, , kn, 它當(dāng)且僅當(dāng)滿足如下關(guān)系: ki=k2i ki= k2i

23、+1 i=1,2, 這是一個上小、 底大的堆。 若是一個上大、 底小的堆, 只需把“=”即可。 堆是一種數(shù)據(jù)元素之間的邏輯關(guān)系, 常用向量做存儲結(jié)構(gòu)。 對于第 6 章中介紹的滿二叉樹, 當(dāng)對它的結(jié)點由上而下, 自左至右編號之后, 編號為i的結(jié)點是編號為2i和2i+1結(jié)點的雙親。反過來講, 結(jié)點2i是結(jié)點i的左孩子, 結(jié)點2i+1是結(jié)點i的右孩子。圖9.7表示完全二叉樹和它在向量中的存儲狀態(tài)。 結(jié)點編號對應(yīng)向量中的下標(biāo)號。 用堆的概念分析向量中的數(shù)據(jù), 它顯然滿足（上小、 底大）堆的關(guān)系。 不難看出, 滿足堆的邏輯關(guān)系的一組數(shù)據(jù), 可畫成二叉樹的形狀, 并且它是一棵完全二叉樹樹形。因此, 也可借

24、助完全二叉樹來描述堆的概念。若完全二叉樹中任一非葉子結(jié)點的值小于等于（或大于等于）其左、 右孩子結(jié)點的值, 則從根結(jié)點開始按結(jié)點編號排列所得的結(jié)點序列就是一個堆。在圖9.8中(a)、 (c)是堆, (b)、 (d)不是堆。 堆排序的思路是: 把n個記錄存于向量r之中, 把它看成完全二叉樹, 此時關(guān)鍵字序列不一定滿足堆的關(guān)系。堆排序大體分兩步處理。 (1) 初建堆。從堆的定義出發(fā), 當(dāng)i=1,2, ,n/2時應(yīng)滿足ki=k2i和ki=k2i+1。所以先取i=n/2 (它一定是第n個結(jié)點雙親的編號), 將以i結(jié)點為根的子樹調(diào)整為堆; 然后令i=i-1, 將以i結(jié)點為根的子樹調(diào)整為堆。此時可能會反復(fù)

25、調(diào)整某些結(jié)點, 直到i=1為止, 堆初步建成。 (2) 堆排序。 首先輸出堆頂元素（一般是最小值）, 讓堆中最后一個元素上移到原堆頂位置, 然后恢復(fù)堆。因為經(jīng)過第一步輸出堆頂元素的操作后, 往往破壞了堆關(guān)系, 所以要恢復(fù)堆; 重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟, 直到全部元素輸出完為止。 例9.6 設(shè)有n個記錄(n=8)的關(guān)鍵字是46,55,13,42,94,17,5,80, 試對它們進行堆排序。 第一步: 初建堆。因為n=8, 所以從i=4開始, 見圖9.9。 調(diào)整成為堆是一個較復(fù)雜的過程, 當(dāng)i值確定之后用kz記下ki的值, 用kz分別與k2i和k2i+1比較, 可理解為kz

26、值與結(jié)點i的左、 右孩子的關(guān)鍵字比較。 如果一開始kz比k2和k2+1均小, 則不進行任何調(diào)整。例如i=4時, k4k8 (4280), 就不用調(diào)整, 見圖9.9(a)。如果結(jié)點i的某一個孩子的關(guān)鍵字小于kz, 則把這個孩子結(jié)點移上來。如果結(jié)點i的兩個孩子的關(guān)鍵字都小于kz, 那么將兩個孩子中較小的一個調(diào)整上來。 如果結(jié)點i的兩個孩子的關(guān)鍵字都小于kz, 那么將兩個孩子中較小的一個調(diào)整上來。 在圖9.9(c)中, i=1時, k2、 k3都小于kz(42,546), 則讓k3(即5)移上去。 此時需要讓kz與更下一層的左、 右孩子的關(guān)鍵字進行比較, 直到某一層的左、右孩子的關(guān)鍵字不小于kz,

27、或左、 右孩子不存在為止。 此時將kz填入適當(dāng)位置, 使之成為堆。在圖9.9(c)中, 先把5調(diào)整上來, 然后把13移到5原來的位置上, 最后將kz(即46)填到13原來的位置上。 第二步: 堆排序。 這是一個反復(fù)輸出堆頂元素, 將堆尾元素移至堆頂, 再調(diào)整恢復(fù)堆的過程。恢復(fù)堆的過程與初建堆中i=1時所進行的操作完全相同。請注意: 每輸出一次堆頂元素，堆尾的邏輯位置退1，直到堆中剩下一個元素為止。排序過程如圖 9.10所示。 堆排序算法實現(xiàn): 由上述可知, 有一種操作過程（即調(diào)整恢復(fù)堆）要被多次反復(fù)調(diào)用, 那就是當(dāng)i值確定之后, 以ki為比較參照值, 與它的左、 右孩子的關(guān)鍵字比較和調(diào)整, 使

28、得以結(jié)點i為根的子樹成為堆, 因此把這個過程設(shè)計成一個函數(shù)heap。另外, 當(dāng)然還需再設(shè)計一個主體算法, 使在初建堆階段, 讓i從n/2變化到1, 循環(huán)調(diào)用函數(shù)heap。而在堆排序階段, 每輸出一次堆頂元素同時將堆尾元素移至堆頂之后, 就調(diào)用一次heap函數(shù)來恢復(fù)堆。主體算法由函數(shù)heapsort實現(xiàn)。 以編號為i的結(jié)點為根, 調(diào)整為堆的算法為: 算法 9.9void heap(struct node rMAXSIZE,int i, int m)/*i是根結(jié)點編號, m是以i結(jié)點為根的子樹的最后一個結(jié)點編號*/ x=ri;j=2*i; /*x保存根記錄內(nèi)容, j為左孩子編號*/ while (

29、j=m) if (jrj+1.key) j+; /*當(dāng)結(jié)點i有左、 右兩個孩子時, j取關(guān)鍵字較小的孩子結(jié)點編號*/ if (rj.keym, 以便結(jié)束循環(huán)*/ ri=x; /* heap*/堆排序主體算法: 算法 9.10HT void heapsort(struct node rMAXSIZE,int n) /*n為文件的實際記錄數(shù),r0沒有使用*/for (i=n/2;i=1;i-) heap(r,i,n) /*初建堆*/for (v=n;v=2;v-) printf(%5d,r1.key); /*輸出堆頂元素*/x=r1; r1=rv; rv=x; /*堆頂堆尾元素交換*/heap(r

30、,1,v-1); /*本次比上次少處理一個記錄*/ printf(%5d,r1.key); /* heapsort*/ 在堆排序圖示中, 堆越畫越小, 實際上在r向量中堆頂元素輸出之后并未刪除, 而是與堆尾元素對換。 由圖9.10可知輸出的是一個由小到大的升序序列, 而最后r向量中記錄的關(guān)鍵字從r1.key到rn.key是一個由大到小的降序序列。堆排序中heap算法的時間復(fù)雜度與堆所對應(yīng)的完全二叉樹的樹深log2n+1 相關(guān)。 而heapsort中對heap的調(diào)用數(shù)量級為n, 所以整個堆排序的時間復(fù)雜度為O(nlog2n)。在內(nèi)存空間占用方面, 基本沒有額外的輔助空間, 僅有一個x?，F(xiàn)在來分析

31、堆排序的穩(wěn)定性問題。設(shè)有一組關(guān)鍵字: 6,7,51,2,52,8,經(jīng)排序后的結(jié)果是: 2,52,51,6,7,8。 本來51在前面, 排序后52移到51的前面, 所以說堆排序是不穩(wěn)定的。堆排序的部分處理過程如圖9.11所示。 9.5 歸并排序 歸并排序(merge sort)是一類與插入排序、交換排序、選擇排序不同的另一種排序方法。 歸并的含義是將兩個或兩個以上的有序表合并成一個新的有序表。 歸并排序有多路歸并排序和兩路歸并排序； 可用于內(nèi)排序, 也可以用于外排序。 這里僅對內(nèi)排序的兩路歸并方法進行討論。 兩路歸并排序算法思路: （1）把n個記錄看成n個長度為l的有序子表; （2）進行兩兩歸并

32、使記錄關(guān)鍵字有序, 得到n/2個長度為2的有序子表; （3） 重復(fù)第（2）步， 直到所有記錄歸并成一個長度為n的有序表為止。 例9.7 HT有一組關(guān)鍵字4,7,5,3,2,8,6,1, n=8, 將其按由小到大的順序排序。 兩路歸并排序操作過程如9.12所示, 其中l(wèi)為子表長度。 初始4 7 5 3 2 8 6 1 l=1第 1 趟4 7 3 2 1 l=2第 2 趟3 4 5 7 1 2 6 8 l=4第 1 趟1 2 3 4 5 6 7 8 l=n 算法實現(xiàn): 此算法的實現(xiàn)不像圖示那樣簡單, 現(xiàn)分三步來討論。 首先從宏觀上分析, 先讓子表表長l=1進行處理; 不斷地使l=2*L, 進行子表

33、處理, 直到l=n為止, 把這一過程寫成一個主體框架函數(shù)mergesort。 然后對于某確定的子表表長l, 將n個記錄分成若干組子表, 兩兩歸并, 這里顯然要循環(huán)若干次, 把這一步寫成一個函數(shù)mergepass, 可由mergesort調(diào)用。 最后再看每一組（一對）子表的歸并, 其原理是相同的, 只是子表表長不同。換句話說, 是子表的首記錄號與尾記錄號不同, 把這個歸并操作作為核心算法寫成函數(shù)merge, 由mergepass來調(diào)用。 主體框架算法描述如下: 算法 9.11 void mergesort(struct node rMAXSIZE,int n) /*r是包含有n個記錄的原文件,

34、歸并過程中另需一個r2作為輔助存儲空間*/ l=1; /*子表初始長度*/ while (l=2*l) /*剩下的記錄數(shù)目大于兩個子表時*/ h1=i; mid=h1+l-1;h2=i+2*l-1; merge(r,r2,h1,mid,h2);i=i+2*l; /*跳過兩個子表, 指向新的一對子表的首記錄*/ if (n-i+1)=l) /*剩下的記錄數(shù)目小于一個子表時*/for (j=i;j=n;j+) r2j=rj;else /*剩下的記錄數(shù)目大于一個, 小于兩個子表時*/ h1=i;mid=h1+l-1;h2=n; merge(r,r2,h1,mid,h2); /* mergesort*

35、/歸并排序核心算法描述如下: 算法 9.13oid merge(struct node rMAXSIZE,struct node r2MAXSIZE,int h1,int mid,int h2 ) /*h1為第一個子表首元素的下標(biāo), mid 為第一個子表未元素的下標(biāo), */ /* h2為第二個子表未元素的下標(biāo) */ i=h1;j=mid+1;k=h1-1; /* k是r2的初始指針*/ while (i=mid) & (j=h2) k=k+1; if (ri.key=rj.key) r2k=ri;i+; else r2k=rj;j+; while (i=mid) k+;r2k=ri;i+;wh

36、ile (j=h2) k+;r2=rj;j+; /* merge*/ 算法的最后兩個while語句也可以改寫成: if (i=mid) for(t=i;t=mid;t+) k+;r2k=rt;else for(t=j;t=h2;t+) k+;r2k=rt; 9.6 基數(shù)排序 基數(shù)排序(radix sort)是與前面所介紹的各類排序方法完全不同的一種排序方法。 前幾節(jié)所介紹的排序方法主要是通過比較記錄的關(guān)鍵字來實現(xiàn)的, 而基數(shù)排序法不必經(jīng)過關(guān)鍵字的比較來實現(xiàn)排序, 而是根據(jù)關(guān)鍵字每個位上的有效數(shù)字的值, 借助于“分配”和“收集”兩種操作來實現(xiàn)排序的。 本章假設(shè)記錄的關(guān)鍵字為整型（實質(zhì)上關(guān)鍵字并不

37、限于整型）。 基數(shù)排序有兩種方法: 一種方法是首先根據(jù)最高位有效數(shù)字進行排序, 然后根據(jù)次高位有效數(shù)字進行排序, 依次類推, 直到根據(jù)最低位（個位）有效數(shù)字進行排序, 產(chǎn)生一個有序序列。這種方法稱最高位優(yōu)先法(Most Significant Digit First), 簡稱MSD法。 另一方法是首先根據(jù)關(guān)鍵字最低位（個位）有效數(shù)字進行排序, 然后根據(jù)次低位（十位）有效數(shù)字進行排序, 依次類推, 直到根據(jù)最高位有效數(shù)字進行排序, 產(chǎn)生一個有序序列。 這種方法稱最低位優(yōu)先法(Least Significant Digit First), 簡稱LSD法。 現(xiàn)用LSD法進行基數(shù)排序。假設(shè)有n個記錄,

38、 其關(guān)鍵字在0999之間, 每一位上有效數(shù)字值在09之間共10種可能性, 則認為基數(shù)是10, 在進行“分配”操作時涉及10個隊列, 即隊列的個數(shù)與基數(shù)相同。 此處關(guān)鍵字最多位數(shù)是3, 那么就需進行3趟“分配”和“收集”操作。 算法思路: 1） 第一趟“分配”, 根據(jù)關(guān)鍵字個位有效數(shù)字, 把所有記錄分配到相應(yīng)的10個隊列中去。 用f0, e0表示 0 號隊列的頭、 尾指針, f9, e9表示9號隊列的頭、 尾指針。 例如, 關(guān)鍵字為184的記錄就分配到4號隊列中去。 （2）第一趟“收集”把所有非空隊列（10個隊列中可能有空隊）按隊列號由小到大的順序頭、尾相接, 收集成一個新的序列。此序列若觀察其

39、關(guān)鍵字的個位, 則它是有序的; 若觀察其關(guān)鍵字的高位, 則它尚處于無序狀態(tài)。 （3）以后各趟分別根據(jù)關(guān)鍵字的十位、 百位有效數(shù)字重復(fù)第（1）、（2）步的“分配”與“收集”操作, 最終得到一個按關(guān)鍵字由小到大的序列。 例9.8 有一組關(guān)鍵字278,109,063,930,589,184,505,269,008,083, 將它們按由小到大的順序排序。 圖9.13(a)是待排序的關(guān)鍵字序列的初始狀態(tài)。 圖9.13(b)是按每個關(guān)鍵字的個位有效數(shù)字將它們分配到相應(yīng)的隊列中去。 例如, 關(guān)鍵字008、278都分配到了8號隊列中去, e8指向隊尾, f8指向隊頭。 圖9.13(c)是將6個非空隊列（0號,

40、 3號, 4號, 5號, 8號, 9號）頭尾相接收集在一起之后得到的一個新的序列。 圖9.13(d)是按每個關(guān)鍵字十位上的有效數(shù)字重新將它們分配到相應(yīng)的隊列中去, 例如, 關(guān)鍵字589、 184、 083都分配到了8號隊列中去。然后再次收集, 形成如圖9.13(e)所示的新的序列。 圖9.13(f)則是按百位上的有效數(shù)字分配之后的各隊列狀態(tài)。 圖9.13(g)則是再次收集后的結(jié)果, 這也是基數(shù)排序所得到的最終的有序序列。 在本章前幾節(jié)的討論中, 待排序的記錄是用向量r做存儲結(jié)構(gòu)的。 基數(shù)排序又是“分配”隊列, 又要“收集”起來, 故適用于鏈表形式存儲。 本節(jié)不采用動態(tài)鏈表而仍用向量r存儲（即一

41、維數(shù)組）, 讓每個存放記錄的數(shù)組元素增加一個指針域。此域為整型, 用來存放該 記錄的下一個相鄰記錄所在數(shù)組元素的下標(biāo)。 這種結(jié)構(gòu)稱為靜態(tài)鏈表結(jié)構(gòu)。所謂隊列的頭、尾指針也是整型, 它們記下可做某號隊列隊頭或隊尾元素的記錄在數(shù)組r中的下標(biāo)值。 記錄結(jié)構(gòu)為: struct node int key; /*關(guān)鍵字域*/ int oth; /*其它信息域*/ int point; /*指針域*/ 基數(shù)排序算法: 設(shè)n個待排序的記錄存儲在向量r中, 限定關(guān)鍵字為整型并且有效數(shù)字位數(shù)d5; 基數(shù)顯然是10; 10個隊列的頭指針、 尾指針分別用向量f和e來表示, 代表頭指針的數(shù)組元素是f0, f1, , f9

42、, 代表尾指針的數(shù)組元素分別是e0, e1, e2, , e9, 則算法描述如下: 算法 9.14 int radixsort(struct node rMAXSIZE,int n) int f10,e10; for (i=1;in;i+) ri.point=i+1; rn.point=0;p=1; /*建立靜態(tài)鏈表, p指向鏈表的第一個元素for (i=1;i=d;i+) /*下面是分配隊列*/ for (j=0;j10;j+) fj=0;ej=0;while (p!KG-*2=0) k=yx(rp.key,i); /*取關(guān)鍵字倒數(shù)第i位有效數(shù)字*if (fk=0) fk=p; ek=p;

43、*讓頭指針指向同一元素*else l=ek;rl.point=p; ek=p; *在k號隊列尾部入隊* p=rp.point; *在r向量中, p指針向后移* *下面是收集* j=0; while (fj=0) j+; /*找第一個非空隊列* p=fj; t=ej; *p記下隊頭做收集后的靜態(tài)鏈表頭指針* while (j10) j+; while (j10) & (fj=0) j+; if (fj!KG-*2=0) rt.point=fj; t=ej; *將前邊一個非空隊列的隊尾指針指向現(xiàn)在隊頭并記下現(xiàn)在隊尾位置*rt.point=0; *這是一趟分配與收集之后的鏈表最后一個元素* /* f

44、or i */ return(p); /*基數(shù)排序結(jié)果p指向靜態(tài)鏈表的第一個元素, 即關(guān)鍵字最小的記錄* /*radixsort*/分離關(guān)鍵字倒數(shù)第i位有效數(shù)字算法: 算法 9.15int yx(int m,int i) switch () case 1:x=m%10; /*個位* case 2:x=(m%100)/10; *十位* case 3:x=(m%1000)/100; *百位* case 4:x=(m%10000)/1000; *千位* return(x); /*yx*/ radixsort算法中基數(shù)為10, 這里用rd表示它, 最高有效數(shù)字位是4, 這里用d表示, 記錄總數(shù)為n。

45、基數(shù)排序時間復(fù)雜度為O(d(n+rd), 這是因為總共循環(huán)d趟, 每趟分配運算量數(shù)量級為O(n), 收集運算量數(shù)量級為O(rd), 所以總時間復(fù)雜度為O(d(n+rd)。 它的空間占用情況是, 向量r多了n個指針域, 輔助空間為2rd個隊列指針。 基數(shù)排序是穩(wěn)定的。 .7 內(nèi)部排序總結(jié) 表9.1列出了8種排序方法的性能比較。 （） 當(dāng)問題的規(guī)模不大, 即待排序的記錄數(shù)n不大時(n=50), 可選用表中前三種排序方法之一。它們的時間復(fù)雜度雖為O(n2), 但方法簡單易掌握。 直接插入排序和冒泡排序在原文件記錄按關(guān)鍵字“基本有序”時, 排序速度比較快。其中直接插入排序更為常用。 （）當(dāng)n值很大,

46、并不強求排序穩(wěn)定性, 并且內(nèi)存容量不寬余時, 應(yīng)該選用快速排序或堆排序。一般來講, 它們排序速度非?？?。但快速排序?qū)υ蛄谢居行虻那闆r, 速度減慢接近O(n2),而堆排序不會出現(xiàn)最壞情況。 （） 當(dāng)n值很大, 對排序穩(wěn)定性有要求, 存儲容量較寬余時, 用歸并排序最為合適。 排序速度很快, 并且穩(wěn)定性好。 （） 當(dāng)n值很大并且關(guān)鍵字位數(shù)較小時, 采用靜態(tài)鏈表基數(shù)排序不僅速度較快, 并且穩(wěn)定性好。 9.8 有關(guān)排序算法的C語言源程序 本章介紹了多種算法, 其中直接插入排序、 折半插入排序、 冒泡排序和簡單選擇排序的程序在各種程序設(shè)計語言中都有詳細的介紹。 這里我們提供希爾排序、 快速排序、 堆排

47、序、 歸并排序和基數(shù)排序的程序清單（均已上機通過）, 供大家在消化算法和實驗時參考。 struct node /*記錄結(jié)構(gòu)。 為簡化問題, 設(shè)定記錄中只含關(guān)鍵字* int key; r20;main( ) oid print(struct node a20,int n); int creat( ); oid shell(struct node a20,int n); int hoare(struct node a20,int l,int h); oid quick1(struct node a20,int n); oid quick2(struct node a20,int l,int h);

48、 oid heap(struct node a20,int i,int m); oid heapsort(struct node a20,int n); oid merge(struct node a20,struct node a220,int h1,int mid,int h2);oid mergepass(struct node a20,struct node a220,int l,int n); oid mergesort(struct node a20,int n); int yx(int m,int i); int radixsort(struct rnode a20,int n)

49、; int num,l,h,c; struct rnode s20;c=1; while (c!KG-*2=0) printf( 主菜單); printf(1. 輸入關(guān)鍵字, 以-9999表示結(jié)束。 n); printf(2. 希爾排序n); printf(3. 非遞歸的快速排序n); printf(4. 遞歸的快速排序n); printf(5. 堆排序n); printf(6. 歸并排序n); printf(7. 基數(shù)排序n); printf(輸入選擇 (1-7,0 表示結(jié)束):); scanf(%d,&c); switch(c) case 1:num=creat();print(r,num

50、);break; case 2:shell(r,num);print(r,num);break; case 3:quick1(r,num);print(r,num);break; case 4:l=0;h=num-1;quick2(r,l,h); printf(output quick2sort result:n); print(r,num);break; case 5:heapsort(r,num);break; case 6:mergesort(r,num);print(r,num);break; case 7:radixsort(s,num); /*main end*/ oid prin

51、 t(struct node a20,int n)*打印記錄* int i; for (i=0;i=1;i-) ai.key=ai-1.key; k=n/2; while (k=1) for (i=k+1;ia0.key) & (j=0) aj+k.key=aj.key;j=j-k; aj+k=a0; k=k/2; for (i=0;in;i+) ai.key=ai+1.key; printf(輸出希爾排序的結(jié)果:n); *shell end*int hoare(struct node a20,int l,int h)*分區(qū)處理函數(shù)* int i,j; struct node x; i=l;j

52、=h;x.key=ai.key; do while(i=x.key) j-; if(ij) ai.key=aj.key;i+; while(ij) & (ai.key=x.key) i+; if (ij) aj.key=ai.key;j-; while (ij); ai.key=x.key;return(i); *hoare end*oid quick1(struct node a20,int n)*非遞歸的快速排序主體函數(shù)* int i,l,h,tag,top; int s202; l=0;h=n-1;tag=1;top=0; do while (lh) i=hoare(a,l,h); to

53、p+;stop0=i+1; stop1=h;h=h-1; if(top=0) tag=0; else l=stop0; h=stop1;top-; while (tag=1);printf(輸出非遞歸快速排序的結(jié)果:n); *quick1 end*oid quick2(struct node a20,int l,int h)*遞歸的快速排序主體函數(shù) int i; if(lh) i=hoare(a,l,h); quick2(a,l,i-1); quick2(a,i+1,h); *quick2 end*oid heap(struct node a20,int i,int m)*調(diào)整堆的函數(shù)* st

54、ruct node x; int j; x.key=ai.key;j=2*i; while (j=m) if (jaj+1.key) j+; if (aj.key0;i-) ai.key=ai-1.key; for (i=n/2;i=1;i-) heap(a,i,n); printf(輸出歸并排序的結(jié)果:n); for(=n;=2;-) printf(%5d,a1.key); x.key=a1.key;a1.key=a.key; a.key=x.key; heap(a,1,-1); printf(%5d,a1.key); for (i=0;in;i+) ai.key=ai+1.key; *he

55、apsort end*oid merge(struct node a20,struct node a220,int h1,int mid,int h2)*歸并排序的核心算法* int i,j,k; i=h1;j=mid+1;k=h1-1; while (i=mid) & (j=h2) k=k+1; if (ai.key=aj.key) a2k.key=ai.key;i+; else a2k.key=aj.key;j+; while (i=mid) k+;a2k.key=ai.key;i+; while (j=2*l) h1=i;mid=h1+l-1;h2=i+2*l-1; merge(a,a2

56、,h1,mid,h2); i=i+2*l; if (n-i)=l) for (j=i;j=n;j+) a2j.key=aj.key; else h1=i;mid=h1+l-1;h2=n-1; merge(a,a2,h1,mid,h2); *mergepass end*oid mergesort(struct node a20,int n)*歸并排序的主體函數(shù) int l; struct node a220; l=1; while (ln) mergepass(a,a2,l,n);l=2*l; mergepass(a2,a,l,n);l=2*l; printf(輸出歸并排序的結(jié)果:n); *me

57、rgesort end*int yx(int m,int i)*分離關(guān)鍵字倒數(shù)第i位有效數(shù)字的算法* int x; switch(i) case 1:x=m%10; break; case 2:x=(m%100)/10;break; case 3:x=(m%1000)/100;break; case 4:x=(m%10000)/1000; return(x); /*yx end*struct rnode /*基數(shù)歸并時記錄的結(jié)構(gòu)* int key; int point; ;int radixsort(struct rnode a20,int n) *基數(shù)排序* int f11,e11,i,j,k,l,p,d,t; for (i=1;i=n;i+) ai.key=ri-1.key; ai.point=i+1; an.point=0;p=1;printf(輸入關(guān)鍵字有效位數(shù)dn); scanf(%d,&d);printf(輸出基數(shù)排序的結(jié)果:n); for(i=1;i=d;i+) for(j=0;j=10;j+) fj=0;ej=0; while (p!KG-*2=0) k=yx(ap.