數(shù)據(jù)結(jié)構(gòu)課件：第十章 排序

1、10.1 概述10.2 插入排序10.3 快速排序10.4 堆排序10.5 歸并排序10.6 基數(shù)排序10.7 各種排序方法的綜合比較第10章 排 序10.1 概 述一、排序的定義二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類一、什么是排序？排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 一般情況下，假設(shè)含n個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K

2、1, K2, ，Kn 這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系 ： Kp1Kp2Kpn(K可以是次關(guān)鍵字)按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。二、內(nèi)部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大， 整個序列的排序過程不可能在內(nèi)存中 完成，則稱此類排序問題為外部排序。三、內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)ki基于不同的“擴大” 有序序列長度的方法，內(nèi)部排序方法

3、大致可分下列幾種類型：插入類交換類選擇類 歸并類待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長度typedef int KeyType; / 關(guān)鍵字類型為整數(shù)類型typedef struct KeyType key; / 關(guān)鍵字項 InfoType otherinfo; / 其它數(shù)據(jù)項 RcdType; / 記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置 int length; / 順序表長度 SqList; / 順序表類型(結(jié)構(gòu)數(shù)組)1. 插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加

4、記錄的有序子序列的長度,有序子序列的初始長度可為零。2. 交換類通過兩兩“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。3. 選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。4. 歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。若采用順序存儲結(jié)構(gòu),要實現(xiàn)高效算法,不分配額外的輔助空間來存儲順序表(空間復(fù)雜度小),排序過程大量的原操作是什么?排序算法的時間復(fù)雜度中大量的原操作應(yīng)包擴哪些?表中元素兩兩交換位置的基本操作?10

5、. 2 插入 排 序有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n實現(xiàn)“一趟插入排序”可分三步進行：3將Ri 插入(復(fù)制)到Rj+1的位置上。2將Rj+1.i-1中的所有記錄均后移動 一個位置；1在R1.i-1中查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；直接插入排序（基于順序查找）表插入排序（基于鏈表存儲）不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）一、直接插入排序利用 “順序查找”實現(xiàn)“在R1.i-1中查找Ri的插入位置”算法的實現(xiàn)要點：從Ri-

6、1起向前進行順序查找， 監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置“哨兵”循環(huán)結(jié)束表明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找j=i-1插入位置 對于在查找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時實現(xiàn)記錄向后移動；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1上述循環(huán)結(jié)束后可以直接進行“插入”插入位置令 i = 2，3，, n, 初始有序子序列長度為1, 可實現(xiàn)整個待排序列的排序。for ( i=2; i=n; +i ) /該循環(huán)控制排序趟數(shù)

7、if ( Ri.key Ri-1.key ) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 0 1 2 3 4 5 6 7 84965 97 76 13 27 5238j=i-1j0 1 2 3 4 5 6 7 838 4997 76 13 27 52插入38插入65j=i-16565插入位置插入520 1 2 3 4 5 6 7 813 27 38 49 65 76 9752j=i-1j插入位置0 1 2 3 4 5 6 7 813 27 38 49 52 65 76 97例如:void InsertionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 fo

8、r ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 復(fù)制為監(jiān)視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置內(nèi)部排序的時間分析：實現(xiàn)內(nèi)部排序的基本操作有兩個：（2）“移動”記錄。（1）“比較”序列中兩個關(guān)鍵字的 大?。粚τ谥苯硬迦肱判颍鹤詈玫那闆r（關(guān)鍵字在記錄序列中正序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動”的次數(shù)：“移

9、動”的次數(shù)：取最大值和最小值的平均值,作為比較次數(shù)移動的次數(shù),約為n2/4,由此,時間復(fù)雜度為O(n2)什么情況下使用直接插入排序較 好? 因為 R1.i-1 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。二、折半插入排序14 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.rvoid BiInsertionSort ( SqList

10、 &L ) / BInsertSort在 L.r1.i-1中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.rhigh+1 = L.r0; / 插入low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點在低半?yún)^(qū)else low = m+1; / 插入點在高半?yún)^(qū) 折半插入排序所需的輔助空間與直接插入排序相同,空間復(fù)雜度相同. 時間上比較,減少了比較次數(shù),而記錄移動次數(shù)不變,因此時間復(fù)雜度

11、仍為 O(n2). 2-路插入排序是折半插入排序一種改進,它主要是為了減少移動次數(shù),但需要增加 n 個輔助空間(循環(huán)向量) 具體實現(xiàn)方法見P267,其移動次數(shù)約為 n2/8 , 但當L.r1.key為最小或最大時,失去了它的優(yōu)勢.三、表插入排序(利用靜態(tài)鏈表) 為了減少在排序過程中進行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應(yīng)該在的位置上。靜態(tài)鏈表的定義：#define SIZE 100Typedef struct /結(jié)點 RcdType rc; int next; SLNod

12、e;Typedef struct /鏈表 SLNode rSIZE; int length;SLinkListType;MAXINT493865977613274910初始狀態(tài)Key域next域0 1 2 3 4 5 6 7 8 MAXINT49386597761327492010 1 2 3 4 5 6 7 8 MAXINT493865977613274923100 1 2 3 4 5 6 7 8 MAXINT4938659776132749231400 1 2 3 4 5 6 7 8 i=2i=3i=4SL0.key = MAXINT ; SL0.next = 1; SL1.next =

13、0;for ( j=0, k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ); SLj.next = i; SLi.next = k; MAXINT49386597761327492315040 1 2 3 4 5 6 7 8 i=5MAXINT493865977613274963150420 1 2 3 4 5 6 7 8 i=6MAXINT4938659776132749631504720 1 2 3 4 5 6 7 8 i=7MAXINT49386597761327496815047230 1 2 3 4 5 6 7 8 i=8void L

14、InsertionSort (Elem SL ， int n) / 對記錄序列SL1.n作表插入排序 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j=0, k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ); SLj.next = i; SLi.next = k; / 結(jié)點i插入在結(jié)點j和結(jié)點k之間/ LinsertionSort算法中使用了三個指針：其中：p指示第i個記錄的當前位置 i指示第i個記錄應(yīng)在的位置 q指示第i+1個記錄的當前位置如

15、何在排序之后調(diào)整記錄序列？MAXINT4938659776132752681504723初始狀態(tài)0 1 2 3 4 5 6 7 8 重排靜態(tài)鏈表數(shù)組中記錄的過程MAXINT13386597764927526(6)15048230 1 2 3 4 5 6 7 8 MAXINT13276597764938526(6)(7)5048130 1 2 3 4 5 6 7 8 MAXINT13273897764965526(6)(7)(7)048530 1 2 3 4 5 6 7 8 i=1p=6q=7i=2p=7q=2i=3p=(2),7q=1p = SL0.next; while (pi) p = S

16、Lp.next; q = SLp.next; if ( p!= i ) SLpSLi; SLi.next = p; p = q; MAXINT13273849769765526(6)(7)(7)(6)40530 1 2 3 4 5 6 7 8 i=4p=(1),6q=8MAXINT13273849529765766(6)(7)(7)(6)(8)0540 1 2 3 4 5 6 7 8 i=5p=8q=3MAXINT13273849526597766(6)(7)(7)(6)(8)(7)040 1 2 3 4 5 6 7 8 i=6p=(3),7q=5MAXINT13273849526576976

17、(6)(7)(7)(6)(8)(7)(8)00 1 2 3 4 5 6 7 8 i=7p=(5),8q=4 while (pi) p = SLp.next; q = SLp.next; if ( p!= i ) SLpSLi; SLi.next = p; p = q; void Arrange ( Elem SL , int n ) p = SL0.next; / p指示第一個記錄的當前位置 for ( i=1; in; +i ) while (pi) p = SLp.next; q = SLp.next; / q指示尚未調(diào)整的表尾 if ( p!= i ) SLpSLi; / 交換記錄，使第

18、i個記錄到位 SLi.next = p; / 指向被移走的記錄 p = q; / p指示尚未調(diào)整的表尾， / 為找第i+1個記錄作準備 / Arrange 四.希爾排序（又稱縮小增量排序） 基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 具體實現(xiàn)為：將記錄序列分成若干子序列，分別對每個子序列進行直接插入排序。其中，d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，R

19、kd，R(k+1)d 例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設(shè)增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 void ShellIn

20、sert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) /(循環(huán)步長為dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsertvoid ShellSort (SqList &L, int dlta, int t) / 增量為dlta的希爾排序 for (k=0; k1) / while / BubbleSort (算法技巧?)i = n;i = lastExchangeInde

21、x; / 本趟進行過交換的 / 最后一個記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;時間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進行一趟冒泡 o(n)“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進行n-1趟冒泡 o(n2)“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：n-1交換一次的“移動”的次數(shù)為多少?二、一趟快速排序（一次劃分）目標：找一個記錄，以它的關(guān)

22、鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 樞軸 (i+1jt)。stlowhigh設(shè) Rs=52 為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進行比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如:R052lowhighhighhighlow算法技巧? 可見

23、，經(jīng)過“一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過程中，設(shè)立了兩個指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，并保證 Rhigh.key52，和 Rlow.key52,否則進行記錄的“交換”。int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 w

24、hile (lowhigh) while(low=pivotkey) - high; / 從右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索Rhigh = Rlow;Rlow = R0; return low;三、快速排序 首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進行快速排序void QSort (RedType & R, int s, int t ) / 對記錄序列Rs.t進行快

25、速排序 if (s t) / 長度大于1 / QSortpivotloc = Partition(R, s, t); / 對 Rs.t 進行一次劃分QSort(R, s, pivotloc-1); / 對低子序列遞歸排序，pivotloc是樞軸位置QSort(R, pivotloc+1, t); / 對高子序列遞歸排序void QuickSort( SqList & L) / 對順序表進行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。0號單元為輔助空間存樞軸四、快速排

26、序的時間分析假設(shè)一次劃分所得樞軸位置 i=k，則對n 個記錄進行快排所需時間：其中 Tpass(n)為對 n 個記錄進行一次劃分所需時間。 若待排序列中記錄的關(guān)鍵字是隨機分布的，則 k 取 1 至 n 中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)設(shè) Tavg(1)b則可得結(jié)果：結(jié)論: 快速排序的時間復(fù)雜度為O(nlogn)由此可得快速排序所需時間的平均值為： 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序或基本有序時，快速排序?qū)⑼懟癁槊芭菖判?，其時間復(fù)雜度為O(n2)。(樞軸最大或最小) 為避免出現(xiàn)這種情況，需在進行一次劃分之前，進行“予處理”，即： 先對 R

27、(s).key, R(t).key 和R(s+t)/2 .key，進行相互比較，然后取關(guān)鍵字為 “三者之中”的記錄為樞軸記錄。除此之外,還有其它的改進方法,如在一趟排序中沒有交換則結(jié)束等. 三者取中為取三者的中值,只要將中值記錄與L.rs的位置互換,其算法不變. 快速排序需要一個棧來實現(xiàn)遞歸,因其劃分過程是一個樹結(jié)構(gòu),棧的最大深度為 log2n +1(包括最外層). 顯然,每次劃分后樞軸偏向一邊,既被分割的兩部分長度相差較大為最壞情況(棧的空間大),如何改進見P277.10.4 堆 排 序一.簡單選擇排序三.堆 排 序二.樹型選擇排序(錦標賽排序)一、簡單選擇排序假設(shè)排序過程中，待排記錄序列的

28、狀態(tài)為：有序序列R1.i-1無序序列 Ri.n 第 i 趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n選擇排序的算法思想: 每一趟在 n-i+1 (i=1,2,3, n-1)個記錄中選取關(guān)鍵字最小的記錄,作為有序序列的第 i 個記錄.簡單選擇排序的算法思想: 一趟簡單選擇排序的操作為:通過n-i次的關(guān)鍵字的比較,從n-i+1個記錄中選取關(guān)鍵字最小的記錄,并和第 i (1in)個記錄交換. 令 i 從1到 n-1進行n-1趟選擇操作. 移動次數(shù)最小值為0,最大值為3(n-1). 比較次數(shù)為(1+n-1)(n-1)/2=n(n-1)/2 O(n2)簡單選擇排序的算法描

29、述如下：void SelectSort (Elem R, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; i0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當前未經(jīng)排序子序列 / H.r1.i中最后一個記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對 H.r1 進行篩選如何“建堆”？兩個問題:如何“篩選”？定義堆類型為:typedef SqList HeapType; / 堆采用順序表表示所謂“篩選”指的是，對

30、一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。堆堆篩選98814973556412362740例如:是大頂堆12但在 98 和 12 進行互換之后，它就不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中記錄的關(guān)鍵字除 Rs 之外均 / 滿足堆的特征，本函數(shù)自上而下調(diào)整 Rs 的 / 關(guān)鍵字，使 Rs.m 也成為一個大頂堆 / HeapAdjustrc = Rs; / 暫存 Rs for ( j=2*s; j= Rj.key ) break

31、; / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調(diào)整Rs = Rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調(diào)整if ( jm & Rj.keyRj+1.key ) +j; / 左/右“子樹根”之間先進行相互比較 / 令 j 指示關(guān)鍵字較大記錄的位置建堆是一個從下往上進行“篩選”的過程。40554973816436122798例如: 排序之前的關(guān)鍵字序列為123681734998817355 現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。 (98,81,49,73,36,27,40,

32、55,64,12)98494064361227(40,55,49,73,12,27,98,81,64,36)堆排序的時間復(fù)雜度分析：1. 對深度為 k 的堆，“篩選”所需進行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3. 調(diào)整“堆頂” n-1 次，總共進行的關(guān)鍵 字比較的次數(shù)不超過 2 (log2(n-1)+ log2(n-2)+ +log22) 2n(log2n) 因此，堆排序的時間復(fù)雜度為O(nlogn)。2. 對 n 個關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進行的關(guān)鍵字比較的次數(shù)至多 4n；10.5 歸 并 排 序歸并排序的過程基于下列基本思想進行： 將兩個或兩個以上的有序子序列

33、 “歸并” 為一個有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有 序 序 列 Rl.n有序子序列 Rl.m有序子序列 Rm+1.n這個操作對順序表而言，是輕而易舉的。void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的記錄序列 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) T

34、Rk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的 SRi.m 復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復(fù)制到 TR歸并排序的算法如果記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應(yīng)該先分別對這兩部分進行 2-路歸并排序。例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 5

35、2 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將SRs.t 歸并排序為 TR1s.t if (s= =t) TR1s=SRs; else / Msort 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

36、.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.tvoid MergeSort (SqList &L) / 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對 n 個記錄進行歸并排序的時間復(fù)雜度為(nlogn)。即： 每一趟歸并的時間復(fù)雜度為 O(n)， 總共需進行 log2n 趟。10.6 基 數(shù) 排 序基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序鏈式基數(shù)排序一、多關(guān)鍵字的排序 n

37、 個記錄的序列 R1, R2, ，Rn對關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是指： 其中: K0 被稱為 “最主”位關(guān)鍵字Kd-1 被稱為 “最次”位關(guān)鍵字 對于序列中任意兩個記錄 Ri 和 Rj(1ijn) 都滿足下列(詞典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1) 實現(xiàn)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)先LSD法最高位優(yōu)先MSD法先對K0進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關(guān)鍵字排序完成為止。 先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依次類

38、推，直至對最主位關(guān)鍵字 K0 排序完成為止。 排序過程中不需要根據(jù) “前一個” 關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子序列。例如:學(xué)生記錄含三個關(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ù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍

39、相同，則按LSD法進行排序時，可以采用“分配-收集”的方法，其好處是不需要進行關(guān)鍵字間的比較。對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數(shù)排序法。例如：對下列這組關(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ū)⑺鼈?/p>

40、 “收集” 在一起；最后按其“百位數(shù)”重復(fù)一遍上述操作。在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序，具體作法為： 待排序記錄以指針相鏈，構(gòu)成一個鏈表；“分配” 時，按當前“關(guān)鍵字位”所取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中記錄的 “關(guān)鍵字位” 相同；“收集”時，按當前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。例如：p368367167239237138230139進行第一次分配進行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138

41、368239139369 239139138進行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368進行第二次收集 進行第三次收集之后便得到記錄的有序序列f1 r1p230237138239139367167368進行第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368注意：“分配”和“收集”的實際操作僅為修改鏈表中的指針和設(shè)置隊列的頭、尾指針；為查找使用，該鏈表尚需應(yīng)用算法Arrange 將它調(diào)整為有序表。 基數(shù)排序的時間復(fù)雜度為O(d(n+rd)其中：分配為O(n) 收集為O(rd)(rd為“基”) d為“分配-收集”的趟數(shù)10.7 各種排序方法的綜合比較一、時間性能1. 平均的時間性能基數(shù)排序時間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序時間復(fù)雜度為 O(n2)：直接插入排序、起泡排序和簡單選擇