1、第十章第十章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序(交換類交換類10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.6 基數排序基數排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.1 概概 述述一、排序的定義一、排序的定義三、內部排序方法的分類三、內部排序方法的分類二、排序方法的穩定性能二、排序方法的穩定性能一、什么是排序？一、什么是排序？排序是計算機內經常進展的一種操作，其目的是將一組“無序的記錄序列調整為“有序的記錄序列。例如：將以下關鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調整為14

2、, 23, 36, 49, 52, 58, 61 ,75, 80, 97二、排序方法的穩定性能二、排序方法的穩定性能 1. 穩定的排序方法指的是，對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經過排序之后，沒有改動。排序之前排序之前 : Ri(K) Rj(K) 排序之后排序之后 : Ri(K) Rj(K) 例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47* )假設排序后得到結果 ( 18, 23, 34, 47, 47*, 56, 66, 82 )那么稱該排序方法是穩定的;假設排序后得到結果 ( 18, 23, 34, 47*, 47, 5

3、6, 66, 82 )那么稱該排序方法是不穩定的。 2. 對于不穩定的排序方法，只需能對于不穩定的排序方法，只需能舉出一個實例闡明即可。舉出一個實例闡明即可。例如例如 : 對對 4*, 3, 4, 2 進展快速排序，進展快速排序， 得到得到 2, 3, 4, 4* 三、內部排序的方法三、內部排序的方法內部排序的過程是一個逐漸擴展記錄的有序序列長度的過程。經過一趟排序經過一趟排序有序序列區無 序 序 列 區有序序列區無 序 序 列 區基于不同的“擴展 有序序列長度的方法，內部排序方法大致可分以下幾種類型：插入類插入類交換類交換類選擇類選擇類 歸并類歸并類1. 插入類插入類將無序子序列中的一個或幾

4、個記錄“插入到有序序列中，從而添加記錄的有序子序列的長度。2. 交換類交換類經過“交換無序序列中的記錄從而得到其中關鍵字最小或最大的記錄，并將它參與到有序子序列中，以此方法添加記錄的有序子序列的長度。3. 選擇類選擇類從記錄的無序子序列中“選擇關鍵字最小或最大的記錄，并將它參與到有序子序列中，以此方法添加記錄的有序子序列的長度。4. 歸并類歸并類經過“歸并兩個或兩個以上的記錄有序子序列，逐漸添加記錄有序序列的長度。 10. 2 插插 入入 排排 序序有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的根本思想：有序序列R1.i無序序列 Ri+1.n實現實現“一趟插入排序一趟插入排序可分

5、三步進展：可分三步進展：3將將Ri 插入插入(復制復制)到到Rj+1的位置的位置上。上。2將將Rj+1.i-1中的一切記錄均后移中的一切記錄均后移 一個位置；一個位置；1在在R1.i-1中查找中查找Ri的插入位置，的插入位置， R1.j.key Ri.key Rj+1.i-1.key；直接插入排序直接插入排序基于順序基于順序查找查找希爾排序希爾排序基于逐趟減少增量基于逐趟減少增量 不同的詳細實現方法導致不同的算法描畫不同的詳細實現方法導致不同的算法描畫折半插入排序折半插入排序基于折半基于折半查找查找一、直接插入排序一、直接插入排序利用 “順序查找實現“在R1.i-1中查找Ri的插入位置算法的實

6、現要點：算法的實現要點：初始形狀初始形狀4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟趟 排序排序 1 趟趟 排序排序 2 趟趟 排序排序 void InsertSort ( SqList &L ) / 對順序表對順

7、序表 L 作直接插入排序。作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) 在在 R1. i-1中查找中查找 RI / InsertSort 排序過程：先將序列中第排序過程：先將序列中第 1 個記錄看成是一個有序子序列，個記錄看成是一個有序子序列， 然后從第然后從第 2 個記錄開場，逐個進展插入，直至整個序列有序。個記錄開場，逐個進展插入，直至整個序列有序。 的插入位置的插入位置; 對于在查找過程中找到的那些關鍵字對于在查找過程中找到的那些關鍵字 不小于不小于 Ri.key 的記錄，在查找的同的記錄，在查找的

8、同 時實現記錄向后挪動；時實現記錄向后挪動； 插入插入 Ri ;L.r0 = L.ri; / 復制為監視哨復制為監視哨 L.ri = L.ri -1; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 記錄后移記錄后移 L.r j + 1 = L.r0; / 插入到正確位置插入到正確位置 對于在查找過程中找到的那些關鍵字不小于Ri.key的記錄，并在查找的同時實現記錄向后挪動；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1上述循環終了后可以直接進展“插入

9、插入位置插入位置內部排序的時間分析：實現內部排序的根本操作有兩個：2“挪動記錄。1“比較序列中兩個關鍵字的 大小；對于直接插入排序：最好的情況最好的情況關鍵字在記錄序列中順序有序關鍵字在記錄序列中順序有序：“比較的次數：最壞的情況最壞的情況關鍵字在記錄序列中逆序有序關鍵字在記錄序列中逆序有序：“比較的次數：112nni02) 1)(4() 1(2nnini“挪動的次數：“挪動的次數：2) 1)(2()(2nnini時間效率： 由于在最壞情況下，一切元素的比較次數總和為01n-1)O(n2)。其他情況下也要思索挪動元素的次數。 故時間復雜度為O(n2) 空間效率：僅占用1個緩沖單元O1算法的穩定

10、性：穩定 由于 R1.i-1 是一個按關鍵字有序的有序序列，那么可以利用折半查找實現“在R1.i-1中查找Ri的插入位置，如此實現的插入排序為折半插入排序。二、折半插入排序二、折半插入排序void 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

11、)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點在低半區插入點在低半區else low = m+1; / 插入點在高半區插入點在高半區14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r時間復雜度：時間復雜度： T(n)=O(n) 空間復雜度：空間復雜度：S(n)=O(1) 折半插入排序是穩定排序折半插入排序是穩定排序 僅減少了比較次數，僅減少了比較次數，

12、挪動次數不變。挪動次數不變。 三、希爾排序三、希爾排序又稱減少增量排序又稱減少增量排序 根本思想：對待排記錄序列先作“宏觀調整，再作“微觀調整。 所謂“宏觀調整，指的是，“騰躍式的插入排序。 詳細做法為：將記錄序列分成假設干子序列，分別對每個子序列進展插入排序。其中，d 稱為增量，它的值在排序過程中從大到小逐漸減少，直至最后一趟排序減為 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 第一趟希爾排序，設

13、增量 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 ShellInsert ( 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 =

14、 L.r0; / 插入插入 / if / ShellInsertvoid ShellSort (SqList &L, int dlta, int t) / 增量為增量為dlta的希爾排序的希爾排序 for (k=0; k1) / while / BubbleSorti = n;i = lastExchangeIndex; / 本趟進展過交換的 / 最后一個記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進展交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeInd

15、ex = 1;留意留意: :2. 普通情況下，每經過一趟“起泡，“i 減一，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=21. 起泡排序的終了條件為， 最后一趟沒有進展“交換記錄。v 算法評價算法評價 時間復雜度：時間復雜度： 最好情況最好情況正序正序 比較次數：比較次數：n -1 挪動次數：挪動次數：0 T(n) = O(n) 最壞情況最壞情況逆序逆序 比較次數：比較次數： 挪動次數：挪動次數： )(21)1(22nnini )(23)1(322nnini 空間復雜度

16、：空間復雜度：S(n) = O(1) 穩定性：穩定排序穩定性：穩定排序 二、一趟快速排序二、一趟快速排序一次劃分一次劃分目的：找一個記錄，以它的關鍵字作為目的：找一個記錄，以它的關鍵字作為“樞軸樞軸，凡其關鍵字小于樞軸的記錄均，凡其關鍵字小于樞軸的記錄均挪動至該記錄之前，反之，凡關鍵字大于挪動至該記錄之前，反之，凡關鍵字大于樞軸的記錄均挪動至該記錄之后。樞軸的記錄均挪動至該記錄之后。致使一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rk.key (sji-1) 樞軸 (i+1kt)。52 49 80 36 14 58 61 97

17、 23 75stlowhigh設設 Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關鍵字進展比較，要求Rhigh.key 樞軸的關鍵字 將 Rlow.key 和 樞軸的關鍵字進展比較，要求Rlow.key 樞軸的關鍵字high23low80high14low52例如例如R052lowhighhighhighlow 可見，經過“一次劃分 ，將關鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調整過程中，設立了兩個指針： low 和high，之后逐漸減小

18、 high，添加 low，并保證 Rhigh.key52，和 Rlow.key52,否那么進展記錄的“交換。int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索從右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索從左向右搜索Rhigh = Rlow;Rlow =

19、R0; return low;三、快速排序三、快速排序 首先對無序的記錄序列進展“一次劃分，之后分別對分割所得兩個子序列“遞歸進展快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進展快速排序void QSort (RedType & R, int s, int t ) / 對記錄序列對記錄序列Rs.t進展快速排序進展快速排序 if (s t-1) / 長度大于長度大于1 / QSortpivotloc = Partition(R, s, t); / 對 Rs.t 進展一次劃分QSort(R, s, pivotloc-1); / 對低子序列遞歸

20、排序，pivotloc是樞軸位置QSort(R, pivotloc+1, t); / 對高子序列遞歸排序void QuickSort( SqList & L) / 對順序表進展快速排序對順序表進展快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調用函數 Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。四、快速排序的時間分析四、快速排序的時間分析時間效率：時間效率：O(nlog2n) 由于每趟確定由于每趟確定的元素呈指數添加，到目前為止快速排的元素呈指數添加，到目前為止快速排序是平均速度最好的一種排序方法。序是平均速度最

21、好的一種排序方法。 空間效率：空間效率：Olog2n由于遞歸要用由于遞歸要用棧棧(存每層存每層low，high和和pivot)穩穩 定定 性：性： 不穩定不穩定 由于有騰躍式交換。由于有騰躍式交換。10.4 選擇選擇 排排 序序簡簡 單單 選選 擇擇 排排 序序堆堆 排排 序序一、簡單項選擇擇排序一、簡單項選擇擇排序假設排序過程中，待排記錄序列的形狀為：有序序列R1.i-1無序序列 Ri.n 第 i 趟簡單項選擇擇排序從中選出關鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n例：關鍵字序列例：關鍵字序列T= T= 2121，2525，4949，2525* *，1616，0808，請給出簡單

22、項選擇擇排序的詳細實現過，請給出簡單項選擇擇排序的詳細實現過程。程。原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49簡單項選擇擇排序的算法描畫如下：void SelectSort (Elem R, int n ) / 對記錄序列對記錄序列R1.n作簡單項選擇擇排序。作簡單項選擇擇排序。 for (i=1; in; +i) / 選擇第選擇第 i 小的記

23、錄，并交換到位小的記錄，并交換到位 / SelectSortj = SelectMinKey(R, i); / 在 Ri.n 中選擇關鍵字最小的記錄if (i!=j) RiRj; / 與第與第 i 個記錄交換個記錄交換時間性能分析時間性能分析時間效率：時間效率： O(n2)雖挪動次數較少，雖挪動次數較少，但比較次數仍多。但比較次數仍多。 空間效率：空間效率：O1沒有附加單元沒有附加單元僅用到僅用到1個個temp)算法的穩定性：不穩定算法的穩定性：不穩定10.4.2 樹形選擇排序樹形選擇排序 思想：首先對思想：首先對 n 個記錄的關鍵字進展兩兩比較，然后在其個記錄的關鍵字進展兩兩比較，然后在其

24、中中 n/2 個較小者之間再進展兩兩比較，直到選出最小關鍵字個較小者之間再進展兩兩比較，直到選出最小關鍵字 的記錄為止。可以用一棵有的記錄為止。可以用一棵有 n 個葉子結點的完全二叉樹表示。個葉子結點的完全二叉樹表示。 38 13 13 13 38 65 27 13 38 49 65 97 76 27 49 13 76 27 27 27 49 49 38 38 49 49 49 49 65 49 49 76 65 65 97 97 76 97 76 97 13 27 38 49 49 65 76 97 時間復雜度：由于含有時間復雜度：由于含有 n 個葉子結點的完全二叉樹的深度個葉子結點的完全二

25、叉樹的深度 為為log2n+1，那么在樹形選擇排序中中，除了最小關鍵字外，每，那么在樹形選擇排序中中，除了最小關鍵字外，每 選擇一個次小關鍵字僅需進展選擇一個次小關鍵字僅需進展 log2n 次比較，故時間復雜度次比較，故時間復雜度 為為 O(nlog2n)。 缺陷：缺陷： 1、與、與“的比較多余；的比較多余； 2、輔助空間運用多。、輔助空間運用多。 二、堆排序二、堆排序堆是滿足以下性質的數列r1, r2, ，rn：或或122iiiirrrr122iiiirrrr堆的定義堆的定義:(小頂堆)(大頂堆)例：有序列例：有序列T1=08, 25, 49, 46, 58, 67和序列和序列T2=91,

26、85, 76, 66, 58, 67, 55,判別它們能否判別它們能否 “堆堆？234561大根堆大根堆2345617小根堆小根堆小頂堆小頂堆 最小堆最小堆大頂堆大頂堆最大堆最大堆123456例：關鍵字序列例：關鍵字序列T= (21，25，49，25*，16，08，請建大根堆。，請建大根堆。2. 怎樣建堆？怎樣建堆？解：為便于了解，先將原始序列畫成完全二叉樹的方式：解：為便于了解，先將原始序列畫成完全二叉樹的方式： 這樣可以很明晰地從這樣可以很明晰地從(n-1)/2開場調整。開場調整。而且而且21還該當向下比較！還該當向下比較！ 49大于大于08，不用調整；，不用調整；i=2: 25大于大于2

27、5*和和16，也不用調整；，也不用調整；i=1: 21小于小于25和和49，要調整！，要調整！建堆是一個從下往上進展建堆是一個從下往上進展“挑選挑選的過程。的過程。40554973816436122798例如例如: 排序之前的關鍵字序列為排序之前的關鍵字序列為(40,55,49,73,12,27,98,81,64,36)建為大根堆建為大根堆.123681734998817355 如今，左/右子樹都曾經調整為堆，最后只需調整根結點，使整個二叉樹是個“堆即可。984940643612273. 3. 怎樣進展整個序列的堆排序？怎樣進展整個序列的堆排序？堆排序需處理的兩個問題：堆排序需處理的兩個問題：

28、 1、如何由一個無序序列建成一個堆？、如何由一個無序序列建成一個堆？ 2、在輸出堆頂元素后，如何將剩余元素、在輸出堆頂元素后，如何將剩余元素調整為一個新的堆？調整為一個新的堆？ 123456而且而且21還該當向下比較！還該當向下比較！1、建堆、建堆舉例：關鍵字序列舉例：關鍵字序列T= (21，25，49，25*，16，08，進展堆排序，進展堆排序2、對剛剛建好的大根堆進展排序：、對剛剛建好的大根堆進展排序：1234561365421234561365421234561365421234561365421234561365424、堆排序算法分析： 時間效率： O(nlog2n)。由于整個排序過程

29、中需求調用n-1次堆頂點的調整，而每次堆排序算法本身耗時為log2n； 空間效率：O(1)。僅在第二個for循環中交換記錄時用到一個暫時變量temp。 穩定性： 不穩定。 優點：對小文件效果不明顯，但對大文件有效。堆排序是一種速度快且省空間的排序方法。 10.5 歸歸 并并 排排 序序歸并排序的過程基于以下根本思想進展： 將兩個或兩個以上的有序子序列 “歸并 為一個有序序列。在內部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m 有序子序列有序子序列 Rm+1.n這個操作對順序表而言，

30、是輕而易舉的。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) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的將剩余的 SRi.m 復制到

31、復制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的將剩余的 SRj.n 復制到復制到 TR歸并排序的算法歸并排序的算法假設記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分別按關鍵字有序，那么利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應該先分別對這兩部分進展 2-路歸并排序。例如：例如：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

32、 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.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m

33、, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.tvoid MergeSort (SqList &L) / 對順序表對順序表 L 作作2-路歸并排序路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort由于在遞歸的歸并排序算法中，函數由于在遞歸的歸并排序算法中，函數Merge( )做一做一趟兩路歸并排序，需求調用趟兩路歸并排序，需求調用merge ( )函數函數 n/(2len) O(n/len) 次，而每次次，而每次merge( )要執要執行比較行比較O(len)次，另外整個歸并過程有次，另外整個歸并過程有log2n “層層 ，

34、所以算法總的時間復雜度為，所以算法總的時間復雜度為O(nlog2n)。 空間效率：空間效率： O(n) 由于需求一個與原始序列同樣大小的輔助序列。這由于需求一個與原始序列同樣大小的輔助序列。這正是此算法的缺陷。正是此算法的缺陷。 穩定性：穩定穩定性：穩定10.6 基基 數數 排排 序序基數排序是一種借助“多關鍵字排序的思想來實現“單關鍵字排序的內部排序算法。多關鍵字的排序多關鍵字的排序鏈式基數排序鏈式基數排序多關鍵字的排序多關鍵字的排序 例：將右表所示的學生例：將右表所示的學生 成果單按數學成果成果單按數學成果 的等級由高到低排的等級由高到低排 序，數學成果一樣序，數學成果一樣 的學生再按英語

35、成的學生再按英語成 績的高低等級排序。績的高低等級排序。 學號學號數學數學英語英語其它其它 101 B C 102 A B 103 C D 104 B B 105 A A 106 D B 107 E A 108 C B105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A特點：每個記錄最特點：每個記錄最終的位置由兩個關終的位置由兩個關鍵字鍵字 k1 k2 決議。決議。第二關鍵字第二關鍵字 K2 第一關鍵字第一關鍵字 K1 我們將它稱之我們將它稱之為復合關鍵字，即為復合關鍵字，即多關鍵字多關鍵字 排序是按排序是按照復合關鍵字

36、照復合關鍵字 的大小排序。的大小排序。 以上兩例都是典型的多關鍵字排序！實現多關鍵字排序通常有兩種作法:最低位優先最低位優先LSDLSD法法最高位優先最高位優先MSDMSD法法由于有分組，故此算法需遞歸實現。例：初始關鍵字序列例：初始關鍵字序列T=T=32, 13, 27, 3232, 13, 27, 32* *, 19, 19，3333，請分別用請分別用MSDMSD和和LSDLSD進展排序，并討論其優缺陷。進展排序，并討論其優缺陷。法法1 1MSDMSD：原始序列：原始序列：32,13,27,3232,13,27,32* *,19,33,19,33先按高位先按高位Ki1 Ki1 排序：排序：

37、13,1913,19,27,27,32,3232,32* *，3333再按低位再按低位Ki2 Ki2 排序排序 ： 13, 19, 27, 32, 3213, 19, 27, 32, 32* *,33,33法法2 2LSDLSD： 原始序列：原始序列：32,13,27,3232,13,27,32* *,19 ,19 ，3333先按低位先按低位Ki2Ki2排序：排序： 32, 3232, 32* *,13, 33, 27, 19 ,13, 33, 27, 19 再按高位再按高位Ki1Ki1排序：排序： 13, 19 ,27, 32, 3213, 19 ,27, 32, 32* *,33,33無需

38、分組，易編程實現！11552164547077027755645402112170775554，64217002又稱散列過程！又稱散列過程！，1177556454021121707064542111027770645554211102，77，55所用隊列是順序構造，浪費空間，能否改用鏈式構造？所用隊列是順序構造，浪費空間，能否改用鏈式構造？能！能！二、鏈式基數排序二、鏈式基數排序假設多關鍵字的記錄序列中，每個關鍵字的取值范圍一樣，那么按LSD法進展排序時，可以采用“分配-搜集的方法，其益處是不需求進展關鍵字間的比較。對于數字型或字符型的單關鍵字，可以看成是由多個數位或多個字符構成的多關鍵字，此

39、時可以采用這種“分配-搜集的方法進展排序，稱作基數排序法。e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9r0530790921101614485215306637738r0e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738530790921101614485215306637738r

40、0r0530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738r0r0提示留意：提示留意：“分配分配和和“搜集搜集的實踐操作僅為的實踐操作僅為修正鏈表中的指針和設置隊列的頭、修正鏈表中的指針和設置隊列的頭、尾指針；尾指針； 基數排序的時間復雜度為O(d(n+rd)其中：分配為O(n) 搜集為O(rd)(rd為“基) d為“分配-搜集的趟數10.7 各種排序方法的綜合比較各種排序