數(shù)據(jù)結(jié)構(gòu)(第10章排序)

第10章內(nèi)部排序排序是數(shù)據(jù)處理中經(jīng)常用到的操作，先來給出排序的定義。通常我們把按關(guān)鍵字遞增有序的序列稱為正序序列，把按關(guān)鍵字遞減有序的序列稱為逆序序列。如果不特別聲明，今后我們說的有序均是指正序。

需要注意的是，在上述定義中，關(guān)鍵字既可以是主關(guān)鍵字，也可以是次關(guān)鍵字。如果是主關(guān)鍵字，則不管對序列采用哪種排序方法，排序的結(jié)果是唯一的。

如果是次關(guān)鍵字，由于可能多個記錄具有相同的關(guān)鍵字，這時對序列采用不同的排序方法，得到的排序結(jié)果可能不相同。

如果一種排序方法可以保證關(guān)鍵字相同的記錄在排序前后的相對次序保持不變，則稱此排序方法是穩(wěn)定的；否則稱為不穩(wěn)定的.假設(shè)有一個記錄序列（R1，R2，…，Rn），Ki為Ri的關(guān)鍵字,所謂排序就是要確定1、2、…、n的一種排列i1、i2、…、in，使得（Ri1，Ri2，…，Rin

）按關(guān)鍵字有序，即滿足：

Ki1≤Ki2≤…≤Kin第10章內(nèi)部排序根據(jù)排序過程中涉及的存儲器類型，排序方法分為兩大類：

為了描述方便起見，特做如下約定（參見P264）：在本章中，我們將研究各種內(nèi)部排序方法。內(nèi)部排序方法有許多種，從排序原理的角度看，可以分為以下幾大類：如果記錄數(shù)量很大，以致于內(nèi)存無法容納所有待排序記錄，必須借助于外存進(jìn)行排序，這種排序稱為外部排序。如果內(nèi)存可以容納所有待排序記錄，排序過程只涉及內(nèi)存，這種排序稱為內(nèi)部排序。

①插入排序 ②交換排序 ③選擇排序④歸并排序 ⑤基數(shù)排序

這些不同類型的方法都有自己的適用范圍，各有優(yōu)缺點(diǎn)。⑴假設(shè)關(guān)鍵字均為整數(shù)，每個記錄由關(guān)鍵字域和其他域組成。⑵用SqList

類型的變量L來表示待排記錄序列，即把待排記錄序列放在L的r數(shù)組中，r[0]空閑或作哨兵，length成員存放記錄個數(shù).⑶有時我們用R(K)表示關(guān)鍵字為K的記錄，R(K)表示另一個關(guān)鍵字為K的記錄。10.2插入排序一、直接插入排序直接插入排序的基本思想是：把數(shù)組L.r中的待排序的n個記錄看成一個有序表和一個無序表，開始時有序表只包含r[1]，無序表包含r[2]～r[n]。接下來反復(fù)地做這樣一件事：從無序表中取出第一個記錄，把它插入到有序表的適當(dāng)位置，使之成為新的有序表。k01234567L.rR(13)R(5)R(65)R(27)R(97)R(49)R(38)k01234567L.rR(5)R(65)R(27)R(97)R(49)R(38)R(13)這樣經(jīng)過n-1次插入后，無序表成為空表，有序表中就包含了全部記錄。我們把每次插入一個記錄的過程稱為一趟排序。顯然，用直接插入排序法對有n個記錄的序列進(jìn)行排序需要n-1趟。

下面對第i趟的插入過程做進(jìn)一步的分析。

直接插入排序第i趟的任務(wù)是把r[i+1]插入有序表r[1]～r[i]中的適當(dāng)位置，使之成為新的有序表。怎么完成呢？①把Ri+1暫存到r[0]中。k01…jj+1…ii+1…nL.rR1…Rj…Ri+1Ri-1RiRi+1②從有序表的最后一個記錄r[i]

起，順序向前查找首個≤

Ri+1

的記錄，并且邊比較邊后移記錄。③如果r[j]≤r[0]，則把要插入的記錄Ri+1存儲到r[j+1]。Rj+1下面對剛才的例子進(jìn)行第3、4趟排序。k01234567L.rR(13)R(38)R(49)R(5)R(65)R(27)R(97)直接插入排序完整的排序過程如下：初始序列：[R(49)]，R(38)，R(13)，R(5)，R(65)，R(27)，R(97)i=1：

[R(38)，R(49)]，R(13)，R(5)，R(65)，R(27)，R(97)i=2：

[R(13)，R(38)，R(49)]，R(5)，R(65)，R(27)，R(97)i=3：

[R(5)，R(13)，R(38)，R(49)]，R(65)，R(27)，R(97)i=4：

[R(5)，R(13)，R(38)，R(49)，R(65)]，R(27)，R(97)i=5：

[R(5)，R(13)，R(27)，R(38)，R(49)，R(65)]，R(97)i=6：

[R(5)，R(13)，R(27)，R(38)，R(49)，R(65)，R(97)]直接插入排序根據(jù)上面的討論，我們可以寫出直接插入排序的算法。voidInsertSort(SqList&L){

for(i=1;i<L.length;i++){//i代表趟號

L.r[0]=L.r[i+1]; //設(shè)置哨兵

for(j=i;L.r[j].key>L.r[0].key);j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}//InsertSortk01234567L.rR(5)R(13)R(38)R(49)R(65)R(27)R(97)voidInsertSort(SqList&L){//算法10.1//對順序表L作直接插入排序。

inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){//"<"時，需將L.r[i]插入有序子表

L.r[0]=L.r[i];//復(fù)制為哨兵

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//記錄后移

L.r[j+1]=L.r[0];//插入到正確位置

}}//InsertSort在教材P265算法10.1中，i代表的是要插入的記錄的下標(biāo)，所以從2開始。另外，考慮到要插入的記錄≥有序表中最后一個記錄的情況，算法P265算法10.1做了進(jìn)一步優(yōu)化，增加了if語句。下面對直接插入排序法的性能進(jìn)行分析。顯然，比較和移動記錄操作是基本操作。下面來考慮兩種極端情況。k01234L.rR(60)R(53)R(28)R(5)當(dāng)待排序的記錄序列為逆序序列時，各趟所需比較和移動次數(shù)如下表所示。趟號比較次數(shù)移動次數(shù)123234………n-1nn+2合計此時，總的比較次數(shù)和移動記錄次數(shù)，都分別達(dá)到了最大值。直接插入排序K01234L.rR(5)R(28)R(53)R(60)相反地，當(dāng)待排序的記錄序列為正序序列時，各趟所需比較和移動次數(shù)如下表所示。趟號比較次數(shù)移動次數(shù)110210………n-110合計n-10此時，總的比較次數(shù)和移動記錄次數(shù)，都分別達(dá)到了最小值。

由此可以推斷，當(dāng)待排序的記錄序列基本有序時，直接插入排序法會有較高的時間效率。綜合以上分析，我們有如下結(jié)論：⑴直接插入排序法的時間復(fù)雜度為O(n2)；⑵直接插入排序法的空間復(fù)雜度為O(1)；⑷直接插入排序法在序列基本有序或n較小時具有較好性能。⑶直接插入排序法是穩(wěn)定的排序方法；直接插入排序10.2插入排序二、折半插入排序折半插入排序也需要n-1趟。第i趟的任務(wù)也是把r[i+1]插入有序表r[1]～r[i]中的適當(dāng)位置，使之成為新的有序表。k01234567L.rR(5)R(13)R(38)R(49)R(65)R(27)R(97)但是，與直接插入不同的是，它首先使用折半查找法來確定Ri+1的插入位置，然后再批量移動記錄。k01…jj+1…ii+1…nL.rR1…RjRj+1…RiRi+1例一、用折半插入排序法對于如下序列排序。假設(shè)經(jīng)過前4趟已經(jīng)完成，下面演示第5趟排序。k01234567L.rR(5)R(13)R(38)R(49)R(65)R(27)R(97)折半插入排序根據(jù)上面的討論，我們可以寫出折半插入排序的算法。voidBInsertSort(SqList&L){

for(i=1;i<L.length;i++){//i代表趟號

L.r[0]=L.r[i+1]; //將r[i+1]暫存到r[0]

low=1;high=i;//設(shè)置初始查找區(qū)間

while(low<=high){m=(low+high)/2;if(L.r[0].key<L.r[m].key)high=m-1;//插入點(diǎn)在左半

elselow=m+1;//插入點(diǎn)在右半?yún)^(qū)間

}

for(j=i;j>=high+1;j--)L.r[j+1]=L.r[j];//記錄后移

L.r[high+1]=L.r[0];//記錄存入插入點(diǎn)high+1位置

}}//BInsertSort折半插入法雖然減少了關(guān)鍵字間的比較次數(shù)，但是記錄的移動次數(shù)仍和直接插入法一樣，因此，其時間復(fù)雜度仍為O(n2)。10.2插入排序三、希爾排序直接插入排序在n較小的時候，或在待排序列基本有序的情況下效果不錯。正是基于這兩點(diǎn)，1959年希爾提出了直接插入排序的改進(jìn)方案--希爾排序。

例如，對此例可以設(shè)計增量序列為{5，3，1}。到底怎樣一次次分割待排序列的呢？為此，我們設(shè)計一個遞減的增量序列{d1，d2，…

，dt}

，其中，

d1>d2>…>dt，dt=1

下面結(jié)合例子介紹希爾排序的思想。k012345678910L.r49386597761327495504

希爾排序的主要思想是，把待排的序列分割成若干個子序列，對這些子序列分別進(jìn)行直接插入排序。如此反復(fù)分割若干次，待整個序列變得基本有序時，再對所有記錄進(jìn)行一次直接插入排序。希爾排序⑴首先把待排序記錄分為d1個組，以d1為步長，使下標(biāo)距離為d1的記錄在同一組中，并對每一組記錄分別進(jìn)行直接插入排序。k012345678910L.r[k]49386597761327495504增量序列{5，3，1}k012345678910L.r[k]13493827654997557604至此，完成了第1趟希爾排序。希爾排序⑵在第1趟排序的基礎(chǔ)上，把記錄序列分為d2個組，以d2為步長，使下標(biāo)距離為d2的記錄在同一組中，并對每一組記錄分別進(jìn)行直接插入排序。k012345678910L.r[k]13274955044938659776增量序列{5，3，1}k012345678910L.r[k]13495504654997387627至此，完成了第2趟希爾排序。如此重復(fù)，直到最后一趟。希爾排序⑶最后，在前面排序的基礎(chǔ)上，把記錄序列分為dt個組。由于dt=1,因此，所有記錄被分在一個組中，接下來對所有記錄進(jìn)行直接插入排序。k012345678910L.r[k]13044938274955659776增量序列{5，3，1}k012345678910L.r[k]04132738494955657697至此，希爾排序過程結(jié)束。希爾排序由于巧妙利用了直接插入排序的長處，所以其效率應(yīng)高于直接插入排序，它的時間復(fù)雜度約為O(n1.5)。另外，希爾排序的過程依賴于增量序列的選取，目前尚無最佳的增量序列的設(shè)計方法。最后，希爾排序又稱為縮小增量排序，而且是不穩(wěn)定的。10.2插入排序練習(xí)分別用直接插入排序和希爾排序法對下列關(guān)鍵字進(jìn)行排序，寫出每趟排序結(jié)果，其中希爾排序的增量為（3,1）

{21，25，49，25，16，08}10.3快速排序一、起泡排序本節(jié)主要討論借助于“交換”手段進(jìn)行排序的方法。起泡排序的思想很簡單，它需要進(jìn)行若干趟（不超過n-1趟）。在第i趟中，對于r[1]～r[n-i+1]間的記錄，依次比較相鄰記錄r[j]、r[j+1]

，若出現(xiàn)逆序即r[j]>r[j+1]，則進(jìn)行交換。如此重復(fù)，直到某趟中無逆序出現(xiàn)，或者n-1趟排序完成為止。例一、用起泡排序法對下面序列排序。k012…nL.rR1R2…Rn初始關(guān)鍵字49133865977627493813496597762749381349659776274938134965977627493813496576972749389749657613274938274965761397493827496597134997第一趟冒泡排序中間過程第一趟排序2749657613499738第二趟排序49496513277638第三趟排序654913274938第四趟排序1327494938第五趟排序27384913273813第六趟排序起泡排序?qū)τ凇罢颉钡某跏夹蛄?，起泡排序只需一趟排序，進(jìn)行n-1次比較，0次記錄交換。但是，對于“逆序”的初始序列，起泡排序要進(jìn)行n-1趟，共進(jìn)行n(n-1)/2次關(guān)鍵字比較，和同數(shù)量級的記錄交換。因此，起泡排序法的時間復(fù)雜度為O(n2)。下面對起泡排序法的性能進(jìn)行分析。顯然，比較和交換記錄是基本操作。下面來考慮兩種極端情況。k01234L.rR(60)R(53)R(28)R(5)k01234L.rR(5)R(28)R(53)R(60)10.3快速排序二、快速排序假設(shè)初始序列如右圖，快速排序的思想如下：k012…nL.rR1R2…Rn這樣一來，序列就變成了下圖的樣子。它以某個位置i處的記錄R1為界，被劃分成了兩部分，左半部分記錄均≤R1，右半部分記錄均≥R1。選擇一個記錄（比如R1）作為標(biāo)尺；根據(jù)標(biāo)尺對記錄進(jìn)行重排。凡是比R1小的記錄都放在R1的左面,凡是比R1大的記錄都放在R1的右面。k012…i-1ii+1…nL.rRk1Rk2…Rki+1R1Rki+1…Rkn這個過程稱為一次劃分或一趟快速排序。標(biāo)尺被稱為樞軸記錄或支點(diǎn)，樞軸記錄的關(guān)鍵字常稱為pivotkey?？梢钥闯?，通過一趟快速排序，也使得樞軸記錄找到了自己的最終位置。接下來，應(yīng)分別對左半部分、右半部分繼續(xù)進(jìn)行劃分，如此重復(fù)，直到每一部分僅包含一個記錄為止?？焖倥判蛳旅嬗懻撘淮蝿澐值木唧w做法。假設(shè)待劃分的部分為：k0…ss+1…t-1t…L.r…RksRks+1…Rkt-1Rkt…一次劃分的具體過程如下：

⑴選擇s處的記錄L.r[s]為樞軸記錄，置pivotkey=L.r[s].key。⑵將樞軸記錄暫存到第0個分量。⑶令low=s、high=t，即分別指向待劃分部分的首記錄和尾記錄。⑷從high所指的記錄起向前搜索，直到第一個關(guān)鍵字＜pivotkey的記錄，并將該記錄移動到low所指位置；再從low所指的記錄起向后搜索，直到第一個關(guān)鍵字＞pivotkey的記錄，并將該記錄移動到high所指位置。如此重復(fù)，直到low=high為止。⑸把樞軸記錄復(fù)制到low所指位置。k012345678L.r4938659776132749下面通過例子來說明如何進(jìn)行一趟快速排序。初始關(guān)鍵字49prikey一次交換二次交換三次交換四次交換完成一趟排序lowhigh4913386597762749652713389776492713389776496527381397766549279738137665492797381376654949lowlowhighhighlowhighhighlowhighlowhighhighlow快速排序根據(jù)上述分析，可以寫出一次劃分的算法。(P274算法10.6b)int

Partition(SqList&L,ints,intt){

pivotkey=L.r[s].key;//設(shè)置pivotkeyL.r[0]=L.r[s];//暫存到r[0]low=s;high=t;//設(shè)置首、尾指針

while(low<high){

while(low<high&&L.r[high].key>=pivotkey)--high;

L.r[low]=L.r[high];

while(low<high&&L.r[low]<=pivotkey)++low;

L.r[high]=L.r[low];}

L.r[low]=L.r[0];//把樞軸記錄存到樞軸位置

returnlow;//返回樞軸位置}//Partition向左掃描向右掃描快速排序由剛才的例子可知，對上面的待排序列進(jìn)行一次劃分后，序列變成了：k012345678L.r4938659776132749首次劃分結(jié)果：2738134976976549接下來，我們應(yīng)再對這兩部分分別進(jìn)行快速排序，直到每一部分僅包含一個記錄為止。132738497697654913273849496576971327384949657697最后結(jié)果：1327384949657697綜上所述，對整個初始序列進(jìn)行快速排序，就是先用一次劃分將整個序列一分為二，然后分別對左子表、右子表進(jìn)行劃分，…，直到每一部分只包含一個記錄為止?？焖倥判蚋鶕?jù)上述分析，可以寫出快速排序的算法(P276算法)。voidQSort(SqList&L,ints,intt){

if(s>=t)return;//若區(qū)間長度≤1，不再劃分

pivotloc=Partition(L,s,t);//劃分且得到樞軸位置

QSort(L,s,pivotloc-1);//對左子表繼續(xù)劃分

QSort(L,pivotloc+1,t);//對右子表繼續(xù)劃分}//QSortvoidQuickSort(SqList&L){

QSort(L,1,L.length);//對區(qū)間[1,n]調(diào)用QSort}//QuickSort快速排序理論上已經(jīng)證明，快速排序的平均時間為O(nlogn)。實際應(yīng)用表明，就平均時間而言，快速排序被認(rèn)為是最好的內(nèi)部排序方法。但是，關(guān)于快速排序還要注意以下幾點(diǎn)：當(dāng)初始序列為基本有序時，快速排序就蛻化為起泡排序?？焖倥判虿环€(wěn)定，例如{R(20)，R(10)，R(10)}。與其他排序法相比，快速排序需要額外的?？臻g，空間復(fù)雜度為O(logn)。例三、用快速排序法對序列(18，5，23，40，13，9)排序，要求寫出每次劃分后的結(jié)果和最后結(jié)果。{9，5，13}，18，{40，23}{5}，9，{13}{23}，40最后結(jié)果：

5，9，13，18，23，4010.4選擇排序一、簡單選擇排序第i趟排序是在n-i+1各記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換。若待排記錄序列的長度為n，則簡單選擇排序共需進(jìn)行n-1趟。在進(jìn)行第i趟時，首先從r[i]～r[n]中選取最小的記錄（例如r[j]）,然后把r[i]與r[j]交換。k01…i-1i…j…nL.rR1…Ri-1……RnRi例一、用簡單選擇排序法對下面的序列排序。

Rjk012345678L.r4938659776132749第1趟：1338659776492749第2趟：1327659776493849第3趟：1327389776496549可以看出，在進(jìn)行第i趟時，r[1]～r[i-1]已經(jīng)有序。簡單選擇排序根據(jù)上面的討論，我們可以寫出簡單選擇排序的算法。voidSelectSort(SqList&L){

for(i=1;i<L.length;i++){//i代表趟號

j=i; //選取r[i]~r[n]中的最小記錄r[j]

for(k=i+1;k<=L.length;k++)

if(L.r[k].key<L.r[j].key)j=k;

L.r[i]←→L.r[j];//r[j]與r[i]交換

}}//SelectSort簡單選擇排序下面對簡單選擇排序的性能進(jìn)行分析。容易看出，在簡單選擇排序中，比較和記錄交換是基本操作。趟號比較次數(shù)交換次數(shù)1n-112n-21………n-111合計n-1總之，簡單選擇排序需要交換n-1次記錄，需要比較n(n-1)/2次。因此,該算法的時間復(fù)雜度為O(n2)。另外，簡單選擇排序的空間復(fù)雜度為O(1)，它是不穩(wěn)定的排序方法?，F(xiàn)在來考慮這樣一個問題，即能否對簡單選擇排序加以改進(jìn)呢？由以上分析不難看出，要想改進(jìn)這個算法，就得從減少比較次數(shù)上下功夫。n-1次，第2趟比較了n-2次。實際上，在進(jìn)行第2趟排序時，如果能夠利用第1趟比較所得信息，第2趟就不用比較這么多次。類似地，在進(jìn)行第i趟排序時，如果能夠利用前些趟比較所得信息，那么第i趟的比較次數(shù)就可以減少。

基于這種想法，人們設(shè)計出了樹形選擇排序。在簡單選擇排序中，第1趟比較了10.4選擇排序二、樹形選擇排序若待排記錄序列的長度為n，則樹形選擇排序也需進(jìn)行n-1趟。與簡單選擇排序類似，第1趟選取最小的記錄，第2趟選取次小的記錄，…，下面結(jié)合例子（P280）來介紹。例一、用樹形選擇排序法對下面的序列排序。（49，38，65，97，76，13，27，49）

首先進(jìn)行第1趟，即選取最小的記錄。為此，把待排序記錄都作為最下層的葉子結(jié)點(diǎn)，并將葉子結(jié)點(diǎn)兩兩比較，直到求出最小值,并輸出最小值(13)。13492713769765384938386513271310.4選擇排序二、樹形選擇排序若待排記錄序列的長度為n，則樹形選擇排序也需進(jìn)行n-1趟。與簡單選擇排序類似，第1趟選取最小的記錄，第2趟選取次小的記錄，…，下面結(jié)合例子（P280）來介紹。例一、用樹形選擇排序法對下面的序列排序。（49，38，65，97，76，13，27，49）

然后進(jìn)行第2趟，即選取次小的記錄。為此，只需把最小值葉子結(jié)點(diǎn)(13)用∞代替，重新進(jìn)行比較，而且只需調(diào)整祖先結(jié)點(diǎn)，其他結(jié)點(diǎn)保持不變。274927∞

769765384938386527277610.4選擇排序二、樹形選擇排序若待排記錄序列的長度為n，則樹形選擇排序也需進(jìn)行n-1趟。與簡單選擇排序類似，第1趟選取最小的記錄，第2趟選取次小的記錄，…，下面結(jié)合例子（P280）來介紹。例一、用樹形選擇排序法對下面的序列排序。（49，38，65，97，76，13，27，49）

接下來進(jìn)行第3趟，即選取第3小的記錄。為此，只需把次小葉子結(jié)點(diǎn)(27)用∞代替，重新進(jìn)行比較，且只需調(diào)整祖先結(jié)點(diǎn)，其他結(jié)點(diǎn)保持不變。經(jīng)過n-1趟后，就得到了有序的序列。3849∞∞

7697653849383865494976樹形選擇排序下面對樹形選擇排序的性能進(jìn)行分析。由例子可以看出，除了第1趟求最小記錄外，其它各趟只需比較3次，即樹的高度-1次。由于具有n個葉子結(jié)點(diǎn)的完全二叉樹的高度為┌l(fā)og2n┐+1，所以除第1趟外，其它各趟僅需比較┌l(fā)og2n┐次，因此，樹形選擇排序的時間復(fù)雜度為O(nlog2n)。

由此可見，樹形選擇排序在進(jìn)行第i趟時，由于充分利用了其它趟的比較結(jié)果，使得效率得以提高。但是它也有缺點(diǎn)，需要較多的輔助空間來保存中間結(jié)果。于是，人們又提出了改進(jìn)方案即堆排序，堆排序的時間復(fù)雜度依然為O(nlog2n)，但只需一個記錄大小的輔助空間。10.4選擇排序三、堆排序則稱之為堆。進(jìn)一步地，前一種稱為小頂堆，后一種稱為大頂堆。為了介紹堆排序，先來復(fù)習(xí)一下完全二叉樹的知識。或者一個序列（k1，k2，…，kn），如果滿足：一棵有n個結(jié)點(diǎn)的二叉樹，如果它與同深度的滿二叉樹的前n個結(jié)點(diǎn)一一對應(yīng)，則該二叉樹被稱為完全二叉樹。完全二叉樹非常適于用順序存儲表示，方法是按照層序依次將結(jié)點(diǎn)存放在數(shù)組中。這樣一來，每個完全二叉樹對應(yīng)一個序列。另外，有n個葉子結(jié)點(diǎn)的完全二叉樹的高度為┌l(fā)og2n┐+1。

小頂堆：(12，36，24，85，47，30，53，91)

大頂堆：(96，83，27，38，11，9)堆排序

小頂堆：(12，36，24，85，47，30，53，91)

大頂堆：(96，83，27，38，11，9)如果把這樣一個序列，看成是某個完全二叉樹所對應(yīng)的序列，那么這棵二叉樹畫出來如右圖所示。96832738119所有大頂堆對應(yīng)的二叉樹都具有此特點(diǎn)。由此聯(lián)想到，如果從一個無序序列所對應(yīng)的二叉樹出發(fā)，通過某些操作把它調(diào)整成一個大頂堆的話，則堆頂記錄即為最大值。另外，在輸出了最大值之后，如果能將剩下的n-1個記錄調(diào)整成一個新堆的話，則堆頂記錄即為次大值。如此反復(fù)，就能得到一個有序序列，這個過程稱為堆排序。不難看出，它具有如下特點(diǎn)：

任一分支結(jié)點(diǎn)的值≥其左、右孩子的值；左、右子樹仍為大頂堆；堆頂記錄就是序列中的最大值。堆排序具體地說，堆排序的操作步驟如下（為了保證輸出序列為按關(guān)鍵字非遞減有序，采用大頂堆排序）：⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。例一、用堆排序法對下面的序列排序。k012345678L.r4938659776132749它所對應(yīng)的二叉樹如右上圖所示。4938659776132749

如何由此二叉樹出發(fā)得到一個大頂堆呢？由于大頂堆要求結(jié)點(diǎn)的值≥其左、右孩子的值，為此需要依次對每個分支結(jié)點(diǎn)進(jìn)行自上而下的調(diào)整。堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。①首先從從i=L.length/2開始，自底向上構(gòu)建大頂堆k012345678L.r493865977613274949386549977613274938654997761327初始排序碼集合49386549977613274938654997761327i=4時的局部調(diào)整49386549977613274938654997761327堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。①首先從從i=L.length/2開始，自底向上構(gòu)建大頂堆k012345678L.r493865977613274949386549977613274938654997761327i=3時的局部調(diào)整49386549977613274938654997761327堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。①首先從從i=L.length/2開始，自底向上構(gòu)建大頂堆k012345678L.r4938659776132749i=2時的局部調(diào)整4938654997761327493865499776132749976549387613274997653849761327堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。①首先從從i=L.length/2開始，自底向上構(gòu)建大根堆k012345678L.r493865977613274997766538494913274997653849761327i=1時的局部調(diào)整9749653849761327堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。②接下來把堆頂記錄97與堆中最后一個記錄38交換，這樣97找到了它的最終位置。766549491327L.r3876654949132797①首先從最后一個分支結(jié)點(diǎn)97開始，自底向上構(gòu)建大根堆4938659776132749k012345678L.r4938659776132749L.r97766549491327389738堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。④接下來把堆頂記錄76與堆中最后一個記錄27交換，這樣76找到了它的最終位置。3876654949132797L.r2749653849137697③為了把剩下的n-1個記錄調(diào)整為新的大頂堆，下面從堆頂開始進(jìn)行自上而下的調(diào)整，調(diào)整后的大頂堆如圖所示。L.r76496538491327977627L.r3876654949132797496538491397堆排序⑴把待排記錄序列調(diào)整成一個大頂堆；⑵把堆頂記錄與堆中最后一個記錄交換；⑶將剩下的記錄調(diào)整為新的大頂堆；⑷重復(fù)⑵、⑶，直到堆中只剩一個記錄為止。⑥接下來把堆頂記錄65與堆中最后一個記錄13交換，這樣65找到了它的最終位置。2749653849137697L.r1349273849657697⑤為了把剩下的n-2個記錄調(diào)整為新的大頂堆，下面從堆頂開始進(jìn)行自上而下的調(diào)整，調(diào)整后的大頂堆如圖所示。L.r65492738491376976513492738497697L.r2749653849137697堆排序L.r1327384949657697我們把自根到葉子結(jié)點(diǎn)的調(diào)整過程稱為篩選。由于在每次篩選過程中，僅需一個輔助記錄單元來完成記錄交換,所以，堆排序的空間復(fù)雜度為O(1)。

另外，堆排序的時間復(fù)雜度為O(nlog2n)，即使在初始序列基本有序情況下也是如此，而快速排序此時為O(n2)。如此重復(fù)，直到堆中只剩一個記錄為止。1327384949657697堆排序適宜記錄較多的文件10.5歸并排序因此，歸并操作的時間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(m+n)。歸并排序是利用歸并操作完成的。歸并操作的功能在于將兩個有序表合并為一個更長的有序表。下面以順序存儲結(jié)構(gòu)為例，回顧一下歸并操作。由此可以看出，若兩個有序表的長度分別為m、n，為了把它們歸并為一個有序表，需要大約進(jìn)行m+n次比較和m+n次記錄移動，另外還需要m+n個記錄的輔助空間來存放歸并結(jié)果。如果把歸并操作的思想用于排序，就形成了歸并排序方法。012301234a13911b28101416012345678c123891011141610.5歸并排序在經(jīng)過了3趟歸并排序之后，就得到了有序序列。一般地，若待排序的記錄序列長度為n，則需要進(jìn)行┌l(fā)og2n┐趟。由于在每趟歸并排序中，需要比較n次，所以歸并排序的時間復(fù)雜度為O(nlog2n)。下面通過例子來加以說明。假設(shè)待排序的記錄序列如下，由于每個記錄可看成是長度為1的有序子序列，所以，可以對它們進(jìn)行兩兩歸并。由于在進(jìn)行歸并排序時，需要長度為n的數(shù)組暫存每一趟的歸并結(jié)果，所以歸并排序的空間復(fù)雜度為O(n)。49，38，65，97，76，13，2738，4965，9713，7627第1趟后結(jié)果38，49，65，9713，27，76第2趟后結(jié)果13，27，38，49，65，76，97第3趟后結(jié)果10.5歸并排序由前面的例子可以看出，當(dāng)用歸并排序?qū)ο旅娴男蛄信判驎r，k012…n-1nL.rR1R2…Rn-1Rn其核心操作是把數(shù)組L.r中前后相鄰的兩個有序序列（如r[s]～r[m]與r[m+1]～r[t]）歸并為一個有序序列，P284算法10.12給出了該操作的實現(xiàn)算法Merge。k0…s…mm+1…t…L.r…Rs…RmRm+1…Rt…利用Merge函數(shù)，可以寫出歸并排序的完整算法，參見P284算法10.13和算法10.14。雖然快速排序、堆排序、歸并排序的平均時間均為O(nlog2n)，但是，只有歸并排序是穩(wěn)定的排序方法。10.6基數(shù)排序?qū)τ陉P(guān)鍵字為278，109，013，930，589，184，505，269，018，083或者為WORK，HEAD，F(xiàn)OUR，TEAM，BELL，…的記錄序列，除了用前面介紹的各種排序方法外，使用基數(shù)排序法可能會得到更高的效率。下面首先來分析這些關(guān)鍵字序列的特點(diǎn)。基數(shù)排序是一種按組成關(guān)鍵字的各位進(jìn)行排序的方法。每個關(guān)鍵字由d位組成，其中k1為最高關(guān)鍵字位，kd為最低位。k1k2…kd各位的地位不同，當(dāng)比較兩個關(guān)鍵字時，是從最高位起開始比較,若相同則比較下一位，…，直到最低位。

k1～kd有同樣的取值范圍，如第1個序列為0～9，共10個數(shù)，這個10稱為基數(shù)，基數(shù)常用rd表示。對這種記錄序列的排序有兩種思路。10.6基數(shù)排序下面以關(guān)鍵字序列278，109，013，930，589，184，505，269，018，083為例加以說明，此時d=3，rd=10。一、最高位優(yōu)先法(MSD)0123456789278109013930589184505269018083⑴按最高關(guān)鍵字位即百位將記錄分堆，每堆內(nèi)記錄的關(guān)鍵字具有相同的百位。⑵在每堆中，再按十位分成10個子堆，每個子堆內(nèi)具有相同的十位。0123456789013018083⑶在每個子堆中，再按個位分堆。012345678901301810.6基數(shù)排序0…90…9至此，如果把最下層中的記錄按順序排列起來，就得到了有序序列。可以看出，MSD是按關(guān)鍵字位逐層分成若干子堆，而每堆的排序是獨(dú)立進(jìn)行的。0…90…90…9…………0…90…9……按k1按k210.6基數(shù)排序下面以關(guān)鍵字序列278，109，013，930，589，184，505，269，018，083為例加以說明，此時d=3，rd=10。二、最低位優(yōu)先法(LSD)0123456789278109013930589184505269018083⑴按最低關(guān)鍵字位即個位將記錄分成若干堆，每堆內(nèi)具有相同的個位.⑵按順序?qū)⒏鞫褦?shù)據(jù)收集在一起，得到：⑶將新序列按十位分成若干堆，每堆內(nèi)具有相同的十位。930，013，083，184，505，278，018，109，589，2690123456789278109013930589184505269018083⑷按順序?qū)⒏鞫褦?shù)據(jù)收集在一起，得到：505，109，013，018，930，269，278，083，184，58910.6基數(shù)排序⑸將新序列按百位分成若干堆，每堆內(nèi)具有相同的百位。0123456789278109013930589184505269018083⑹按順序?qū)⒏鞫褦?shù)據(jù)收集在一起，得到：013，018，083，109，184，269，278，505，589，930505，109，013，018，930，269，278，083，184，589至此，得到的序列就是有序序列。

由此可以看出，LSD方法是一個分配和收集交替進(jìn)行的過程，分配和收集的次數(shù)取決于關(guān)鍵字的位數(shù)d。10.6基數(shù)排序基數(shù)排序法就是基于LSD原理實現(xiàn)的。在基數(shù)排序法中，待排記錄序列保存在靜態(tài)鏈表中；需要進(jìn)行d次分配與收集工作;

為了記錄分配結(jié)果，建立了rd個鏈隊列，f[i]、e[i]分別表示第i個隊列的隊頭、隊尾指針。下面結(jié)合P287圖10.14的例子來介紹基數(shù)排序法。在本例中，由于每個關(guān)鍵字有d=3位，所以要進(jìn)行3次分配與收集工作，又因為基數(shù)rd=10，所以需要建立10個鏈隊列。例：初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]