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

1、第十章第十章 排序排序精英專升本精英專升本10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序無序”的記錄序列調(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 概概 述述若整個排序過程不需要訪問外存不需要訪問外存便能完成，則稱此類排序問

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

3、到前面已經(jīng)排好序的一組對象已經(jīng)排好序的一組對象的的適當(dāng)位置適當(dāng)位置上上，直到，直到對象全部插入為止。對象全部插入為止。有序序列R1.i-1Ri無序序列 Ri.n直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n利用 “順序查找順序查找”實現(xiàn)“在R1.i-1中查找查找Ri的插入位置”排序過程：整個排序過程為排序過程：整個排序過程為n-1n-1趟插入，即先將序列中趟插入，即先將序列中第第1 1個記個記錄錄看成是一個有序子序列，然后從看成是一個有序子序列，然后從第第2 2個記錄個記錄開始，開始，逐個逐個進行插進行插入，直至整個序列有序入，直至整個序列有序?！?3】, 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作為哨兵作為哨兵* *表示后一個表示后一個2525從Ri-1起向前進

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

7、第最壞情況下：第 i i 趟比較趟比較i i次，移動次，移動i+1i+1次次2) 1)(2(2nnini比較次數(shù)比較次數(shù)2) 1)(4() 1(2nnini移動次數(shù)移動次數(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ù)和和移動次數(shù)移動次數(shù)為為n n2 2/4/4時間復(fù)雜度為時間復(fù)雜度為 o(o(n n2 2) )空間復(fù)雜度為空間

8、復(fù)雜度為 o(1)是一種是一種穩(wěn)定穩(wěn)定的排序方法的排序方法0 1 2 3 4 5 因為 R1.i-1 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找折半查找實現(xiàn)“在R1.i-1中查找查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插折半插入入排序。二、折半插入排序二、折半插入排序212549251608lowhighi=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時間復(fù)雜度為時間復(fù)雜度為 o(o(n n2 2) )空間復(fù)雜度為空間復(fù)雜度為 o(1)是一種是一種穩(wěn)定穩(wěn)定的排序方法的排序方法需需 n-1趟排序，趟排序，第第i趟比較趟比較n-i次，移動次，移動3(n-i)次次最壞情況下：最壞情況下：基本思想：基本思想：任取一個元素任取一個元素 ( (如第一個如第一個) ) 為中心為中心所有比它所有比它小小的元素一律前放，比它的元素一律前放，比它大大的元素一律的元素一律后放，形成后放，形成左右兩個子表左右兩個子表；對各子表重新選擇對各子表重新選擇中心中心元素并依此規(guī)則調(diào)整，直元素并依此規(guī)則調(diào)整

11、，直到每個子表的元素到每個子表的元素只剩一個只剩一個目標(biāo)：目標(biāo)：找一個記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動至該記錄之前移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸關(guān)鍵字大于樞軸的記錄均移動至該記錄之后移動至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列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)鍵字進

12、行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進行比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow 可見，經(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, 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; 首先對無序的記錄序列進行“一次劃分一次劃分”，之后分別分別對分割所得兩個子序列“遞歸遞歸”進行快速排序進行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進行快速排序void QSort (RedType &

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

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

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

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

18、rt (Elem R, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; i0; -i ) / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 / H.r1.i中最后一個記錄相互交換 / 對 H.r1 進行篩選如何如何“建堆建堆”？兩個問題兩個問題:如何如何“調(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 個結(jié)點的完全二叉樹

19、采用順序個結(jié)點的完全二叉樹采用順序存儲，最后一個分支結(jié)點的標(biāo)號是多少？存儲，最后一個分支結(jié)點的標(biāo)號是多少？從第從第 n/2 個元素起，至第一個元素止，進行反復(fù)個元素起，至第一個元素止，進行反復(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無序序列建成堆無序序列建成堆1 8 12 3 6 30 1 60 240 4 70 5 12 810 7 1 2 3 4 5 6 7 3060124070810無序序列建

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

21、 6 2 60 5 70 1 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810無序序列建成堆無序序列建成堆3 3 6 2 5 70 1 30建堆完畢建堆完畢將根結(jié)點將根結(jié)點r1與左、右子樹根結(jié)點比較，并與左、右子樹根結(jié)點比較，并與小者與小者交換交換重復(fù)重復(fù)直至葉子結(jié)點，得到新的堆直至葉子結(jié)點，得到新的堆交換交換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時間效率：時間效率：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)，用建小根堆，請畫出建堆的過程。 10.5 10.5 歸并排序歸并排序歸并：將兩個或兩個以上的有序表組合成一個新有序表歸并：將兩個或兩個以上的有序表組合成一個新有序表 排序過程排序過程初始序列看成初始序列看成n個個有序子序列，每個子序列長度為有序子序列，每個子序列長度

27、為1兩兩合并兩兩合并，得到，得到 n/2 個長度為個長度為2或或1的有序子序列的有序子序列再兩兩合并，重復(fù)直至得到再兩兩合并，重復(fù)直至得到一個一個長度為長度為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時間效率：時間效率：O(nlogO(nlog2 2n) n) 空間效率：空間效率：O O（n n）穩(wěn)穩(wěn) 定定 性：性：穩(wěn)定穩(wěn)定10.6 10.6 基數(shù)排序基數(shù)排序?qū)?252張撲克牌按以下次序排序：張撲克牌按以下次序排序： 22 33 AA 22 33 AA 22 33 AA 22 33 A A兩個關(guān)鍵字：花色（兩個關(guān)鍵字：花色（ ） 面值（面值（2323AA）并且并且“花色花色”地位高于

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

32、8,109,063,930,184,589,269,008,083按百位排序008,063,083269,278589930109,184按個位排序008063083109184269278589930十位十位278，109，063，930，184，589，269，008，083按個位排序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)先法 知道各級關(guān)鍵字的知道各級關(guān)鍵字的主次關(guān)系主次關(guān)系 知

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

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

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