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

1、基本概念插入排序交換排序選擇排序基數(shù)排序內(nèi)部排序比較外排序 第91關(guān)鍵字 假設(shè)被排序的對象是由一組記錄組成的文件，記錄由若干個數(shù)據(jù)項(或域)組成，其中有一項可用來標識一個記錄，稱為關(guān)鍵字項。該數(shù)據(jù)項的值稱為關(guān)鍵字(Key)。在不易產(chǎn)生混淆時，本章中將關(guān)鍵字項簡稱為關(guān)鍵字。 排序 所謂排序（Sort），就是要整理文件中的記錄，使它們按關(guān)鍵字遞增(或遞減)次序重新排列。排序方法的穩(wěn)定性在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，則稱該排序方法是穩(wěn)定的；否則，若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱該排序方法是不穩(wěn)定的。9.1 排

2、序的基本概念2排序方法的分類 按是否涉及數(shù)據(jù)的內(nèi)、外存交換分類： 外排序、內(nèi)排序。 按策略劃分內(nèi)部排序方法： 插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序等。排序算法性能評價 評價排序算法好壞的標準主要有兩條：（1）執(zhí)行算法所需的時間； （2）執(zhí)行算法所需的輔助空間。 3不同存儲方式的排序過程以順序表作為存儲結(jié)構(gòu)： 對記錄本身進行物理重排。以鏈表作為存儲結(jié)構(gòu)： 無須移動記錄，僅需修改指針。用順序的方式存儲待排序的記錄，但同 時建立一個輔助表。 只需對輔助表的表目進行物理重排，適 用于難以在鏈表上實現(xiàn)，仍需避免排序 過程中移動記錄的排序方法。 4 若無特別說明，則所討論排序均為升序（即按遞增

3、排序），并以記錄數(shù)組作為文件的存儲結(jié)構(gòu)。同時假定關(guān)鍵字是整數(shù)。記錄數(shù)組的類型說明如下：typedef int KeyType； typedef struct KeyType key； InfoType otherinfo； RecType；typedef RecType SeqListn+1；59.2 插入排序 基本原理：每步將一個待排序的記錄，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組記錄適當(dāng)位置上，直到記錄全部插入為止。直接插入排序希爾排序69.2.1 直接插入排序 基本思想：假設(shè)待排序的記錄存放在數(shù)組R1.n中（ R1.n表示數(shù)組元素的范圍是從R1到Rn ）。初始時，i=1，R1自成一個

4、有序區(qū)，無序區(qū)為R2.n。然后，從i=2起直至i=n，依次將Ri插入當(dāng)前的有序區(qū)R1.i-1中，最后，生成含n個記錄的有序區(qū)。7例9.1 直接插入排序舉例初始關(guān)鍵字 49 38 65 97 76 13 27 49j=2 (38) 38 49 65 97 76 13 27 49j=3 (65) 38 49 65 97 76 13 27 49j=4 (97) 38 49 65 97 76 13 27 49j=5 (76) 38 49 65 76 97 13 27 49j=6 (13) 13 38 49 65 76 97 27 49j=7 (27) 13 27 38 49 65 76 97 49j=

5、8 (49) 13 27 38 49 49 65 76 97監(jiān)視哨R0圖9.1 直接插入排序過程示例8直接插入排序算法void lnsertSort(SeqList R) int i,j; for (i=2;in;i+) R0Ri; ji-1; while (R0.key=1）。 因此，我們把R0稱為“監(jiān)視哨”。10直接插入排序的算法分析直接插入排序算法由兩重循環(huán)組成，對于有n個記錄的排序，內(nèi)循環(huán)表明完成一趟排序所需進行的記錄關(guān)鍵字間的比較和記錄的后移。若初始時關(guān)鍵字遞增有序，這是最好情況。每一趟排序中僅需進行一次關(guān)鍵字的比較，所以總的比較次數(shù)為n-1。在while循環(huán)之前和之中，至少要移動記

6、錄兩次，所以總的比較次數(shù)為2(n-1)。若初始時關(guān)鍵字遞減有序，這是最壞情況。這時的記錄比較和移動次數(shù)分別為： 直接插入排序是一種穩(wěn)定的排序方法。119.2.2 希爾排序1959年由D.L. Shell提出，又稱縮小增量排序(Diminishing-increment sort) ?；舅枷耄涸谥苯硬迦肱判蛑?，只比較相鄰的結(jié)點，一次比較最多把結(jié)點移動一個位置。如果對位置間隔較大距離的結(jié)點進行比較，使得結(jié)點在比較以后能夠一次跨過較大的距離，這樣就可以提高排序的速度。12希爾排序的基本過程 設(shè)待排序的記錄序列有n個記錄，首先取一個整數(shù)d1 n作為間隔，將全部記錄分為d1個子序列，所有距離為d1的記

7、錄放在同一個序列中，在每一個子序列中分別施行直接插入排序，然后縮小間隔d2 ，如取d2 = d1 /2，重復(fù)上述的子序列劃分和排序工作，直到最后取dt= 1為止。13希爾排序示例初始關(guān)鍵字 49 38 65 97 76 13 27 49 55 04 （增量為5）一趟排序結(jié)果： 13 27 49 55 04 49 38 65 97 76 （增量為3）二趟排序結(jié)果： 13 04 49 38 27 49 55 65 97 76（增量為1）三趟排序結(jié)果： 04 13 27 38 49 49 55 65 76 97圖9.2 希爾排序過程示例14希爾排序算法void ShellPass(SeqList R

8、，int d) for(i=d+1；i=n；i+)if(Ri.key0&R0.key1)； 15 為什么shell排序的時間性能優(yōu)于直接插入排序呢？ 因為直接插入排序在初態(tài)為正序時所需時間最少，實際上，初態(tài)為基本有序時直接插入排序所需的比較和移動次數(shù)均較少。另一方面，當(dāng)n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度O(n2)差別不大。在shell排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但組內(nèi)元素已經(jīng)過多次排序，數(shù)組已經(jīng)比較接近有序狀態(tài)，所以新的一趟排序過程也較塊。

9、16希爾排序中增量di的取法Shell最初的方案是d1 = n/2, di+1 = di /2，直到dt =1。Knuth的方案是di+1 = di /3+1。其它方案有：都取奇數(shù)為好；或di互質(zhì)為好等等。17希爾排序的算法分析對希爾排序的復(fù)雜度的分析很困難，在特定情況下可以準確地估算關(guān)鍵字的比較和記錄移動次數(shù)，但是考慮到與增量之間的依賴關(guān)系，并要給出完整的數(shù)學(xué)分析，目前還做不到。Knuth的統(tǒng)計結(jié)論是，平均比較次數(shù)和記錄平均移動次數(shù)在n1.25 與1.6n1.25之間。希爾排序的穩(wěn)定性 希爾排序是一種不穩(wěn)定的排序方法。見前例，未排序前，25在25* 之前，希爾排序完成后， 25在25* 之后

10、，這就說明希爾排序是不穩(wěn)定的。189.3 交換排序兩種常見的交換排序冒泡排序快速排序基本原理：兩兩比較待排序的記錄的關(guān)鍵字，如果發(fā)生逆序，則交換之，直到全部記錄都排好序為止。199.3.1 冒泡排序 將被排序的記錄數(shù)組R1.n垂直排列，每個記錄Ri看作是重量為Ri.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上（也可以從上往下）掃描數(shù)組R，凡掃描到違反此原則的輕氣泡，就使其向上“飄浮”。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上、重者在下為止。 初始時R1.n為無序區(qū)。第一趟掃描從無序區(qū)底部向上依次比較相鄰的兩個氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(

11、Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)；對于每對氣泡(Rj+1，Rj)，若Rj+1.keyRj.key，則交換Rj+1和Rj的內(nèi)容。第一趟掃描完畢時，“最輕”的氣泡就飄浮到該區(qū)間的頂部，即關(guān)鍵字最小的記錄被放在最高位置R1上。第二趟掃描掃描R2.n。掃描完畢時，“次輕”的氣泡飄浮到R2的位置上。最后，經(jīng)過n-1趟掃描可得到有序區(qū)R1.n。冒泡排序的基本思想20例9.3 冒泡排序示例49 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 6

12、5 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97初始 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟 最終排序關(guān)鍵字 排序后 排序后 排序后 排序后 排序后 排序后, 結(jié)果 已無記錄交換， 冒泡排序終止！ 圖9.3 冒泡排序過程示例（由下向上比較）21冒泡排序算法void BubbleSort(SeqList R)int i，j，exchange；for(i=1;i=i；j-) if(Rj+1.keyRj.key) R0=Rj+1； Rj+1=Rj； Rj=R0； exch

13、ange=1； if(!exchange) break； 22冒泡排序的算法分析考慮關(guān)鍵字的比較次數(shù)和記錄移動次數(shù)在最好情況下，初始狀態(tài)是遞增有序的，一趟掃描就可完成排序，關(guān)鍵字的比較次數(shù)為n-1，沒有記錄移動。若初始狀態(tài)是反序的，則需要進行n-1趟掃描，每趟掃描要進行n-i次關(guān)鍵字的比較，且每次需要移動記錄三次，因此，最大比較次數(shù)和移動次數(shù)分別為： 冒泡排序方法是穩(wěn)定的。23快速排序的基本思想快速排序方法是一種所需比較次數(shù)較少、在內(nèi)部排序中速度比較快的排序方法。其思想是在待排序的記錄序列中任取某個記錄（作為基準）的值作為控制值，采用某種方法把這個記錄放到適當(dāng)?shù)奈恢?，使得這個位置的左邊的所有記

14、錄的值都小于或等于這個控制值，而這個位置的右邊的所有記錄的值都大于或等于這個控制值。9.3.2 快速排序24例9.4 (a) 一趟快速排序示例（一次劃分過程）49386597761327493865977613274927386597761349273897761365492738139776654927381376976549273813 49 76 49 654949pivotiiiiiiijjjjjjj25例9.4 (b) 各趟排序后的狀態(tài)493865977613274927 3813497697654913273849496576 971327 38 49496576971327384

15、94965 7697初始關(guān)鍵字一趟排序之后二趟排序之后三趟排序之后排序結(jié)果圖中，粉紅色關(guān)鍵字表示基準關(guān)鍵字pivot.key。 方括號 表示劃分后的區(qū)間。26快速排序算法void QuickSort(SeqList R，int low，int high) int pivotpos； if(lowhigh) pivotpos=Partition(R，low，high)； QuickSort(R，low，pivotpos-1)； QuickSort(R，pivotpos+1，high)； 27劃分算法int Partition(SeqList R，int i，int j)ReceType pivo

16、t=Ri； while(ij) while(i=pivot.key) j-； if(ij) Ri+=Rj； while(ij&Ri.key=pivot.key) i+； if(ij) Rj-=Ri; /endwhile Ri=pivot； return i； 28快速排序的算法分析最好情況是每次所取的基準都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準的左右兩個無序子區(qū)的長度大致相等。考慮關(guān)鍵字的比較次數(shù)和記錄移動次數(shù)最壞情況是每次劃分選取的基準都是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的結(jié)果是基準的左邊（或右邊）為空，劃分前后無序區(qū)的元素個數(shù)減少一個，因此，排序必須做n-1趟，每一趟中需

17、做n-i次比較，所以最大比較次數(shù)為29 快速排序的記錄移動次數(shù)不會大于比較次數(shù)，所以，快速排序的最壞時間復(fù)雜度為O(n2)；最好時間復(fù)雜度為O(nlog2n)。 快速排序的平均時間復(fù)雜度也是(nlog2n)，空間復(fù)雜度為O(log2n)。 快速排序是不穩(wěn)定的排序方法。例如：初始關(guān)鍵字 2 2* 1 一趟排序后 1 2* 2二趟排序后 1 2* 2 排序結(jié)果 1 2* 2309.4 選擇排序兩種常見的選擇排序直接選擇排序堆排序基本思想: 將待排序的記錄分為已排序(初始為空)和未排序兩組，依次將未排序的記錄中關(guān)鍵字值最小的記錄放入已排序的記錄組的最后，直到記錄直到排序完畢為止。31直接選擇排序的基

18、本思想(1)在一組記錄Ri到Rn中選擇具有最小關(guān)鍵字的記錄。(2)若它不是這組記錄中的第一個記錄，則將它與這組記錄中的第一個記錄對調(diào)。(3) 除去這個最小關(guān)鍵字的記錄，在剩下的記錄中重復(fù)(1)、(2)步，直到剩余記錄只有一個為止。9.4.1 直接選擇排序3249386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697例9.5 直接選擇排序過程示例初始關(guān)鍵字第一趟排序后第二趟排序后第三趟排序后第四趟排序

19、后第五趟排序后第六趟排序后 第七趟排序后得最后排序結(jié)果33直接選擇排序算法void SelectSort(SeqList R) int i，j，k； for(i=1;in;i+) k=i； for(j=i+1;j=n;j+) if(Rj.key1；i-) R0=R1；R1=Ri；Ri=R0； /*將堆頂和堆中最后一個記錄交換*/ Heapify(R，1，i-1)； /*調(diào)整堆函數(shù),將R1.i-1重新調(diào)整為堆*/ 42調(diào)整堆函數(shù)Heapify( )的實現(xiàn)每趟排序開始前Rl.i是以R1為根的堆，在R1與Ri交換后，新的無序區(qū)R1.i-1中只有R1的值發(fā)生了變化，故除R1可能違反堆性質(zhì)外，其余任何結(jié)

20、點為根的子樹均是堆。因此，當(dāng)被調(diào)整區(qū)間是Rlow.high時，只須調(diào)整以Rlow為根的樹即可。Rlow的左、右子樹(若存在)均已是堆，這兩棵子樹的根R2low和R2low+1分別是各自子樹中關(guān)鍵字最大的結(jié)點。若Rlow.key不小于這兩個孩子結(jié)點的關(guān)鍵字，則Rlow未違反堆性質(zhì)，以Rlow為根的樹已是堆，無須調(diào)整；否則必須將Rlow和它的兩個孩子結(jié)點中關(guān)鍵字較大者進行交換，即：交換Rlow與Rlarge(Rlarge.key=max(R2low.key，R2low+1.key) 。交換后又可能使結(jié)點Rlarge違反堆性質(zhì)，同樣由于該結(jié)點的兩棵子樹(若存在)仍然是堆，故可重復(fù)上述的調(diào)整過程，對以

21、Rlarge為根的樹進行調(diào)整。此過程直至當(dāng)前被調(diào)整的結(jié)點已滿足堆性質(zhì)，或者該結(jié)點已是葉子為止。上述過程就象過篩子一樣，把較小的關(guān)鍵字逐層篩下去，而將較大的關(guān)鍵字逐層選上來。因此，有人將此方法稱為“篩選法”。43算法9.8 調(diào)整堆函數(shù)（用篩選法調(diào)整堆）。void Heapify(SeqList R,int k,int m)/*假設(shè)Rk.m是以Rk為根的完全二叉樹,且分別以R2k和R2k+1為根的左、右子樹*/ /*為大根堆,調(diào)整Rk,使整個序列Rk.m滿足堆的性質(zhì)*/ RecType t=rk；/*暫存“根”結(jié)點Rk*/ x=rk.key； i=k； j=2*i； while(j=m) /*jm

22、,Rj是Ri的左孩子 */ if(jm) & (Rj.key Rj+1.key) j=j+1; /*若存在右子樹，且右子樹根的關(guān)鍵字大，則沿右分支“篩選”*/ if(x=1;i-) Heapify(R,i,n); /*調(diào)整堆函數(shù)*/46例9.8 用篩選法建新堆示例。 已知關(guān)鍵字序列為 42，13，91，23， 24， 16，05，88，要求建立大根堆。因n=8，故從第4個結(jié)點開始調(diào)整。42139123241605884213912324160588(a) i=4，23篩下一層4742139188241605234213918824160523(b) i=3，不調(diào)整484213918824160

23、5234213918824160523(c) i=2，13篩下兩層4942889123241605134288912324160513(d) i=1，42篩下一層5091884223241605139188422324160513(e) 建成的大根堆51 建成大根堆后，將堆頂記錄R1與最后一個記錄Rn交換，就得到第一趟排序的結(jié)果；然后將剩余記錄R1. n-1重新調(diào)整為堆，再將堆頂記錄R1與最后一個記錄Rn-1交換，就得到第二趟排序的結(jié)果； 如此重復(fù)n-1趟排序之后，就使有序區(qū)擴充到整個記錄區(qū)R1到Rn。 請參見下例堆排序的全過程示例。529188422324160513918842232416

24、0513（a）初始堆R1到R8堆排序的全過程示例5313884223241605911388422324160591（b）第一趟排序之后54（c）重建的堆R1到R7882442231316059188244223131605915505244223131688910524422313168891（d）第二趟排序之后56（e）重建的堆R1到R64224162313058891422416231305889157（f）第三趟排序之后0524162313428891052416231342889158（g）重建的堆R1到R52423160513428891242316051342889159（h）第

25、四趟排序之后1323160524428891132316052442889160（i）重建的堆R1到R42313160524428891231316052442889161（j）第五趟排序之后0513162324428891051316232442889162（k）重建的堆R1到R31613052324428891161305232442889163（l）第六趟排序之后0513162324428891051316232442889164（m）重建的堆R1到R21305162324428891130516232442889165（n）第七趟排序之后，整個記錄區(qū)已經(jīng)有序,堆排序到此結(jié)束。05131

26、62324428891051316232442889166堆排序的算法分析堆排序的時間復(fù)雜度為O(n log2n)。堆排序的空間復(fù)雜度為 O(1)。堆排序是不穩(wěn)定的排序方法。由于建立初始堆所需要的比較次數(shù)較多，因此堆排序不適宜記錄數(shù)較少的文件。679.5 歸并排序歸并排序的基本思想是：將一些有序的子序列進行歸并，從而得到有序的序列。 所謂歸并，是指將若干個已排好序的子序列合并成一個有序的序列。歸并是一種常見運算，其方法是：比較各子序列的第一個記錄的鍵值，最小的一個就是排序后序列的第一個記錄的鍵值。取出這個記錄，繼續(xù)比較各子序列現(xiàn)在的第一個記錄的鍵值，便可找出排序后的第二記錄。如此繼續(xù)下去，最終

27、可以得到排序結(jié)果。因此，歸并排序的基礎(chǔ)是歸并。68二路歸并的基本思想 設(shè)兩個有序的子文件放在同一向量中相鄰的位置上：Rlow.m，Rm+1.high，先將它們合并到一個局部的暫存向量R1中，待合并完成后將R1復(fù)制回Rlow.high中。 合并過程中，設(shè)置i，j和p三個指針，其初值分別指向這三個記錄區(qū)的起始位置。合并時依次比較Ri和Rj的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到R1p中，然后將被復(fù)制記錄的指針i或j加1，并將指向復(fù)制位置的指針p加1。 重復(fù)這一過程直至兩個輸入的子文件有一個已全部復(fù)制完畢(不妨稱其為空)，此時將另一非空的子文件中剩余記錄依次復(fù)制到R1中即可。69二路歸并的示例25 57

28、48 37 12 92 86 25 57 37 48 92 12 86 25 37 48 57 12 86 92 12 25 37 48 57 86 92 70算法9.10 歸并算法void Merge(SeqList R，int low，int m，int high)/*將兩個有序的子文件Rlow.m和Rm+1.high歸并成一個有序的子文件Rlow.high */int i=low，j=m+1，p=0；RecType *R1；R1=(RecType *)malloc(high-low+1)*sizeof(RecType)；if(! R1) printf(“空間不足!);return ERR

29、OR;while(i=m&j=high) R1p+=(Ri.key=Rj.key)?Ri+：Rj+)；while(i=m) R1p+=Ri+；while(j=high) R1p+=Rj+；for(p=0，i=low；i=high；p+，i+) Ri=R1p；return OK;71 二路歸并的基本思想是：第1趟歸并排序時，將待排序的文件R1.n看作是n個長度為1的有序子文件，將這些子文件兩兩歸并，若n為偶數(shù)，則得到 個長度為2的有序子文件；若n為奇數(shù)，則最后一個子文件輪空(不參與歸并)。故本趟歸并完成后，前個有序子文件長度為2，但最后一個子文件長度仍為1；第2趟歸并則是將第1趟歸并所得到的 個

30、有序的子文件兩兩歸并，如此反復(fù)，直到最后得到一個長度為n的有序文件為止。 上述每次的歸并操作，都是將兩個子序列歸并為一個子序列，這就是“二路歸并”，類似地還可以有“三路歸并”或“多路歸并”。72歸并過程示例(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)73算法9.11 一趟歸并算法void MergePass(SeqList R，int length) int i； for(i=1;i+2*length-1=n;i=i+2*l

31、ength) Merge(R，i，i+length-1，i+2*length-1)； if(i+length-1n) Merge(R，i，i+length-1，n)； 算法9.12 二路歸并排序算法void MergeSort(SeqList R) int length； for(1ength=1；lengthn；length*=2) MergePass(R，length)；74歸并排序的算法分析 歸并排序是穩(wěn)定的排序方法。 歸并排序在第i 趟歸并后，有序子文件長度為2i，因此，對于具有n個記錄的文件來說，必須做 趟歸并，每趟歸并所花的時間為O(n)，所以，二路歸并排序算法的時間復(fù)雜度為O(n

32、log2n)。 算法中輔助數(shù)組R1所需的空間為O(n)。（見算法9.10 ）759.6 基數(shù)排序前面介紹的各種排序方法都是根據(jù)關(guān)鍵字值的大小來進行排序的。本節(jié)介紹的基數(shù)排序是一種借助于多關(guān)鍵字排序的思想對單個邏輯關(guān)鍵字進行排序的方法。 基數(shù)排序的基本思想：采用“分配”和“收集”兩種操作，對單邏輯關(guān)鍵字進行排序的一種方法。769.6.1 多關(guān)鍵字的排序?qū)淇伺频呐判蛎繌垞淇伺朴袃蓚€“關(guān)鍵字”：花色和面值，且“花色”地位高于“面值”?？梢韵劝础盎ㄉ迸判颍ǚ殖?堆），再按“面值”整理排序。也可以先按“面值”排序（分成13堆），再按“花色”整理排序。這兩種整理撲克牌的方法就是兩種多關(guān)鍵字的排序方法。

33、具體例子如下：779.6.2 鏈式基數(shù)排序基數(shù)排序是利用“分配”和“收集”兩種操作對單關(guān)鍵字進行排序一種內(nèi)部排序方法?；鶖?shù)排序的排序過程：設(shè)關(guān)鍵字共有d位，分別令j= d-1, d-2,.,0, 依次執(zhí)行d次“分配”與“收集”。78179208306093859984055009271033B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 271093033984055306208179859009(a) 初始關(guān)鍵字狀態(tài)(b) 第一趟分配之后，按

34、最低位關(guān)鍵字（個位數(shù)字）分配圖9.11 鏈式基數(shù)排序示例79271033093984055306208009859179B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 033984009208306859055179271093圖9.11 鏈式基數(shù)排序示例（續(xù)1）(c) 第一趟收集之后(d) 第二趟分配之后，按次低位關(guān)鍵字（十位數(shù)字）分配80306208009033055859271179984093B0.f B1.f B2.f B3.f B4

35、.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 179306984859093055033009271208009033055093179208271306859984(f) 第三趟分配之后，按最高位關(guān)鍵字（百位數(shù)字）分配(e) 第二趟收集之后(g) 第三趟收集之后，得到有序的序列圖9.11 鏈式基數(shù)排序示例（續(xù)2）81算法的靜態(tài)鏈表類型定義#define RADIX 10 /*關(guān)鍵字基數(shù)*/#define KEY_SIZE 6 /*關(guān)鍵字項數(shù)的最大值*/#define LIST_SIZ

36、E 1000 /*靜態(tài)鏈表的最大空間*/ typedef int KeyType；typedef struct KeyType keysKEY_SIZE；/*子關(guān)鍵字數(shù)組*/ OtherType other_data； /*其它數(shù)據(jù)項*/ int next； /*靜態(tài)鏈域*/ RecordType1； /*靜態(tài)鏈表的結(jié)點類型*/ typedef struct RecordType1 rLIST_SIZE+1；/* r0為頭結(jié)點*/ int length； /*靜態(tài)鏈表的當(dāng)前長度*/ int keynum； /*記錄的當(dāng)前關(guān)鍵字個數(shù)*/ SlinkList； /*靜態(tài)鏈表類型*/ typedef int PVectorRADIX； /*指針數(shù)組類型*/ 82算法9.14 分配算法void Distribute(RecordType1 r,int i,PVector head,PVector tail)/* 記錄數(shù)組r中記錄已按低位關(guān)鍵字keyi+