《數(shù)據(jù)結(jié)構(gòu)與算法》課件chap10

1、第十章 內(nèi)部 排序 目錄101 基本概念102 插入排序103 交換排序104 選擇排序105 歸并排序106 基數(shù)排序101 基本概念10.1.1 排序介紹 排序（Sorting）是數(shù)據(jù)處理中一種很重要的運算，同時也是很常用的運算，一般數(shù)據(jù)處理工作25%的時間都在進行排序。簡單地說，排序就是把一組記錄（元素）按照某個域的值的遞增（即由小到大）或遞減（即由大到?。┑拇涡蛑匦屡帕械倪^程。表10-1 學生檔案表學號姓名年齡性別99001王曉佳18男99002林一鵬19男99003謝寧17女99004張麗娟18女99005周濤20男99006李小燕16女例如，在表10-1中，若以每個記錄的學號為關(guān)鍵

2、字，按排序碼年齡的遞增（由小到大）排序，則所有記錄的排序結(jié)果可簡記為：（99006，16），（99003，17），（99001，18），（99004，18），（99002，19），（99005，20）；也可能為：（99006，16），（99003，17），（99004，18），（99001，18），（99002，19），（99005，20）；這兩個結(jié)果都是表9-1按年齡的遞增排序結(jié)果。若按排序碼姓名來進行遞增排序，則得到的排序結(jié)果為：（99006，李小燕），（99002，林一鵬），（99001，王曉佳），（99003，謝寧），（99004，張麗娟），（99005，周濤）當然，我們還可以按排序碼

3、性別來進行遞增排序，在此不再作進一步的分析。10.1.2 基本概念1排序碼（Sort Key） 作為排序依據(jù)的記錄中的一個屬性。它可以是任何一種可比的有序數(shù)據(jù)類型，它可以是記錄的關(guān)鍵字，也可以是任何非關(guān)鍵字。如上例中的學生年齡。在此我們認為對任何一種記錄都可找到一個取得它排序碼的函數(shù)Skey(一個或多個關(guān)鍵字的組合)。 2有序表與無序表一組記錄按排序碼的遞增或遞減次序排列得到的結(jié)果被稱之為有序表，相應(yīng)地，把排序前的狀態(tài)稱為無序表。3正序表與逆序表若有序表是按排序碼升序排列的，則稱為升序表或正序表，否則稱為降序表或逆序表。不失普遍性，我們一般只討論正序表。4排序定義若給定一組記錄序列r1 ，r2

4、 ，rn，其排序碼分別為s1，s2 ，sn ，將這些記錄排成順序為rk1 ，rk2 ，rkn的一個序列R，滿足條件sk1sk2 skn，獲得這些記錄排成順序為rp1 ，rp2 ，rpn的一個序列R”，滿足條件sp1sp2 spn的過程稱為排序。也可以說，將一組記錄按某排序碼遞增或遞減排列的過程，稱為排序。 5穩(wěn)定與不穩(wěn)定因為排序碼可以不是記錄的關(guān)鍵字，同一排序碼值可能對應(yīng)多個記錄。對于具有同一排序碼的多個記錄來說，若采用的排序方法使排序后記錄的相對次序不變，則稱此排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。在上例中（見表9-1，按年齡排序），如果一種排序方法使排序后的結(jié)果必為前一個結(jié)果，則稱此方法是穩(wěn)

5、定的；若一種排序方法使排序后的結(jié)果可能為后一個結(jié)果，則稱此方法是不穩(wěn)定的。 6內(nèi)排序與外排序按照排序過程中使用內(nèi)外存的不同將排序方法分為內(nèi)排序和外排序。若排序過程全部在內(nèi)存中進行，則稱為內(nèi)排序；若排序過程需要不斷地進行內(nèi)存和外存之間的數(shù)據(jù)交換，則稱為外排序。內(nèi)排序大致可分為五類：插入排序、交換排序、選擇排序、歸并排序和分配排序。本章僅討論內(nèi)排序。7排序的時間復(fù)雜性排序過程主要是對記錄的排序碼進行比較和記錄的移動過程。因此排序的時間復(fù)雜性可以以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數(shù)越少，則認為該方法的時間復(fù)雜性就越好，分析一

6、種排序方法，不僅要分析它的時間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。為了以后討論方便，我們直接將排序碼寫成一個一維數(shù)組的形式，并且在沒有聲明的情形下，所有排序都按排序碼的值遞增排列。 排序 插入排序（直插排序、二分排序、希爾排序） 交換排序（冒泡排序、快速排序） 選擇排序 （直選排序、樹型排序、堆排序） 歸并排序（二路歸并排序、多路歸并排序） 分配排序 （多關(guān)鍵字排序、基數(shù)排序） 102 插入排序 10.2.1直接插入排序1直接插入排序的基本思想 直接插入排序（Straight Insertion Sorting）的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始

7、時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。2直接插入的算法實現(xiàn) void sort(NODE array,int n)/待排序元素用一個數(shù)組array 表示，數(shù)組有n個元素 int i, j; NODE x; / x 為中間結(jié)點變量 for ( i=1; i=0)& ( x.keyarrayj.key) arrayj+1=arrayj; j-; / 順序比較和移動 arrayj+1=x; 例如，n=6，數(shù)組R的六個排序碼分別為：17，3，25，14

8、，20，9。它的直接插入排序的執(zhí)行過程如圖7-1所示。3直接插入排序的效率分析從上面的敘述可以看出，直接插入排序算法十分簡單。那么它的效率如何呢？首先從空間來看，它只需要一個元素的輔助空間，用于元素的位置交換。從時間分析，首先外層循環(huán)要進行n-1次插入，每次插入最少比較一次（正序），移動兩次；最多比較i次，移動i2次（逆序）（i=1，2，n-1）。因此，直接插入排序的時間復(fù)雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。10.2.3希爾排序1希爾排序的基本思想希爾排序, 又稱為“縮小增量排序”。是1959年由D.L.Shell提出來的。該方法的基本思想是：先將整個待排元素序列

9、分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。2希爾排序的效率分析雖然我們給出的算法是三層循環(huán)，最外層循環(huán)為log2n數(shù)量級，中間的for循環(huán)是n數(shù)量級的，內(nèi)循環(huán)遠遠低于n數(shù)量級，因為當分組較多時，組內(nèi)元素較少；此循環(huán)次數(shù)少；當分組較少時，組內(nèi)元素增多，但已接近有序，循環(huán)次數(shù)并不增加。因此，希爾排序的時間復(fù)雜性在O（nlog2n）和O（n2 ）之間，大致為O（n1. 3）。

10、例如，n=8，數(shù)組array 的八個元素分別為：91，67，35，62，29，72，46，57。下面用圖10-2給出希爾排序算法的執(zhí)行過程。由于希爾排序?qū)γ總€子序列單獨比較，在比較時進行元素移動，有可能改變相同排序碼元素的原始順序，因此希爾排序是不穩(wěn)定的。103 交換排序10.3.1 冒泡排序1冒泡排序的基本思想 通過對待排序序列從后向前（從下標較大的元素開始），依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較小的元素逐漸從后部移向前部（從下標較大的單元移向下標較小的單元），就象水底下的氣泡一樣逐漸向上冒。因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明

11、序列有序，因此要在排序過程中設(shè)置一個標志flag判斷元素是否進行過交換。從而減少不必要的比較。2冒泡排序的算法實現(xiàn)void Bubblesort( NODE array,int n) int i, j, flag; /當flag為0則停止排序 NODE temp; for ( i=1; i=i; j-) if (arrayj.keyarrayj-1.key) /發(fā)生逆序 temp=arrayj;arrayj=arrayj-1;arrayj-1=temp; flag=1; /交換，并標記發(fā)生了交換 if(flag=0) break; 例如，n=6，數(shù)組R的六個排序碼分別為：17，3，25，14，

12、20，9。下面用圖10-3給出冒泡排序算法的執(zhí)行過程。3冒泡排序的效率分析從上面的例子可以看出，當進行完第三趟排序時，數(shù)組已經(jīng)有序，所以第四趟排序的交換標志為0，即沒進行交換，所以不必進行第四趟排序。從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數(shù)為（n-1）次，移動元素次數(shù)為0；若待排序的元素為逆序，則需進行n-1趟排序，比較次數(shù)為(n2-n)/2，移動次數(shù)為3(n2-n )/2，因此冒泡排序算法的時間復(fù)雜度為O（n2）。由于其中的元素移動較多，所以屬于內(nèi)排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動，所以是一個穩(wěn)定的算法。10.3.2 快速排序1快

13、速排序的基本思想快速排序（Quick Sorting）是迄今為止所有內(nèi)排序算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序?？焖倥判蚴菍γ芭菖判虻囊环N改進方法，算法中元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面單元，排序碼較小的記錄一次就能夠交換到前面單元，記錄每次移動的距離較遠，因而總的比較和移動次數(shù)較少。 快速排序的過程為：把待排序區(qū)

14、間按照第一個元素（即基準元素）的排序碼分為左右兩個子序列的過程叫做一次劃分。設(shè)待排序序列為arraystartarrayend，其中start為下限，end為上限，startend，mid=arraystart為該序列的基準元素，為了實現(xiàn)一次劃分，令i,j的初值分別為start和end。在劃分過程中，首先讓j從它的初值開始，依次向前取值，并將每一元素arrayj的排序碼同mid的排序碼進行比較，直到arrayj.key=end) return; i=start;j=end;mid=arrayi; while (ij) while (imid.key) j-; if (ij) arrayi=ar

15、rayj; i+; while (ij & arrayi.key=mid.key) i+; if (ij) arrayj=arrayi; j-; /一次劃分得到基準值的正確位置 arrayi=mid; quicksort(array,start,i-1); /遞歸調(diào)用左子區(qū)間 quicksort(array,i+1,end); /遞歸調(diào)用右子區(qū)間3快速排序的效率分析若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長度大致相等），則結(jié)點數(shù)n與二叉樹深度h應(yīng)滿足log2nhlog2n+1 ，所以總的比較次數(shù)不會超過(n+1) log2n。因此，快速排序的最好時間復(fù)雜度應(yīng)為O（nlog2n）。而且在理論上已

16、經(jīng)證明，快速排序的平均時間復(fù)雜度也為O（nlog2n）。若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，得到的非空子區(qū)間包含有n-i個(i代表二叉樹的層數(shù)（1in）元素，每層劃分需要比較n-i+2次，所以總的比較次數(shù)為（n2+3n-4）/2。因此，快速排序的最壞時間復(fù)雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復(fù)雜度為O（log2n），最壞的空間復(fù)雜度為O(n)。快速排序是一種不穩(wěn)定的排序方法。 74 選擇排序 7.4.1 直接選擇排序1直接選擇排序的基本思想直接選擇排序也是一種簡單的排序方法。它的基本思想是：第一次從

17、array0arrayn-1中選取最小值，與array0交換，第二次從array1arrayn-1中選取最小值，與array1交換，第三次從array2arrayn-1中選取最小值，與array2交換，第i次從arrayi-1arrayn-1中選取最小值，與arrayi-1交換，, 第n-1次從arrayn-2arrayn-1中選取最小值，與arrayn-2交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。例如，給定n=8，數(shù)組R中的8個元素的排序碼為：（8，3，2，1，7，4，6，5），則直接選擇排序過程如圖7-5所示。3直接選擇排序的效率分析在直接選擇排序中，共需要進行n-1

18、次選擇和交換，每次選擇需要進行n-i次比較（1in-1），而每次交換最多需3次移動，因此，總的比較次數(shù)C= =(n2-n)/2，總的移動次數(shù)M= =3(n-1)。由此可知，直接選擇排序的時間復(fù)雜度為O(n2)數(shù)量級，所以當記錄占用的字節(jié)數(shù)較多時，通常比直接插入排序的執(zhí)行速度要快一些。由于在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩(wěn)定的排序方法。例如，給定排序碼為3，7，3，2，1，排序后的結(jié)果為1，2，3，3，7。7.4.2 樹形選擇排序從直接選擇排序可知，在n個排序碼中，找出最小值需n-1次比較，找出第二小值需n-2次比較，找出第三小值需n-3次比較，其余依此類推

19、。所以，總的比較次數(shù)為：(n-1)+(n-2)+3+2+1= (n2-n)/2，那么，能否對直接選擇排序算法加以改進，使總的比較次數(shù)比 (n2-n)/2小呢？顯然，在n個排序碼中選出最小值，至少進行n-1次比較，但是，繼續(xù)在剩下的n-1個關(guān)鍵字中選第二小的值，就并非一定要進行n-2次比較，若能利用前面n-1次比較所得信息，則可以減少以后各趟選擇排序中所用的比較次數(shù)，比如8個運動員中決出前三名，不需要7+6+5=18場比賽（前提是，若甲勝乙，而乙勝丙，則認為甲勝丙），最多需要11場比賽即可（通過7場比賽產(chǎn)生冠軍后，第二名只能在輸給冠軍的三個對中產(chǎn)生，需 2場比賽，而第三名只能在輸給亞軍的三個對中

20、產(chǎn)生，也需2場比賽，總共11場比賽）。具體見圖7-6所示。從圖10-6（a）可知，8個隊經(jīng)過4場比賽，獲勝的4個隊進入半決賽，再經(jīng)過2場半決賽和1場決賽即可知道冠軍屬誰（共7場比賽）按照錦標賽的傳遞關(guān)糸，亞軍只能產(chǎn)生于分別在決賽，半決賽和第一輪比賽中輸給冠軍的選取手中，于是亞軍只能在b、c、e這3個隊中產(chǎn)生（見圖7-6（b），即進行2場比賽（e 與c一場，e與c的勝隊與b一場）后，即可知道亞軍屬誰。同理，第三名只需在c、f、g這3個隊產(chǎn)生（見圖7-6（c）即進2場比賽（f與g一場，f與g的勝隊與c一場）即可知道第三名屬誰。 樹形選擇排序，又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方法

21、。首先對n個記錄的排序碼進行兩兩比較，然后在其中n/2 個較小者之間再進行兩兩比較，如此重復(fù)，直到選出最小排序碼為止。例如，給定排序碼頭 50，37，66，98，75，12，26，49，樹形選擇排序過程見圖7-7。 10.4.3 堆排序1堆的定義若有n個元素的排序碼k1，k2，k3，kn，當滿足如下條件： kik2i kik2i（1） kik2i+1 或 (2) kik2i+1 其中i=1,2,n/2則稱此n個元素的排序碼k1，k2，k3，kn為一個堆。若將此排序碼按順序組成一棵完全二叉樹，則（1）稱為小根堆（二叉樹的所有根結(jié)點值小于或等于左右孩子的值），（2）稱為大根堆（二叉樹的所有根結(jié)點值

22、大于或等于左右孩子的值）。若將此排序碼按順序組成一棵完全二叉樹，則（1）稱為小根堆（二叉樹的所有根結(jié)點值小于或等于左右孩子的值），（2）稱為大根堆（二叉樹的所有根結(jié)點值大于或等于左右孩子的值）。RiR2iR2i+1堆頂元素左子樹為堆右子樹為堆 若n個元素的排序碼k1，k2，k3，kn滿足堆，且讓結(jié)點按1、2、3、n順序編號，根據(jù)完全二叉樹的性質(zhì)（若i為根結(jié)點，則左孩子為2i，右孩子為2i+1）可知，堆排序?qū)嶋H與一棵完全二叉樹有關(guān)。若將排序碼初始序列組成一棵完全二叉樹，則堆排序可以包含建立初始堆（使排序碼變成能符合堆的定義的完全二叉樹）和利用堆進行排序兩個階段。例如：定義一維數(shù)組 int S11

23、=12,36,27,65,40,34,98,81,73,55,49012345678910111236276540349881735549S2堆排序的基本思想 將排序碼k1，k2，k3，kn表示成一棵完全二叉樹，然后從第n/2 個排序碼(即樹的最后一個非終端結(jié)點)開始篩選，使由該結(jié)點作根結(jié)點組成的子二叉樹符合堆的定義，然后從第n/2 -1個排序碼重復(fù)剛才操作，直到第一個排序碼止。這時候，該二叉樹符合堆的定義，初始堆已經(jīng)建立。 接著，可以按如下方法進行堆排序：將堆中第一個結(jié)點（二叉樹根結(jié)點）和最后一個結(jié)點的數(shù)據(jù)進行交換（k1與kn），再將k1kn-1重新建堆，然后k1和kn-1交換，再將k1kn

24、-2重新建堆，然后k1和kn-2交換，如此重復(fù)下去，每次重新建堆的元素個數(shù)不斷減1，直到重新建堆的元素個數(shù)僅剩一個為止。這時堆排序已經(jīng)完成，則排序碼k1，k2，k3，kn已排成一個有序序列。例如，給定排序碼49，38，65，97，76，13，27，70，建立初始堆的過程如圖7-8所示。建成如圖7-8(e)所示的堆后，堆排序過程如圖7-9所示。按層次遍歷完全二叉樹，得到一個由大到小排列的有序序列：97，76，70，65，49，38，27，134堆排序的效率分析在整個堆排序中，共需要進行n+n/2 -1次篩選運算，每次篩選運算進行雙親和孩子或兄弟結(jié)點的排序碼的比較和移動次數(shù)都不會超過完全二叉樹的深

25、度，所以，每次篩選運算的時間復(fù)雜度為O(log2n)，故整個堆排序過程的時間復(fù)雜度為O(nlog2n)。堆排序占用的輔助空間為1（供交換元素用），故它的空間復(fù)雜度為O（1）。堆排序是一種不穩(wěn)定的排序方法，例如，給定排序碼：2，1，2，它的排序結(jié)果為：1，2，2。105 歸并排序 10.5.1 二路歸并排序二路歸并排序的基本思想 二路歸并排序的基本思想是：將兩個有序子區(qū)間（有序表）合并成一個有序子區(qū)間，一次合并完成后，有序子區(qū)間的數(shù)目減少一半，而區(qū)間的長度增加一倍，當區(qū)間長度從1增加到n（元素個數(shù)）時，整個區(qū)間變?yōu)橐粋€，則該區(qū)間中的有序序列即為我們所需的排序結(jié)果。例如，給定排序碼46，55，13

26、，42，94，05，17，70，二路歸并排序過程如圖7-10所示。3二路歸并排序的效率分析二路歸并排序的時間復(fù)雜度等于歸并趟數(shù)與每一趟時間復(fù)雜度的乘積。而歸并趟數(shù)為log2n (當log2n 為奇數(shù)時，則為log2n +1)。因為每一趟歸并就是將兩兩有序子區(qū)間合并成一個有序子區(qū)間，而每一對有序子區(qū)間歸并時，記錄的比較次數(shù)均小于等于記錄的移動次數(shù)（即由一個數(shù)組復(fù)制到另一個數(shù)組中的記錄個數(shù)），而記錄的移動次數(shù)等于這一對有序表的長度之和，所以，每一趟歸并的移動次數(shù)均等于數(shù)組中記錄的個數(shù)n，即每一趟歸并的時間復(fù)雜度為O(n)。因此，二路歸并排序的時間復(fù)雜度為O(nlog2n)。利用二路歸并排序時，需要

27、利用與待排序數(shù)組相同的輔助數(shù)組作臨時單元，故該排序方法的空間復(fù)雜度為O(n)，比前面介紹的其它排序方法占用的空間大。由于二路歸并排序中，每兩個有序表合并成一個有序表時，若分別在兩個有序表中出現(xiàn)有相同排序碼，則會使前一個有序表中相同排序碼先復(fù)制，后一有序表中相同排序碼后復(fù)制，從而保持它們的相對次序不會改變。所以，二路歸并排序是一種穩(wěn)定的排序方法。10.6 基 數(shù) 排 序基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序鏈式基數(shù)排序一、多關(guān)鍵字的排序 n 個記錄的序列 R1, R2, ，Rn對關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是指： 其中: K

28、0 被稱為 “最主”位關(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 進行排序，依次類推，直至對最主位關(guān)鍵字 K0 排序完成為止。 排序過程中不需要根據(jù) “前一個” 關(guān)鍵字的排序結(jié)果，將記

29、錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子序列。例如:學生記錄含三個關(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)鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配-收集”的方法，其好處是不需要進行關(guān)鍵字間的比較。對于數(shù)字

30、型或字符型的單關(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ū)⑺鼈?“收集” 在一起；最后按其“百位數(shù)”重復(fù)一遍上述操作。在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)

31、采用鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序，具體作法為： 待排序記錄以指針相鏈，構(gòu)成一個鏈表；“分配” 時，按當前“關(guān)鍵字位”所取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中記錄的 “關(guān)鍵字位” 相同；“收集”時，按當前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。例如：p369367167239237138230139進行第一次分配進行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138368239139369 239139138進行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368進行第二次收集 進行第三次收集之后便得到記錄的有序序列f1 r1p230237138239139367167368進行第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368提醒注意：“分配”和“收集”的實際操作僅為修改鏈表中的指針和設(shè)置隊列的