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

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

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

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

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

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

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

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

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

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

11、序列有序，因此要在排序過(guò)程中設(shè)置一個(gè)標(biāo)志flag判斷元素是否進(jìn)行過(guò)交換。從而減少不必要的比較。2冒泡排序的算法實(shí)現(xiàn)void Bubblesort( NODE array,int n) int i, j, flag; /當(dāng)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; /交換，并標(biāo)記發(fā)生了交換 if(flag=0) break; 例如，n=6，數(shù)組R的六個(gè)排序碼分別為：17，3，25，14，

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

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

14、間按照第一個(gè)元素（即基準(zhǔn)元素）的排序碼分為左右兩個(gè)子序列的過(guò)程叫做一次劃分。設(shè)待排序序列為arraystartarrayend，其中start為下限，end為上限，startend，mid=arraystart為該序列的基準(zhǔn)元素，為了實(shí)現(xiàn)一次劃分，令i,j的初值分別為start和end。在劃分過(guò)程中，首先讓j從它的初值開(kāi)始，依次向前取值，并將每一元素arrayj的排序碼同mid的排序碼進(jìn)行比較，直到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-; /一次劃分得到基準(zhǔn)值的正確位置 arrayi=mid; quicksort(array,start,i-1); /遞歸調(diào)用左子區(qū)間 quicksort(array,i+1,end); /遞歸調(diào)用右子區(qū)間3快速排序的效率分析若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長(zhǎng)度大致相等），則結(jié)點(diǎn)數(shù)n與二叉樹(shù)深度h應(yīng)滿足log2nhlog2n+1 ，所以總的比較次數(shù)不會(huì)超過(guò)(n+1) log2n。因此，快速排序的最好時(shí)間復(fù)雜度應(yīng)為O（nlog2n）。而且在理論上已

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

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

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

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

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

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

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

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

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

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

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

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

28、0 被稱為 “最主”位關(guān)鍵字Kd-1 被稱為 “最次”位關(guān)鍵字 對(duì)于序列中任意兩個(gè)記錄 Ri 和 Rj(1ijn) 都滿足下列(詞典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1) 實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)先LSD法最高位優(yōu)先MSD法 先對(duì)K0進(jìn)行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對(duì) K1 進(jìn)行排序，.， 依次類推，直至最后對(duì)最次位關(guān)鍵字排序完成為止。 先對(duì) Kd-1 進(jìn)行排序，然后對(duì) Kd-2 進(jìn)行排序，依次類推，直至對(duì)最主位關(guān)鍵字 K0 排序完成為止。 排序過(guò)程中不需要根據(jù) “前一個(gè)” 關(guān)鍵字的排序結(jié)果，將記

29、錄序列分割成若干個(gè)(“前一個(gè)”關(guān)鍵字不同的)子序列。例如:學(xué)生記錄含三個(gè)關(guān)鍵字:系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。 無(wú)序序列對(duì)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的排序過(guò)程如下:二、鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時(shí)，可以采用“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。對(duì)于數(shù)字

30、型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。例如：對(duì)下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個(gè)位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集” 在一起； 然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“收集” 在一起；最后按其“百位數(shù)”重復(fù)一遍上述操作。在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)

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