[哲學]C語言第十章課件

1、第10章 內(nèi)部排序?qū)W習目的與要求：1.深刻理解排序的定義和各種排序方法的特點, 并能加以靈活應用;2.熟練掌握各種排序方法的執(zhí)行過程；3.熟練掌握各種排序方法的時間復雜度的分析方法，從“關鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能;4.理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的?；緝?nèi)容一、概述二、插入排序三、交換排序四、選擇排序五、歸并排序六、基數(shù)排序七、各種排序方法的比較一、概述1基本概念排序：將數(shù)據(jù)元素(或記錄)的一個任意序列,重新排列成一個按關鍵字有序的序列。排序方法的穩(wěn)定性：對關鍵字相同的數(shù)據(jù)元素，排序前后它們的領先關系

2、保持不變，則稱該排序方法是穩(wěn)定的；反之，稱該排序方法是不穩(wěn)定的。內(nèi)部排序：待排序記錄存放在計算機的內(nèi)存中進行的排序。外部排序：待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序。排序的時間開銷：排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。算法運行時間代價的估算一般都按平均情況進行估算。對于那些受記錄關鍵字序列初始排列及記錄個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。2排序的分類按排序過程依據(jù)的不同原則進行分類：交換排序選擇排序歸并排序計數(shù)排序插入排序按工作量進行分類：先進的排序方法，其時

3、間復雜度為O(nlog2n)簡單的排序方法,其時間復雜度為O(n2)基數(shù)排序基數(shù)排序，其時間復雜度為O(dn)3排序的基本操作和記錄的存儲方式排序過程中需要的兩種基本操作：（1）比較關鍵字的大小；（2）將記錄從一個位置移至另一個位置。待排序記錄序列可有下列三種存儲方式：（1）記錄存放在一組連續(xù)的存儲單元中；類似于線性表的順序存儲結構，記錄次序由存儲位置決定，實現(xiàn)排序需移動記錄。（2）記錄存放在靜態(tài)鏈表中；記錄次序由指針指示，實現(xiàn)排序不需移動記錄，僅需修改指針。鏈排序（3）記錄本身存放在一組連續(xù)的存儲單元中，同時另設指示各個記錄存儲位置的地址向量，排序過程中不移動記錄本身，而移動地址向量中相應記

4、錄的地址。排序結束后再根據(jù)地址調(diào)整記錄的存儲位置。地址排序4待排序記錄的數(shù)據(jù)類型#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key; InfoType otherinfo;RcdType;typedef struct RedType rMAXSIZE+1; /0單元作為哨兵 int length;SqList;二、插入排序1直接插入排序2折半插入排序32-路插入排序4表插入排序5希爾排序插入排序的基本方法是：每步將一個待排序的記錄，按其關鍵字大小，插入到前面已經(jīng)排好序的一組記錄的適當位置上，直到記錄全部插入為止。1直

5、接插入排序基本思想： 當插入第i (i 1) 個記錄時，前面的r1, r2， ， ri-1已經(jīng)排好序。這時，用ri的關鍵字與ri-1， ri-2， 的關鍵字順序進行比較，找到插入位置即將ri插入，原來位置上之后的所有記錄依次向后順移。例49 38 65 97 76 13 27（ ）i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=7 (13 38 49

6、65 76 97 ) 27j9727j76j65j49j38j排序結果： (13 27 38 49 65 76 97)直接插入排序的算法void InsertSort(SqList &L) /對待排序序列L進行直接插入排序 for(i=2; i=L.length; +i) if ( LT(L.ri.key, L.ri-1.key) ) L.r0 = L.ri; / 復制為哨兵 for(j = i-1; L.r0.key L.rj.key; -j) L.rj+1 = L.rj; / 記錄后移 L.rj+1 = L.r0; /記錄插入 / InsertSort算法評價記錄的比較次數(shù)記錄的移動次數(shù)最

7、好情況最壞情況0時間復雜度：T(n)=O(n)結論：空間復雜度： S(n)=O(1)直接插入排序是一個穩(wěn)定的排序方法。2折半插入排序基本思想： 利用直接插入排序的思想，只是在排序過程中，為減少查找次數(shù)，對已排好序的序列 r1, r1, , ri-1 ，利用折半查找法尋找 ri 的插入位置。例 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20.i=7 6 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20lhmi=8 20 (6 13 30 39 42 70 85 ) 2

8、0lhmi=8 20 (6 13 30 39 42 70 85 ) 20l, m, hi=8 20 (6 13 30 39 42 70 85 ) 20lhi=8 20 (6 13 20 30 39 42 70 85 )算法描述如下：void Bin_InsertSort(SqList &L) /對待排序序列L進行折半插入排序 for(i=2; i=L.length; +i) low = 1; high = i-1; while(low=high) mid = (low+high)/2; if(r.mid.key h; j- ) L.rj+1 = L.rj; / 記錄后移 L.rj+1 = L.

9、r0; /記錄插入 / Bin_InsertSort算法分析折半插入排序減少了關鍵字間的比較次數(shù)（由O(n)下降到O(nlog2n)。折半插入排序的記錄移動次數(shù)仍為O(n) 。折半插入排序的時間復雜度仍為O(n) ，空間復雜度仍為O() 。折半插入排序是一個穩(wěn)定的排序方法。32-路插入排序基本思想：利用直接插入排序的思想，只是在排序過程中，為減少記錄的移動次數(shù)，但需要n個記錄的輔助空間。其做法是：另設一個和L.r同類型的數(shù)組d，首先將L.r1賦給d.r1，并將d.r1看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第二個記錄起依次到d.r1之前或之后的有序序列中。例 30 13 70

10、85 39 42 6 20排序過程中d的狀態(tài)變化如下：i=1 (30) firstfinali=2 (30) 13 firstfinal 30 13 70 85 39 42 6 20i=3 (30) 70 13 firstfinali=4 (30) 70 85 13 firstfinali=5 (30) 39 70 85 13 firstfinali=6 (30) 39 42 70 85 13 firstfinali=7 (30) 39 42 70 85 6 13 firstfinali=8 (30) 39 42 70 85 6 13 20firstfinal算法描述如下：void Two_I

11、nsertSort(SqList L，SqList &D ) /對待排序序列L進行2-路插入排序 D.r1 = L.r1; D.length = L.length; first = final = 1; for( i =2; i= L.length; i+ ) x = L.ri.key; if ( x D.r1.key ) if ( first = 1 ) D.rD.length = L.ri; first = D.length; else low = first; high = D.length; while( low = high ) mid = (low+high)/2; if( x D

12、.rmid.key ) high = mid -1; else low = mid+1; for(k = first; k = high+1; k+ ) D.rk-1 = D.rk; D.rhigh+1 = L.ri ; first-; else if (final = 1 ) final+; D.rfinal = L.ri; else low = 2; high = final; while( low = high ) mid = (low+high)/2; if( x = high+1; k+ ) D.rk+1 = D.rk; D.rhigh+1 = L.ri ; fianl+; /for

13、/Two_InsertSort算法分析2-路插入排序減少了關鍵字間的比較次數(shù)(小于nlog2n)。2-路插入排序減少了記錄移動次數(shù)，約為n2/8 。2-路插入排序的時間復雜度仍為O(n) ，但空間復雜度為O(n) 。2-路插入排序是一個穩(wěn)定的排序方法。4表插入排序表插入排序采用了靜態(tài)鏈表的存儲結構，其排序過程如下：首先將靜態(tài)鏈表中數(shù)組下標為1的分量（結點）和表頭結點構成一個循環(huán)鏈表，然后依次將下標為2至n的分量（結點）按記錄關鍵字非遞減有序插入到循環(huán)鏈表中。 表插入排序的基本操作仍是將一個記錄插入到已排好序的有序表中。和直接插入排序相比，不同之處僅是以修改2n次指針值代替移動記錄，排序過程中所

14、需進行的關鍵字間的比較次數(shù)相同。因此，表插入排序的時間復雜度仍是O(n2)。5希爾排序希爾排序方法又稱為“縮小增量”排序?；舅枷耄?先將整個待排序記錄序列分割成若干子序列分別進行直接插入排序，待整個序列“基本有序”時，再對全體記錄進行一次直接插入排序。例 初始：49 38 65 97 76 13 27 48 55 4取d1=5一趟分組：49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76取d2=3二趟分組：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97

15、76取d3=1三趟分組：13 4 48 38 27 49 55 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97希爾排序算法分析子序列的構成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列；希爾排序可提高排序速度，因為關鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序;增量序列取法有多種： 1) 沒有除1以外的公因子 2) 最后一個增量值必須為1時間復雜度是所取增量序列的函數(shù)，但至今沒人能夠給出完整的數(shù)學分析。希爾排序是一個不穩(wěn)定的排序方法。三、交換排序1起泡排序(Bubble Sort)2快速排序(Quick Sor

16、t)1起泡排序(Bubble Sort)基本過程： 1) 將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序r1.keyr2.key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止第一趟冒泡排序，結果關鍵字最大的記錄被安置在最后一個記錄上; 2) 對前n-1個記錄進行第二趟冒泡排序，結果使關鍵字次大的記錄被安置在第n-1個記錄位置; 3)重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止。例： 49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76

17、 13 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 97初始關鍵字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后算法分析時間復雜度最好情況（正序）最壞情況（逆序）比較次數(shù)移動次數(shù)n-10T(n)=O(n)空間復雜度：S(n)=O(1)起泡排序是一個穩(wěn)定的排序方法2快速排序(Quick Sort)對冒泡排序的一種改進基本思想： 通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)分別進行排序，以達到整個序列有序。排序過程：1) 初始時令i=s, j=t; 2)

18、 首先從j所指位置向前搜索第一個關鍵字小于pivot的記錄，并和rp交換; 3) 再從i所指位置起向后搜索，找到第一個關鍵字大于pivot的記錄，和rp交換; 4) 重復上述兩步，直至i=j為止;（此時整個序列被分成有序的前后兩塊） 5) 再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止。 對rst中記錄進行一趟快速排序，附設兩個指針i和j，設樞軸記錄rp=rs，pivot=rp.key快速排序舉例初始關鍵字：49，38，65，97，76，13，27，49pivotkey 491次交換后：27，38，65，97，76，13， ， 49ijijji2次交換后：27， 38， ，

19、97，76，13，65，49ijj3次交換后：27，38，13，97，76， ，65，49iji4次交換后：27，38，13， ，76，97，65，49jij一趟完成后：27，38，13，49，76，97，65，49一趟完成后：27，38，13，49，76，97，65，49分別進行快速排序： 13 27 38 49 49 65 76 97 快速排序結束： 13 27 38 49 49 65 76 97快速排序算法描述：int Partition(SqList &L, int low, int high)/對順序表L進行一趟快速排序，返回樞軸記錄所在的位置 L.r0 = L.rlow; / 用子

20、表的第一記錄作樞軸記錄 pivotkey = L.rlow.key; while(lowhigh) while(low=pivotkey) -high; L.rlow = L.rhigh; / 將比pivotkey 小的記錄移到低端 while(lowhigh & L.rlow.key=pivotkey) +low; L.rhigh = L.rlow; / 將比pivotkey 大的記錄移到高端 L.rlow = l.r0; return low;void Qsort(SqList &L, int low, int high)/對順序表L的子序列L.rlow.high作快速排序 if(lowh

21、igh) pivotloc = Partition(L, low, high); Qsort(L, low, pivotloc-1); Qsort(L, pivotloc+1, high); / QSortvoid QuickSort(SqList &L)/對順序表L作快速排序 Qsort(L, 1, L.length); / QuickSort快速排序算法分析在n個元素的序列中，對一個記錄定位所需時間為 O(n)。若設 T(n) 是對 n 個元素的序列進行排序所需的時間，而且每次對一個記錄正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為： T(n) cn + 2 T(n

22、/2 ) / c是一個常數(shù) cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )快速排序的平均時間是O(nlogn)，在所有同數(shù)量級(O(nlogn)的排序方法中，就平均計算時間而言，快速排序是我們所討論的所有內(nèi)部排序方法中最好的一個。快速排序需要一個?？臻g來實現(xiàn)遞歸，若每趟排序都將記錄序列均勻地分割成長度相接近的兩個子序列，則棧的最大深度為O(logn) 。若初始序列按關鍵字基本有序（最壞情況），快速排序蛻化為起泡排序

23、，其時間復雜度為O(n2) ，最壞情況下棧的深度為n 。改進的方法，用“三者取中”的法則選取樞軸記錄（pivotkey)。快速排序是一種不穩(wěn)定的排序方法。對于 n 較大的平均情況而言，快速排序是“快速”的，但是當 n 很小時，這種排序方法往往比其它簡單排序方法還要慢。 四、選擇排序基本思想：每一趟 (例如第 i 趟，i = 1, , n-1) 在 n-i+1 個記錄中選取關鍵字最小的記錄 作為有序序列中第 i 個記錄。1簡單選擇排序(Select Sort)2樹形選擇排序(Tree Selection Sort)3堆排序(Heap Sort)1簡單選擇排序(Select Sort)基本步驟：

24、i從1開始，直到n-1，進行n-1趟排序，第i 趟的排序過程為： 在一組記錄rirn (i=1,2,n-1)中選擇具有最小關鍵字的記錄, 并和第 i 個記錄進行交換。簡單選擇排序的算法void SelectSort(SqList &L) /對順序表L進行簡單選擇排序 for ( i=1; iL.length; +i) k=i; /選擇關鍵字最小的記錄 for (j = i+1;j L.rj.key) k=j;/最小記錄與第i個記錄互換 if (i!=k) temp=L.ri; L.ri=L.rk; L.rk=temp; 算法分析簡單選擇排序的關鍵字比較次數(shù)與記錄的初始排列無關。第 i 趟選擇具

25、有最小關鍵字的記錄所需的比較次數(shù)是 n-i 次，若整個待排序序列有 n 條記錄。因此，總的關鍵字比較次數(shù)為：記錄的移動次數(shù)與記錄的初始排列有關。當初始狀態(tài)是按其關鍵字從小到大有序的時候，記錄的移動次數(shù)為 0，達到最少(最好情況)。最壞情況是每一趟都要進行交換，總的記錄移動次數(shù)為3(n-1)。簡單選擇排序是一種不穩(wěn)定的排序方法。簡單選擇排序的時間復雜度是O(n2)，空間復雜度是O(1)。2樹形選擇排序(Tree Selection Sort) 又稱錦標賽排序 (Tournament Sort) , 是簡單選擇排序的改進(減少關鍵字間的比較次數(shù))?；舅枷? 與體育比賽時的淘汰賽類似。 首先取得

26、n 個記錄的關鍵字，進行兩兩比較，得到 n/2 個比較的優(yōu)勝者(關鍵字小者)，作為第一步比較的結果保留下來。然后對這 n/2 個記錄再進行關鍵字的兩兩比較，如此重復，直到選出一個關鍵字最小的記錄為止。如果 n 不是2的 k 次冪，則讓葉子結點數(shù)補足到滿足 2k-1個。葉結點上面一層的非葉結點是葉結點關鍵字兩兩比較的結果。最頂層是樹的根。每次兩兩比較的結果是把關鍵字小者作為優(yōu)勝者上升到雙親結點，稱這種比賽樹為勝者樹。位于最底層的葉結點叫做勝者樹的外結點，非葉結點稱為勝者樹的內(nèi)結點。每個結點除了存放記錄的關鍵字 key 外，還存放了此記錄是否要參選的標志 flag和此記錄在滿二叉樹中的序號inde

27、x。形成初始勝者樹（最小關鍵字上升到根）關鍵字比較次數(shù) : 7關鍵字比較次數(shù) : 2關鍵字比較次數(shù) : 2說明：錦標賽排序構成的樹是完全二叉樹，其深度為 log2n +1，其中 n 為待排序元素個數(shù)。除第一次選擇具有最小關鍵字的記錄需要進行 n-1 次關鍵字比較外，重構勝者樹選擇具有次小、再次小關鍵字記錄所需的關鍵字比較次數(shù)均為 log2n ?？傟P鍵字比較次數(shù)為O(nlog2n)。記錄的移動次數(shù)不超過關鍵字的比較次數(shù)，所以錦標賽排序總的時間復雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。錦標賽排序是一個穩(wěn)定的排序方法。3堆排序(Heap Sort) 堆

28、排序是樹形選擇排序的一種改進，主要是為了減少輔助存儲空間和多余比較。堆的定義： n個元素的序列k1, k2, , kn當且僅當滿足下列關系時，稱之為堆。例 ：（96，83，27，38，11，9）例： （13，38，27，50，76，65，49，97）可將堆序列看成完全二叉樹大頂堆小頂堆堆排序的基本思想是：把n個記錄存于向量r之中，把它看成完全二叉樹，此時關鍵字序列不一定滿足堆的關系。堆排序大體分兩步處理：第一步： 初建堆。從堆的定義出發(fā)，當i=1,2,n/2時應滿足kik2i和kik2i+1（或kik2i和kik2i+1）。所以先取i=n/2(它一定是第n個結點雙親的編號)將以i結點為根的子樹

29、調(diào)整為堆；然后令i=i-1，再將以i結點為根的子樹調(diào)整為堆。此時可能會反復調(diào)整某些結點，直到i=1為止，堆初步建成。第二步： 堆排序。首先輸出堆頂元素，讓堆中最后一個元素上移到原堆頂位置，然后恢復堆，因為經(jīng)過上移堆頂元素的操作后，往往破壞了堆關系，所以要恢復堆；重復執(zhí)行輸出堆頂元素、堆尾元素上移和恢復堆的步驟，直到全部元素輸出完為止。 我們稱這個從堆頂至葉子的調(diào)整過程為“篩選”。從一個無序序列建堆的過程就是一個反復“篩選”的過程。例如：根據(jù)輸入序列49, 38, 65, 97, 76, 13, 27, 49 ，建立一個小頂堆。第一步： 初建堆第二步：堆排序。這是一個反復輸出堆頂元素，將堆尾元素

30、移至堆頂，再調(diào)整恢復堆的過程?；謴投训倪^程與初建堆中i=1時所進行的操作完全相同。注意：每輸出一次堆頂元素，堆頂與堆尾元素就交換一次，同時堆尾的邏輯位置退1，直到堆中剩下一個元素為止。例如：對于給定的輸入序列80, 42, 13, 55, 94, 17, 46，進行堆排序。堆排序算法描述如下：void HeapSort(HeapType &H) /對順序表H進行堆排序 /初始堆建立 for ( i = H.length/2; i 0; -i) HeapAdjust(H, i, H.length); /堆的輸出與調(diào)整 for ( i = H.length; i 1; -i) temp = H.r

31、1; H.r1 = H.ri; H.ri = temp; HeapAdjust(H, 1, i-1); void HeapAdjust(HeapType &H, int s, int m)/調(diào)整H.rs.m成一個大頂堆 rc=H.rs; for(j=2*s; j=m; j*=2 ) if( jm & H.rj.key H.rj+1.key ) j+; if( rc.key H.rj.key) break; H.rs = H.rj; s=j; H.rs = rc; 算法分析時間復雜度：最壞情況下T(n)=O(nlogn)空間復雜度：S(n)=O(1)對記錄數(shù)較少的文件不值得提倡，但對n較大的文件

32、很有效。堆排序是一個不穩(wěn)定的排序方法。五、歸并排序(Merging Sort) 歸并排序(merge sort)是一類與插入排序、交換排序、選擇排序不同的另一種排序方法。歸并的含義是將兩個或兩個以上的有序表合并成一個新的有序表。歸并排序有多路歸并排序、2-路歸并排序；可用于內(nèi)部排序，也可以用于外部排序。我們僅對內(nèi)部排序的2-路歸并方法進行討論。2-路歸并排序算法思路：(1) 把n個記錄看成n個長度為1的有序子表；(2) 進行兩兩歸并使記錄關鍵字有序，得到n/2個長度為2的有序子表；(3) 重復第(2)步直到所有記錄歸并成一個長度為n的有序表為止。 例如：初始關鍵字： 49 38 65 97 7

33、6 13 27一趟歸并之后： 38 49 65 97 13 76 27兩趟歸并之后： 38 49 65 97 13 27 76 三趟歸并之后： 13 27 38 49 65 76 97 2-路歸并排序中的核心操作是將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列，其算法描述如下：void Merge( RcdType SR , RcdType &TR , int i, int m, int n )/將有序的SRi.m和SRm+1.n歸并為有序的TRi.n j = m+1; k = i; while( i = m & j = n ) if( SRi.key = SRj.key ) TRk+

34、= SRi+; else TRk+ = SRj+; while( i = m) TR k+ = SRi+; while( j = n) TR k+ = SRj+;/Merge 2-路歸并排序的遞歸算法描述如下：void MSort( RcdType SR, RcdType &TR1, int s, int t)/將SRs.t歸并排序為TR1s.t。 if( s = t ) TR1s = SRs; else m = ( s+t )/2; /將SRs.t平分為SRs.m和SRm+1.t MSort( SR, TR2, s, m ); /將SRs.m歸并為有序的TR2s.m MSort( SR, T

35、R2, m+1, t); /將SRm+1.t歸并為有序的TR2m+1.t Merge( TR2, TR1, s, m, t ); /將TR2s.m和TR2m+1.t歸并到TR1s.t /MSort void MergeSort( SqList &L )/對順序表L作歸并排序 MSort( L.r, L.r, 1, L.length );/MergeSort算法分析在歸并排序算法中，遞歸深度為O(log2n)，記錄的關鍵字比較次數(shù)為O(nlog2n)。算法總的時間復雜度為O(nlog2n)。歸并排序所需的附助空間較多，需要一個與原待排序序列數(shù)組同樣大小的輔助數(shù)組，所以算法的空間復雜度為O(n)。

36、歸并排序是一個穩(wěn)定的排序方法。六、基數(shù)排序(Radix Sort) 基數(shù)排序是與前面所介紹的排序方法完全不同的一種排序方法，該排序方法采用“分配”與“收集”的辦法，用對多關鍵字進行排序的思想實現(xiàn)對單關鍵字進行排序的方法。多關鍵字排序以撲克牌排序為例：每張撲克牌有兩個“關鍵字”：花色和面值。其有序關系為：花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A注：“花色”的地位高于“面值”如果我們進行多關鍵字排序,可以把所有撲克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A對于上例兩關鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再

37、按花色排序（先按不同“面值”分成13堆，然后將這13堆牌自小至大疊在一起（大數(shù)放在小數(shù)的下面），然后將這付牌整個顛倒過來再重新按不同“花色”分成4堆，最后將這4堆牌按自小至大的次序合在一起）。 一般情況下，假定有一個 n 個記錄的序列 R1, R2, , Rn ，且每個記錄Ri 中含有 d 個關鍵字 (Ki0, Ki1, , Kid-1) . 如果對于序列中任意兩個記錄 Ri 和 Rj ( 1 i j n ) 都滿足： (Ki0, Ki1, , Kid-1) (Kj0, Kj1, , Kjd-1) 則稱序列R1, R2, , Rn對關鍵字 (K0, K1, , Kd-1) 有序。其中，K0稱為

38、最主位關鍵字，Kd-1稱為最次位關鍵字。實現(xiàn)多關鍵字排序通常有兩種方法：最高位優(yōu)先MSD (Most Significant Digit first)最低位優(yōu)先LSD (Least Significant Digit first)最高位優(yōu)先法先根據(jù)最主位關鍵字K0排序,得到若干子序列，每個子序列中每個記錄都有相同關鍵字K0。 再分別對每個子序列中記錄根據(jù)關鍵字K1進行排序，按K1值的不同，再分成若干個更小的子序列，每個子序列中的記錄具有相同的K0和K1值。 依此重復，直到對關鍵字Kd-1完成排序為止。 最后，把所有子序列中的記錄依次連接起來，就得到一個有序的記錄序列。最低位優(yōu)先法 首先依據(jù)最次

39、位關鍵字Kd-1對所有記錄進行一趟排序，再依據(jù)關鍵字Kd-2對上一趟排序的結果再排序，依次重復，直到依據(jù)關鍵字K0最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個關鍵字進行排序時，不需要再分組，而是整個序列都參加排序。 MSD 和LSD方法也可應用于對一個關鍵字進行的排序。此時可將單關鍵字 Ki 看作是一個子關鍵字組： (Ki0, Ki1, , Kid-1)鏈式基數(shù)排序 基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關鍵字進行排序。在這種方法中，把單關鍵字 Ki 看成是一個d元組： (Ki0, Ki1, , Kid-1) 其中的每一個分量Kij ( 0

40、j d-1) 也可看成是一個關鍵字。假設分量Kij 有radix種取值，則稱radix為基數(shù)。例如，關鍵字984可以看成是一個3元組(9, 8, 4)，每一位有0, 1, , 9等10種取值，基數(shù)radix = 10。關鍵字data可以看成是一個4元組(d, a, t, a)，每一位有a, b, , z等26種取值，radix = 26。 針對d元組中的每一個分量Kij，把記錄序列中的所有記錄, 按 Kij 的取值，先“分配”到radix(rd)個隊列中去。然后再按各隊列的順序，依次把記錄從隊列中“收集”起來，這樣所有記錄按取值 Kij 排序完成。 如果對于所有記錄的關鍵字K0, K1, ,

41、Kn-1，依次對各位的分量，讓 j = d-1, d-2, , 0，分別用這種“分配”、“收集”的運算逐趟進行排序，在最后一趟“分配”、“收集” 完成后，所有記錄就按其關鍵字的值從小到大排好序了。 各隊列采用鏈式存儲結構，分配到同一隊列的關鍵字用鏈接指針鏈接起來。每一隊列設置兩 個隊列指針： front radix指示隊頭， rear radix 指向隊尾。 以靜態(tài)鏈表作為待排序序列的存儲結構。在記錄重排時不必移動記錄，只需修改各記錄的鏈接指針即可。例如：待排序序列放在單鏈表中，如下所示：109063930589184505269008083278e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f92781090639305