1、第十章第十章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 歸并排序歸并排序10.6 基數排序基數排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.8 外部排序外部排序10.1 概概 述述一、排序的定義一、排序的定義二、內部排序和外部排序二、內部排序和外部排序三、內部排序方法的分類三、內部排序方法的分類一、什么是排序？一、什么是排序？排序是計算機內經常進行的一種操作，其目的是將一組“無序無序”的記錄序列調的記錄序列調整為整為“有序有序”的記錄序列。例如：將下列關鍵字序列52, 49, 80, 36, 14, 58, 6

2、1, 23, 97, 75調整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 一般情況下，假設含n個記錄的序列為 R1, R2, ， Rn 其相應的關鍵字序列為 K1, K2, ，Kn 這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系 ： Kp1Kp2Kpn按此固有關系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作操作稱作排序排序。二、內部排序和外部排序二、內部排序和外部排序若整個排序過程不需要訪問外存不需要訪問外存便能完成，則稱此類排序問題為內部排內部排序序； 反之，若參加排序的記錄數量很大， 整個序列的排序過程不可能在內存中 完

3、成，則稱此類排序問題為外部排序外部排序。三、內部排序的方法三、內部排序的方法內部排序的過程是一個逐步擴大逐步擴大記錄的有序序列長度有序序列長度的過程。經過一趟排序經過一趟排序有序序列區無 序 序 列 區有序序列區無 序 序 列 區基于不同的“擴大擴大” 有序序列長度的方法，內部排序方法方法，內部排序方法大致可分下列幾種類型：插入類插入類交換類交換類選擇類選擇類 歸并類歸并類其它方法其它方法待排記錄的數據類型定義如下待排記錄的數據類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長度待排順序表最大長度typedef int KeyType; / 關鍵字類型為整數類型關鍵字

4、類型為整數類型typedef struct KeyType key; / 關鍵字項關鍵字項 InfoType otherinfo; / 其它數據項其它數據項 RcdType; / 記錄類型記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置閑置 int length; / 順序表長度順序表長度 SqList; / 順序表類型順序表類型1. 插入類插入類將無序子序列中的一個或幾個記錄“插入插入”到有序序列中，從而增加記錄的有序子序列的長度。2. 交換類交換類通過“交換交換”無序序列中的記錄從而得到其中關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法

5、增加記錄的有序子序列的長度。3. 選擇類選擇類從記錄的無序子序列中“選擇”關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。4. 歸并類歸并類通過“歸并歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5. 其它方法其它方法 10. 2 插插 入入 排排 序序有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n實現實現“一趟插入排序一趟插入排序”可分三步進行：可分三步進行：3將Ri 插入插入(復制)到Rj+1的位置上。2將Rj+1.i-1中的所有記錄記錄均后移后移 一個位置；1在R1.i

6、-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；直接插入排序直接插入排序（基于順序查找）（基于順序查找）表插入排序表插入排序（基于鏈表存儲）（基于鏈表存儲）不同的具體實現方法導致不同的算法描述不同的具體實現方法導致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）一、直接插入排序一、直接插入排序利用 “順序查找順序查找”實現“在R1.i-1中查找查找Ri的插入位置”算法的實現要點：算法的實現要點：從Ri-1起向前進行順序查找， 監視哨設置在R0；R0 = Ri; / 設置“哨兵

7、”循環結束表明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找j=i-1插入位置插入位置 對于在查找過程中找到的那些關鍵字不小于Ri.key的記錄，并在查找的同時實現記錄向后移動；for (j=i-1; R0.keyRj.key; -j) Rj+1 = RjR0jRij= i-1上述循環結束后可以直接進行“插入”插入位置插入位置令 i = 2，3，, n, 實現整個序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; void Inser

8、tionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 復制為監視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置內部排序的時間分析時間分析：實現內部排序的基本操作基本操作有兩個：（2）“移動移動”記錄。（1）“比較比較”序列中兩個關鍵字的 大小；對于直接插入排序：最好的情況（關鍵字在

9、記錄序列中順序有序）：最好的情況（關鍵字在記錄序列中順序有序）：“比較”的次數：最壞的情況（關鍵字在記錄序列中逆序有序）：最壞的情況（關鍵字在記錄序列中逆序有序）：“比較”的次數：112nni02) 1)(4() 1(2nnini“移動”的次數：“移動”的次數：2) 1)(4() 1(2nnini 因為 R1.i-1 是一個按關鍵字有序的有序序列，則可以利用折半查找折半查找實現“在R1.i-1中查找查找Ri的插入位置”，如此實現的插入排序為折半插折半插入入排序。二、折半插入排序二、折半插入排序14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh1

10、4 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.rvoid BiInsertionSort ( SqList &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.k

11、ey) high = m-1; / 插入點在低半區else low = m+1; / 插入點在高半區三、表插入排序三、表插入排序 為了減少在排序過程中進行的“移動”記錄的操作，必須改變排序過程中采用的存儲結構。利用靜態鏈表進行排序，并在排序完成之后，一次性地調整各個記錄相互之間的位置，即將每個記錄都調整到它們所應該在的位置上。void LInsertionSort (Elem SL ， int n) / 對記錄序列SL1.n作表插入排序 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j=0,

12、k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ) SLj.next = i; SLi.next = k; / 結點i插入在結點j和結點k之間/ LinsertionSort算法中使用了三個指針：其中：p指示第i個記錄的當前位置 i指示第i個記錄應在的位置 q指示第i+1個記錄的當前位置如何在排序之后調整記錄序列？如何在排序之后調整記錄序列？void Arrange ( Elem SL , int n ) p = SL0.next; / p指示第一個記錄的當前位置 for ( i=1; in; +i ) while (pi) p = SLp.ne

13、xt; q = SLp.next; / q指示尚未調整的表尾 if ( p!= i ) SLpSLi; / 交換記錄，使第交換記錄，使第i個記錄到位個記錄到位 SLi.next = p; / 指向被移走的記錄指向被移走的記錄 p = q; / p指示尚未調整的表尾， / 為找第i+1個記錄作準備 / Arrange 四、希爾排序（又稱縮小增量排序）四、希爾排序（又稱縮小增量排序） 基本思想：對待排記錄序列先作“宏觀”調整，再作“微觀”調整。 所謂“宏觀”調整，指的是，“跳躍式”的插入排序。 具體做法為：將記錄序列分成若干子序列，分別對每個子序列進行插入排序。其中，d 稱為增量，它的值在排序過程

14、中從大到小逐漸縮小，直至最后一趟排序減為 1。例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 void ShellIn

15、sert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=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 / BubbleSorti = n;i = lastExchangeIndex; / 本趟

16、進行過交換的 / 最后一個記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;注意注意: :2. 一般情況下，每經過一趟“起泡”，“i 減一”，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=21. 起泡排序的結束條件為， 最后一趟沒有進行最后一趟沒有進行“交換記錄交換記錄”。時間

17、分析時間分析: :最好的情況（關鍵字在記錄序列中順序有序）：最好的情況（關鍵字在記錄序列中順序有序）： 只需進行一趟起泡只需進行一趟起泡“比較比較”的次數：的次數：最壞的情況（關鍵字在記錄序列中逆序有序）：最壞的情況（關鍵字在記錄序列中逆序有序）： 需進行需進行n-1趟起泡趟起泡“比較比較”的次數：的次數：0“移動移動”的次數：的次數：“移動移動”的次數：的次數：n-12) 1() 1(2nnini2) 1(3) 1(32nnini二、一趟快速排序（一次劃分）二、一趟快速排序（一次劃分）目標：目標：找一個記錄，以它的關鍵字作為“樞軸樞軸”，凡其關鍵字小于樞軸關鍵字小于樞軸的記錄均移動至該記錄之

18、前移動至該記錄之前，反之，凡關鍵字大于關鍵字大于樞軸樞軸的記錄均移動至該記錄之后移動至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列Rs.t將分割成兩部分分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 樞軸樞軸 (i+1jt)。52 49 80 36 14 58 61 97 23 75stlowhigh設設 Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關鍵字進行比較，要求Rhigh.key 樞軸的關鍵字 將 Rlow.key 和 樞軸的關鍵字進行比較，要求Rlow.key 樞軸的關鍵字high23low80high1

19、4low52例如例如R052lowhighhighhighlow 可見，經過“一次劃分一次劃分” ，將關鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調整過程中，設立了兩個指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，并保證 Rhigh.key52，和 Rlow.key52,否則進行記錄的“交換”。int Partition (RedType& R, int low, int high) pivotk

20、ey = Rlow.key; while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回樞軸所在位置 / Partitionint Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; /

21、 從右向左搜索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進行快速排序 if (s t-1)

22、 / 長度大于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 第一次調用函數 Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。四、快速排序的時間分析四、快速排

23、序的時間分析假設一次劃分所得樞軸位置 i=k，則對n 個記錄進行快排所需時間：其中 Tpass(n)為對 n 個記錄進行一次劃分所需時間。 若待排序列中記錄的關鍵字是隨機分布的，則 k 取 1 至 n 中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)nkavgavgavgknTkTnCnnT1)() 1(1)(設 Tavg(1)b則可得結果：) 1ln() 1)(22()(nncbnTavg結論結論: 快速排序的時間復雜度為快速排序的時間復雜度為O(nlogn)由此可得快速排序所需時間的平均值為： 若待排記錄的初始狀態為按關鍵字有序若待排記錄的初始狀態

24、為按關鍵字有序時，快速排序將蛻化為起泡排序時，快速排序將蛻化為起泡排序，其時間復雜度為O(n2)。 為避免出現這種情況，需在進行一次劃分之前，進行“予處理予處理”，即： 先對 R(s).key, R(t).key 和 R(s+t)/2.key，進行相互比較，然后取取關鍵字為 “三者之中三者之中”的記錄為樞軸為樞軸記錄。10.4 選擇選擇 排排 序序簡簡 單單 選選 擇擇 排排 序序堆堆 排排 序序一、簡單選擇排序一、簡單選擇排序假設排序過程中，待排記錄序列的狀態為：有序序列R1.i-1無序序列 Ri.n 第 i 趟簡單選擇排序從中選出關鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n簡單選

25、擇排序的算法描述如下：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; / 將堆頂記錄和當前未經排序子序列 / H.r1.i中最后一個記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對 H.r1 進行篩選如何如何“建堆建堆”？兩個問題兩個問題:如何如何“篩選篩選”？定義堆類型為定義堆類型為:typedef SqList HeapTy

26、pe; / 堆采用順序表表示之所謂“篩選篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調整調整”根結根結點點使整個二叉樹也成為一個堆。堆堆篩選篩選98814973556412362740例如例如:是大頂堆是大頂堆12但在 98 和 12 進行互換之后，它就不不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較比較void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中記錄的關鍵字除 Rs 之外均 / 滿足堆的特征，本函數自上而下調整 Rs 的 / 關鍵字，使 Rs.m 也成為一個大頂堆 / HeapAdjus

27、trc = Rs; / 暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續往下調整Rs = Rj; s = j; / 否則記錄上移，尚需繼續往下調整if ( jm & Rj.keyRj+1.key ) +j; / 左/右“子樹根”之間先進行相互比較 / 令 j 指示關鍵字較大記錄的位置建堆是一個從下往上進行建堆是一個從下往上進行“篩選篩選”的過程。的過程。40554973816436122798例如例如: 排序之前的關鍵字序列為12368173499

28、8817355 現在，左/右子樹都已經調整為堆，最后只要調整根結點，使整個二叉樹是個“堆”即可。98494064361227堆排序的時間復雜度分析：堆排序的時間復雜度分析：1. 對深度為 k 的堆，“篩選”所需進行的關鍵字比較的次數至多為2(k-1)；3. 調整“堆頂” n-1 次，總共進行的關鍵 字比較的次數不超過 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，堆排序的時間復雜度為O(nlogn)。2. 對 n 個關鍵字，建成深度為h(=log2n+1)的堆，所需進行的關鍵字比較的次數至多 4n；10.5 歸歸 并并 排排 序序歸并排序

29、的過程基于下列基本思想基本思想進行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列。在內部排序中，通常采用的是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

30、; i=m & j=n; +k) / 將SR中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的 SRi.m 復制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復制到 TR歸并排序的算法歸并排序的算法如果記錄無序序列 Rs.t 的兩部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分別按關鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應該先分別對這兩部分進行 2-路歸并排

31、序。例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 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.tMs

32、ort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.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 個記錄進行歸并排序的時間復雜度為(nlogn)。即： 每一趟歸并的時間復雜度為 O(n)， 總共需進行 l

33、og2n 趟。10.6 基基 數數 排排 序序基數排序基數排序是一種借助“多關鍵字排序”的思想來實現“單關鍵字排序”的內部排序算法。多關鍵字的排序多關鍵字的排序鏈式基數排序鏈式基數排序一、多關鍵字的排序一、多關鍵字的排序 n 個記錄的序列個記錄的序列 R1, R2, ，Rn對關鍵字對關鍵字 (Ki0, Ki1, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被稱為被稱為 “最主最主”位關鍵字位關鍵字Kd-1 被稱為被稱為 “最次最次”位關鍵字位關鍵字 對于序列中任意兩個記錄 Ri 和 Rj(1ijn) 都滿足滿足下列(詞典詞典)有序有序關系： (Ki0, Ki1, , ,Kid-1

34、) ) (Kj0, Kj1, , ,Kjd-1) ) 實現多關鍵字排序通常有兩種作法:最低位優先最低位優先LSD法法最高位優先最高位優先MSD法先對先對K0進行排序進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關直至最后對最次位關鍵字排序完成為止鍵字排序完成為止。 先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依次類推，直至對最主位直至對最主位關鍵字關鍵字 K0 排序完成為止排序完成為止。 排序過程中不需要根據 “前一個” 關鍵字的排序結果，將記錄序列分割成若干個(“前一個”關鍵字不同的)子序列。例如例如: :學生記

35、錄含三個關鍵字:系別系別、班號班號和班內的序列號班內的序列號，其中以系別為最主位關鍵字。 無序序列無序序列對對K2排序排序對對K1排序排序對對K0排序排序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的排序過程如下:二、鏈式基數排序二、鏈式基數排序假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配分配- -收集收集”的方法，其好處是不需要進行關鍵字間的比較

36、。對于數字型或字符型的單關鍵字單關鍵字，可以看成看成是由多個數位或多個字符構成的多多關鍵字關鍵字，此時可以采用采用這種“分配分配- -收集收集”的辦法進行排序進行排序，稱作基數排序法稱作基數排序法。例如：例如：對下列這組關鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個位數” 取值分別為 0, 1, , 9 “分配分配” 成 10 組，之后按從 0 至 9 的順序將 它們 “收集收集” 在一起； 然后按其 “十位數” 取值分別為 0, 1, , 9 “分配分配” 成 10 組，之后再按從 0 至 9 的順序將它們 “收集收集” 在一起

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

38、37138368239139369 239139138進行第二次分配進行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368進行第二次收集 進行第三次收集之后便得到記錄的有序序列進行第三次收集之后便得到記錄的有序序列f1 r1p230237138239139367167368進行第三次分配進行第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368提醒注意：提醒注意：“分配分配”和和“收集

39、收集”的實際操作的實際操作僅為修改鏈表中的指針和設置隊列的僅為修改鏈表中的指針和設置隊列的頭、尾指針；頭、尾指針；為查找使用，該鏈表尚需應用算為查找使用，該鏈表尚需應用算法法Arrange 將它調整為有序表。將它調整為有序表。 基數排序的時間復雜度為基數排序的時間復雜度為O(d(n+rd)其中：分配為O(n) 收集為O(rd)(rd為“基”) d為“分配-收集”的趟數10.7 各種排序方法的綜合比較各種排序方法的綜合比較一、時間性能一、時間性能1. 平均的時間性能平均的時間性能基數排序基數排序時間復雜度為時間復雜度為 O(nlogn)：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時間復

40、雜度為時間復雜度為 O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡單選擇排序簡單選擇排序時間復雜度為時間復雜度為 O(n):2. 當待排記錄序列按關鍵字順序有序時當待排記錄序列按關鍵字順序有序時3. 簡單選擇排序、堆排序和歸并排序簡單選擇排序、堆排序和歸并排序的時間性能不隨不隨記錄序列中關鍵字的分布而改變。 直接插入排序直接插入排序和起泡排序起泡排序能達到O(n)的時間復雜度， 快速排序快速排序的時間性能蛻化為O(n2) 。二、空間性能二、空間性能指的是排序過程中所需的輔助空間大小1. 所有的簡單排序方法簡單排序方法(包括：直接插入、起泡和簡單選擇) 和堆排序堆排序的空間復雜度

41、為為O(1)；2. 快速排序為快速排序為O(logn)，為遞歸程序執行過程中，棧所需的輔助空間；3. 歸并排序歸并排序所需輔助空間最多，其空間復雜度為 O(n);4. 鏈式基數排序鏈式基數排序需附設隊列首尾指針，則空間復雜度為 O(rd)。三、排序方法的穩定性能三、排序方法的穩定性能 1. 穩定的排序方法指的是，對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經過排序之后，沒有改變。 2. 當對多關鍵字的記錄序列進行LSD方法排序時，必須采用穩定的排序方法。排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 例如：例如： 排序前 ( 56, 34, 47,

42、 23, 66, 18, 82, 47 )若排序后得到結果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是穩定穩定的;若排序后得到結果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是不穩定不穩定的。 3. 對于不穩定的排序方法，只要能舉出一個實例說明即可。 4. 快速排序、堆排序和希爾排序是不穩快速排序、堆排序和希爾排序是不穩定的排序方法定的排序方法。例如例如 : 對 4, 3, 4, 2 進行快速排序， 得到 2, 3, 4, 4 四、關于四、關于“排序方法的時間復雜度的下限排序方法的時間復雜度的下限” 本章討論的各

43、種排序方法，除基數排序外，其它方法都是基于基于“比較關鍵字比較關鍵字”進進行排序的排序方法。行排序的排序方法。 可以證明， 這類排序法可能達到的最可能達到的最快的時間復雜度為快的時間復雜度為O(nlogn)。 (基數排序不是基于“比較關鍵字”的排序方法，所以它不受這個限制。) 例如:對三個關鍵字進行排序的判定樹如下：K1K3K1K2K1K3K2K3K2 K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2樹上的每一次“比較”都是必要的;樹上的葉子結點包含所有可能情況。 一般情況下，對n個關鍵字進行排序，可能得到的結果有n! 種，由于含n! 個葉子結點的二叉樹的深度不小于log2(n!) +1, 則對 n 個關鍵字進行排序的比較次數至少是 log2(n!) nlog2n (斯蒂林近似公式)。 所以，基于基于“比較關鍵字比較關鍵字