數(shù)據(jù)結(jié)構(gòu)課件10

1、第十章第十章 排序排序精英專(zhuān)升本精英專(zhuān)升本10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序無(wú)序”的記錄序列調(diào)整為的記錄序列調(diào)整為“有序有序”的記錄序列。52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 9710.1 概概 述述若整個(gè)排序過(guò)程不需要訪問(wèn)外存不需要訪問(wèn)外存便能完成，則稱此類(lèi)排序問(wèn)

2、題為內(nèi)部排內(nèi)部排序序； 反之，若參加排序的記錄數(shù)量很大， 整個(gè)序列的排序過(guò)程不可能在內(nèi)存中 完成，則稱此類(lèi)排序問(wèn)題為外部排序外部排序。內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大逐步擴(kuò)大記錄的有序序列長(zhǎng)度有序序列長(zhǎng)度的過(guò)程。經(jīng)過(guò)一趟排序經(jīng)過(guò)一趟排序有序序列區(qū)無(wú) 序 序 列 區(qū)有序序列區(qū)無(wú) 序 序 列 區(qū)52, 49, , 36, 14, 58, 61, 23, , 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 規(guī)則不同規(guī)則不同時(shí)間復(fù)雜度不同時(shí)間復(fù)雜度不同10.2 10.2 插入排序插入排序每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入插入到前面

3、到前面已經(jīng)排好序的一組對(duì)象已經(jīng)排好序的一組對(duì)象的的適當(dāng)位置適當(dāng)位置上上，直到，直到對(duì)象全部插入為止。對(duì)象全部插入為止。有序序列R1.i-1Ri無(wú)序序列 Ri.n直接插入排序的基本思想：有序序列R1.i無(wú)序序列 Ri+1.n利用 “順序查找順序查找”實(shí)現(xiàn)“在R1.i-1中查找查找Ri的插入位置”排序過(guò)程：整個(gè)排序過(guò)程為排序過(guò)程：整個(gè)排序過(guò)程為n-1n-1趟插入，即先將序列中趟插入，即先將序列中第第1 1個(gè)記個(gè)記錄錄看成是一個(gè)有序子序列，然后從看成是一個(gè)有序子序列，然后從第第2 2個(gè)記錄個(gè)記錄開(kāi)始，開(kāi)始，逐個(gè)逐個(gè)進(jìn)行插進(jìn)行插入，直至整個(gè)序列有序入，直至整個(gè)序列有序。【13】, 6, 3, 31,

4、9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3, 6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 0 1 2 3 4 5 6254925*1608初態(tài)：初態(tài)：將序列存入順序表將序列存入順序表L L中，將中，將L.r0L.r0作為哨兵作為哨兵* *表示后一個(gè)表示后一個(gè)2525從Ri-1起向前進(jìn)

5、行順序查找， R0 = Ri; / 設(shè)置“哨兵”循環(huán)結(jié)束表明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找j=i-1插入位置插入位置 對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1插入位置插入位置令 i = 2，3，, n, 實(shí)現(xiàn)整個(gè)序列的排序。for ( i=2; i=n; +i ) void InsertionSort ( SqList &L ) / 對(duì)順序表 L 作直接插

6、入排序。 / 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; / 插入到正確位置實(shí)現(xiàn)內(nèi)部排序的基本操作基本操作有兩個(gè)：（2）“移動(dòng)移動(dòng)”記錄。（1）“比較比較”序列中兩個(gè)關(guān)鍵字的 大??；n-1 比較次數(shù)比較次數(shù)移動(dòng)次數(shù)移動(dòng)次數(shù)最好情況下：最好情況下：每趟只需比較每趟只需比較 1 次，不移動(dòng)次，不移動(dòng) 總比較次數(shù)為總比較次數(shù)為 n-1for(i=2;i=L.length;+i) if( L.ri.keyL.ri-1.key)最壞情況下：

7、第最壞情況下：第 i i 趟比較趟比較i i次，移動(dòng)次，移動(dòng)i+1i+1次次2) 1)(2(2nnini比較次數(shù)比較次數(shù)2) 1)(4() 1(2nnini移動(dòng)次數(shù)移動(dòng)次數(shù)if( L.ri.keyL.ri-1.key) L.r0=L.ri; / 復(fù)制為哨兵復(fù)制為哨兵 L.rj+1=L.r0; /插入到正確位置插入到正確位置 若出現(xiàn)各種可能排列的概率相同，則可取最好情況若出現(xiàn)各種可能排列的概率相同，則可取最好情況和最壞情況的平均情況和最壞情況的平均情況 平均情況平均情況比較次數(shù)比較次數(shù)和和移動(dòng)次數(shù)移動(dòng)次數(shù)為為n n2 2/4/4時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 o(o(n n2 2) )空間復(fù)雜度為空間

8、復(fù)雜度為 o(1)是一種是一種穩(wěn)定穩(wěn)定的排序方法的排序方法0 1 2 3 4 5 因?yàn)?R1.i-1 是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找折半查找實(shí)現(xiàn)“在R1.i-1中查找查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩逭郯氩迦肴肱判颉６?、折半插入排序二、折半插入排?12549251608lowhighi=2212549251608lowhighmi=3212549251608lowhighm212549251608low/mhighi=4212549251608lowhighm212549251608low/mhighi=5212549251608lowhighm2125492

9、51608lowhighmi=62 12 54 92 51 60 8void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.r = L.r0; / 插入low = 1; high = i-1;while (low0)&(flag=1) flag=0; for(j=1;jL.rj+1.key) flag=1; x=L.rj;L.rj=L.rj+1;L.rj+1=x; 最好情況下：最好

10、情況下：)(21)(211nninni)(23)(321nninni時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 o(o(n n2 2) )空間復(fù)雜度為空間復(fù)雜度為 o(1)是一種是一種穩(wěn)定穩(wěn)定的排序方法的排序方法需需 n-1趟排序，趟排序，第第i趟比較趟比較n-i次，移動(dòng)次，移動(dòng)3(n-i)次次最壞情況下：最壞情況下：基本思想：基本思想：任取一個(gè)元素任取一個(gè)元素 ( (如第一個(gè)如第一個(gè)) ) 為中心為中心所有比它所有比它小小的元素一律前放，比它的元素一律前放，比它大大的元素一律的元素一律后放，形成后放，形成左右兩個(gè)子表左右兩個(gè)子表；對(duì)各子表重新選擇對(duì)各子表重新選擇中心中心元素并依此規(guī)則調(diào)整，直元素并依此規(guī)則調(diào)整

11、，直到每個(gè)子表的元素到每個(gè)子表的元素只剩一個(gè)只剩一個(gè)目標(biāo)：目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后移動(dòng)至該記錄之后。致使一趟排序一趟排序之后，記錄的無(wú)序序列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設(shè)設(shè) Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進(jìn)

12、行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow 可見(jiàn)，經(jīng)過(guò)“一次劃分一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = R

13、low.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索Rhigh = Rlow;Rlow = R0; return low; 首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別分別對(duì)分割所得兩個(gè)子序列“遞歸遞歸”進(jìn)行快速排序進(jìn)行快速排序。無(wú) 序 的 記 錄 序 列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序void QSort (RedType &

14、 R, int s, int t ) / 對(duì)記錄序列Rs.t進(jìn)行快速排序 if (s t-1) / 長(zhǎng)度大于1 / QSortpivotloc = Partition(R, s, t); / 對(duì) Rs.t 進(jìn)行一次劃分一次劃分 / 對(duì)低子序列遞歸排序，pivotloc是樞軸位置是樞軸位置 / 對(duì)高子序列遞歸排序void QuickSort( SqList & L) / 對(duì)順序表進(jìn)行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時(shí)，待排序記錄序列的上、下界分別為 1 和 L.length。可以證明，平均計(jì)算時(shí)間是可以證明，

15、平均計(jì)算時(shí)間是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間平均計(jì)算時(shí)間而言，快速排序是我而言，快速排序是我們所討論的所有內(nèi)排序方法中們所討論的所有內(nèi)排序方法中最好最好的一個(gè)的一個(gè)。快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)參數(shù)時(shí)參數(shù)（新的（新的lowlow和和highhigh）。最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，因此，要最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，因此，要求存儲(chǔ)開(kāi)銷(xiāo)為求存儲(chǔ)開(kāi)銷(xiāo)為 O(log2n) 。最好：劃分后，左側(cè)右側(cè)子序列的最好：劃分后，左側(cè)右側(cè)子序列的長(zhǎng)度相同長(zhǎng)度相同最壞：從小到大排好序，最壞：從小到

16、大排好序，遞歸樹(shù)成為單支樹(shù)遞歸樹(shù)成為單支樹(shù)，每次，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列，必劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列，必須經(jīng)過(guò)須經(jīng)過(guò) n n-1 -1 趟才能把所有對(duì)象定位，而且第趟才能把所有對(duì)象定位，而且第 i i 趟趟需要經(jīng)過(guò)需要經(jīng)過(guò) n n- -i i 次關(guān)鍵碼比較才能找到第次關(guān)鍵碼比較才能找到第 i i 個(gè)對(duì)象個(gè)對(duì)象的安放位置的安放位置2121211nnninni)()(時(shí)間效率：時(shí)間效率：O(nlog2n) 每趟確定的元素呈指數(shù)增加每趟確定的元素呈指數(shù)增加空間效率：空間效率：O（log2n）遞歸要用到?？臻g遞歸要用到?？臻g穩(wěn)穩(wěn) 定定 性：性： 不穩(wěn)定不穩(wěn)定 可選

17、任一元素為支點(diǎn)?？蛇x任一元素為支點(diǎn)。10.4 10.4 選擇排序選擇排序每一趟在后面每一趟在后面 n-i +1個(gè)中選出關(guān)鍵碼最小的對(duì)象個(gè)中選出關(guān)鍵碼最小的對(duì)象, 作作為有序序列的第為有序序列的第 i 個(gè)記錄個(gè)記錄簡(jiǎn)簡(jiǎn) 單單 選選 擇擇 排排 序序堆堆 排排 序序假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列R1.i-1無(wú)序序列 Ri.n 第 i 趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無(wú)序序列 Ri+1.n最小者最小者最小者最小者最小者最小者0 1 2 3 4 5最小者最小者最小者最小者結(jié)果結(jié)果各趟排序后的結(jié)果各趟排序后的結(jié)果簡(jiǎn)單選擇排序的算法描述如下：void SelectSo

18、rt (Elem R, int n ) / 對(duì)記錄序列R1.n作簡(jiǎn)單選擇排序。 for (i=1; i0; -i ) / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 / H.r1.i中最后一個(gè)記錄相互交換 / 對(duì) H.r1 進(jìn)行篩選如何如何“建堆建堆”？?jī)蓚€(gè)問(wèn)題兩個(gè)問(wèn)題:如何如何“調(diào)整調(diào)整”？typedef SqList HeapType; / 堆采用順序表表示之 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210思考：有思考：有n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)

19、采用順序個(gè)結(jié)點(diǎn)的完全二叉樹(shù)采用順序存儲(chǔ)，最后一個(gè)分支結(jié)點(diǎn)的標(biāo)號(hào)是多少？存儲(chǔ)，最后一個(gè)分支結(jié)點(diǎn)的標(biāo)號(hào)是多少？從第從第 n/2 個(gè)元素起，至第一個(gè)元素止，進(jìn)行反復(fù)個(gè)元素起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選篩選堆堆 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210 30 1 60 240 4 70 510 7 1 2 3 4 5 6 7 3060 840701210無(wú)序序列建成堆無(wú)序序列建成堆1 8 12 3 6 30 1 60 240 4 70 5 12 810 7 1 2 3 4 5 6 7 3060124070810無(wú)序序列建

20、成堆無(wú)序序列建成堆1 3 6 30 1 6040 4 12 810 7 1 2 3 4 5 6 7 3060124070810無(wú)序序列建成堆無(wú)序序列建成堆2 3 6 2 70 5 30 1 7040 4 12 810 7 1 2 3 4 5 6 7 3070124060810無(wú)序序列建成堆無(wú)序序列建成堆2 3 6 2 60 5 7040 4 12 810 7 1 2 3 4 5 6 7 3070124060810無(wú)序序列建成堆無(wú)序序列建成堆3 3 6 2 60 5 30 1 3040 4 12 810 7 1 2 3 4 5 6 7 7030124060810無(wú)序序列建成堆無(wú)序序列建成堆3 3

21、 6 2 60 5 70 1 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810無(wú)序序列建成堆無(wú)序序列建成堆3 3 6 2 5 70 1 30建堆完畢建堆完畢將根結(jié)點(diǎn)將根結(jié)點(diǎn)r1與左、右子樹(shù)根結(jié)點(diǎn)比較，并與左、右子樹(shù)根結(jié)點(diǎn)比較，并與小者與小者交換交換重復(fù)重復(fù)直至葉子結(jié)點(diǎn)，得到新的堆直至葉子結(jié)點(diǎn)，得到新的堆交換交換r1和和rn后，如何將后，如何將r1.n-1重新調(diào)整，重新調(diào)整，使之成使之成為新堆？為新堆？ 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810 3 6 2 30 5 70 1堆的重新調(diào)整堆的重新調(diào)整1堆的重新調(diào)整

22、堆的重新調(diào)整1 6040 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 510 17060124030810707010 60106010104040堆的重新調(diào)整堆的重新調(diào)整2 4010 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 560 160401210308107070 堆的重新調(diào)整堆的重新調(diào)整2 4010 4 12 6010 7 1 2 3 4 5 6 7 3 6 2 30 58 1840121030601070706060堆的重新調(diào)整堆的重新調(diào)整2 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 140

23、3012108601070706060堆的重新調(diào)整堆的重新調(diào)整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 1403012108601070706060堆的重新調(diào)整堆的重新調(diào)整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 1830121086010707060604040堆的重新調(diào)整堆的重新調(diào)整3 108 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新調(diào)整堆的重新調(diào)整4 108 4 12 6010 7 1 2 3 4 5 6 7

24、 3 6 28 530 1301012886010707060604040堆的重新調(diào)整堆的重新調(diào)整4 1030 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 18101230860107070606040403030堆的重新調(diào)整堆的重新調(diào)整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 512 11210830860107070606040403030堆的重新調(diào)整堆的重新調(diào)整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新調(diào)整堆的重

25、新調(diào)整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新調(diào)整堆的重新調(diào)整5 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新調(diào)整堆的重新調(diào)整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新調(diào)整堆的重新調(diào)整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 5

26、8 18883086010707060604040303012121010時(shí)間效率：時(shí)間效率：O(nlogO(nlog2 2n) n) 空間效率：空間效率：O O（1 1）穩(wěn)穩(wěn) 定定 性：性：不穩(wěn)定不穩(wěn)定適用于適用于n 較大較大的情況的情況已知一組待排記錄的關(guān)鍵字序列為(16，12，18，60，15，36，14，18，25，85)，用建小根堆，請(qǐng)畫(huà)出建堆的過(guò)程。 10.5 10.5 歸并排序歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新有序表歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新有序表 排序過(guò)程排序過(guò)程初始序列看成初始序列看成n個(gè)個(gè)有序子序列，每個(gè)子序列長(zhǎng)度為有序子序列，每個(gè)子序列長(zhǎng)度

27、為1兩兩合并兩兩合并，得到，得到 n/2 個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為2或或1的有序子序列的有序子序列再兩兩合并，重復(fù)直至得到再兩兩合并，重復(fù)直至得到一個(gè)一個(gè)長(zhǎng)度為長(zhǎng)度為n的有序序的有序序列為止列為止0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7130 1 2 3 44913659776780AB0

28、 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776

29、780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680B B 表的元素都表的元素都已移入已移入 C C 表，表，只需將只需將 A A 表的表的剩余部分移入剩余部分移入 C C 表即可表即可0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965768097例例初始關(guān)鍵字：初始關(guān)鍵字： 49 38 65 97 76

30、13 27一趟歸并后：一趟歸并后： 38 49 65 97 13 76 27二趟歸并后：二趟歸并后： 38 49 65 97 13 27 76三趟歸并后：三趟歸并后： 13 27 38 49 65 76 97時(shí)間效率：時(shí)間效率：O(nlogO(nlog2 2n) n) 空間效率：空間效率：O O（n n）穩(wěn)穩(wěn) 定定 性：性：穩(wěn)定穩(wěn)定10.6 10.6 基數(shù)排序基數(shù)排序?qū)?duì)5252張撲克牌按以下次序排序：張撲克牌按以下次序排序： 22 33 AA 22 33 AA 22 33 AA 22 33 A A兩個(gè)關(guān)鍵字：花色（兩個(gè)關(guān)鍵字：花色（ ） 面值（面值（2323AA）并且并且“花色花色”地位高于

31、地位高于“面值面值”多關(guān)鍵字排序多關(guān)鍵字排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序：用鏈?zhǔn)交鶖?shù)排序：用作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序先對(duì)先對(duì)最高位最高位關(guān)鍵字關(guān)鍵字k1k1（如花色）排序，將序列分如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的成若干子序列，每個(gè)子序列有相同的k1k1值；值；然后讓每個(gè)子序列對(duì)然后讓每個(gè)子序列對(duì)次關(guān)鍵字次關(guān)鍵字k2k2（如面值）排序如面值）排序，又分成若干更小的子序列；，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字最低位關(guān)鍵字kdkd排序排序，就可以得到一個(gè)有序的序列。，就可以得到一個(gè)有序的序列。27

32、8,109,063,930,184,589,269,008,083按百位排序008,063,083269,278589930109,184按個(gè)位排序008063083109184269278589930十位十位278，109，063，930，184，589，269，008，083按個(gè)位排序930，063，083，184，278，008，109，589，269按十位排序008，109，930，063，169，278，083，184，589按百位排序008，063，083，109，169，184，278，589，930，最低位優(yōu)先法最低位優(yōu)先法 知道各級(jí)關(guān)鍵字的知道各級(jí)關(guān)鍵字的主次關(guān)系主次關(guān)系 知

33、道各級(jí)關(guān)鍵字的知道各級(jí)關(guān)鍵字的取值范圍取值范圍鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序 首先對(duì)首先對(duì)低位關(guān)鍵字低位關(guān)鍵字排序，各個(gè)記錄按照此位關(guān)鍵字排序，各個(gè)記錄按照此位關(guān)鍵字的值的值分配分配到相應(yīng)的序列里。到相應(yīng)的序列里。 按照序列對(duì)應(yīng)的值的大小，從各個(gè)序列中將記錄按照序列對(duì)應(yīng)的值的大小，從各個(gè)序列中將記錄收集收集，收集后的序列按照此位關(guān)鍵字有序。，收集后的序列按照此位關(guān)鍵字有序。 在此基礎(chǔ)上，對(duì)前一位關(guān)鍵字進(jìn)行排序。在此基礎(chǔ)上，對(duì)前一位關(guān)鍵字進(jìn)行排序。初始狀態(tài)：初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3

34、e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收集一趟收集008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5

35、e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589二趟收集二趟收集 設(shè)置設(shè)置1010個(gè)隊(duì)列個(gè)隊(duì)列，fifi和和eiei分別頭指針和尾指針?lè)謩e頭指針和尾指針對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，錄的指針值，將鏈表中記錄分配至將鏈表中記錄分配至1010個(gè)鏈隊(duì)列中個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同是改變所有非空隊(duì)列的是改變所有非空隊(duì)列的域，令其指向域，令其指向，重新將重新將1010個(gè)隊(duì)列鏈成一個(gè)鏈表個(gè)隊(duì)列鏈成一個(gè)鏈表