數(shù)據(jù)結構(第10章排序)

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

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

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

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

）按關鍵字有序，即滿足：

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

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

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

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

類型的變量L來表示待排記錄序列，即把待排記錄序列放在L的r數(shù)組中，r[0]空閑或作哨兵，length成員存放記錄個數(shù).⑶有時我們用R(K)表示關鍵字為K的記錄，R(K)表示另一個關鍵字為K的記錄。10.2插入排序一、直接插入排序直接插入排序的基本思想是：把數(shù)組L.r中的待排序的n個記錄看成一個有序表和一個無序表，開始時有序表只包含r[1]，無序表包含r[2]～r[n]。接下來反復地做這樣一件事：從無序表中取出第一個記錄，把它插入到有序表的適當位置，使之成為新的有序表。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個記錄的序列進行排序需要n-1趟。

下面對第i趟的插入過程做進一步的分析。

直接插入排序第i趟的任務是把r[i+1]插入有序表r[1]～r[i]中的適當位置，使之成為新的有序表。怎么完成呢？①把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下面對剛才的例子進行第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]; //設置哨兵

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];//復制為哨兵

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

由此可以推斷，當待排序的記錄序列基本有序時，直接插入排序法會有較高的時間效率。綜合以上分析，我們有如下結論：⑴直接插入排序法的時間復雜度為O(n2)；⑵直接插入排序法的空間復雜度為O(1)；⑷直接插入排序法在序列基本有序或n較小時具有較好性能。⑶直接插入排序法是穩(wěn)定的排序方法；直接插入排序10.2插入排序二、折半插入排序折半插入排序也需要n-1趟。第i趟的任務也是把r[i+1]插入有序表r[1]～r[i]中的適當位置，使之成為新的有序表。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例一、用折半插入排序法對于如下序列排序。假設經(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;//設置初始查找區(qū)間

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

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

}

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

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

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

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

，dt}

，其中，

d1>d2>…>dt，dt=1

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

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

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

，若出現(xiàn)逆序即r[j]>r[j+1]，則進行交換。如此重復，直到某趟中無逆序出現(xiàn)，或者n-1趟排序完成為止。例一、用起泡排序法對下面序列排序。k012…nL.rR1R2…Rn初始關鍵字49133865977627493813496597762749381349659776274938134965977627493813496576972749389749657613274938274965761397493827496597134997第一趟冒泡排序中間過程第一趟排序2749657613499738第二趟排序49496513277638第三趟排序654913274938第四趟排序1327494938第五趟排序27384913273813第六趟排序起泡排序?qū)τ凇罢颉钡某跏夹蛄校鹋菖判蛑恍枰惶伺判?，進行n-1次比較，0次記錄交換。但是，對于“逆序”的初始序列，起泡排序要進行n-1趟，共進行n(n-1)/2次關鍵字比較，和同數(shù)量級的記錄交換。因此，起泡排序法的時間復雜度為O(n2)。下面對起泡排序法的性能進行分析。顯然，比較和交換記錄是基本操作。下面來考慮兩種極端情況。k01234L.rR(60)R(53)R(28)R(5)k01234L.rR(5)R(28)R(53)R(60)10.3快速排序二、快速排序假設初始序列如右圖，快速排序的思想如下：k012…nL.rR1R2…Rn這樣一來，序列就變成了下圖的樣子。它以某個位置i處的記錄R1為界，被劃分成了兩部分，左半部分記錄均≤R1，右半部分記錄均≥R1。選擇一個記錄（比如R1）作為標尺；根據(jù)標尺對記錄進行重排。凡是比R1小的記錄都放在R1的左面,凡是比R1大的記錄都放在R1的右面。k012…i-1ii+1…nL.rRk1Rk2…Rki+1R1Rki+1…Rkn這個過程稱為一次劃分或一趟快速排序。標尺被稱為樞軸記錄或支點，樞軸記錄的關鍵字常稱為pivotkey?？梢钥闯?，通過一趟快速排序，也使得樞軸記錄找到了自己的最終位置。接下來，應分別對左半部分、右半部分繼續(xù)進行劃分，如此重復，直到每一部分僅包含一個記錄為止?？焖倥判蛳旅嬗懻撘淮蝿澐值木唧w做法。假設待劃分的部分為：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所指的記錄起向前搜索，直到第一個關鍵字＜pivotkey的記錄，并將該記錄移動到low所指位置；再從low所指的記錄起向后搜索，直到第一個關鍵字＞pivotkey的記錄，并將該記錄移動到high所指位置。如此重復，直到low=high為止。⑸把樞軸記錄復制到low所指位置。k012345678L.r4938659776132749下面通過例子來說明如何進行一趟快速排序。初始關鍵字49prikey一次交換二次交換三次交換四次交換完成一趟排序lowhigh4913386597762749652713389776492713389776496527381397766549279738137665492797381376654949lowlowhighhighlowhighhighlowhighlowhighhighlow快速排序根據(jù)上述分析，可以寫出一次劃分的算法。(P274算法10.6b)int

Partition(SqList&L,ints,intt){

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

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向左掃描向右掃描快速排序由剛才的例子可知，對上面的待排序列進行一次劃分后，序列變成了：k012345678L.r4938659776132749首次劃分結果：2738134976976549接下來，我們應再對這兩部分分別進行快速排序，直到每一部分僅包含一個記錄為止。132738497697654913273849496576971327384949657697最后結果：1327384949657697綜上所述，對整個初始序列進行快速排序，就是先用一次劃分將整個序列一分為二，然后分別對左子表、右子表進行劃分，…，直到每一部分只包含一個記錄為止?？焖倥判蚋鶕?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)。實際應用表明，就平均時間而言，快速排序被認為是最好的內(nèi)部排序方法。但是，關于快速排序還要注意以下幾點：當初始序列為基本有序時，快速排序就蛻化為起泡排序?？焖倥判虿环€(wěn)定，例如{R(20)，R(10)，R(10)}。與其他排序法相比，快速排序需要額外的?？臻g，空間復雜度為O(logn)。例三、用快速排序法對序列(18，5，23，40，13，9)排序，要求寫出每次劃分后的結果和最后結果。{9，5，13}，18，{40，23}{5}，9，{13}{23}，40最后結果：

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

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

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

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

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

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

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

由此可見，樹形選擇排序在進行第i趟時，由于充分利用了其它趟的比較結果，使得效率得以提高。但是它也有缺點，需要較多的輔助空間來保存中間結果。于是，人們又提出了改進方案即堆排序，堆排序的時間復雜度依然為O(nlog2n)，但只需一個記錄大小的輔助空間。10.4選擇排序三、堆排序則稱之為堆。進一步地，前一種稱為小頂堆，后一種稱為大頂堆。為了介紹堆排序，先來復習一下完全二叉樹的知識?；蛘咭粋€序列（k1，k2，…，kn），如果滿足：一棵有n個結點的二叉樹，如果它與同深度的滿二叉樹的前n個結點一一對應，則該二叉樹被稱為完全二叉樹。完全二叉樹非常適于用順序存儲表示，方法是按照層序依次將結點存放在數(shù)組中。這樣一來，每個完全二叉樹對應一個序列。另外，有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)如果把這樣一個序列，看成是某個完全二叉樹所對應的序列，那么這棵二叉樹畫出來如右圖所示。96832738119所有大頂堆對應的二叉樹都具有此特點。由此聯(lián)想到，如果從一個無序序列所對應的二叉樹出發(fā)，通過某些操作把它調(diào)整成一個大頂堆的話，則堆頂記錄即為最大值。另外，在輸出了最大值之后，如果能將剩下的n-1個記錄調(diào)整成一個新堆的話，則堆頂記錄即為次大值。如此反復，就能得到一個有序序列，這個過程稱為堆排序。不難看出，它具有如下特點：

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

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

另外，堆排序的時間復雜度為O(nlog2n)，即使在初始序列基本有序情況下也是如此，而快速排序此時為O(n2)。如此重復，直到堆中只剩一個記錄為止。1327384949657697堆排序適宜記錄較多的文件10.5歸并排序因此，歸并操作的時間復雜度為O(m+n)，空間復雜度為O(m+n)。歸并排序是利用歸并操作完成的。歸并操作的功能在于將兩個有序表合并為一個更長的有序表。下面以順序存儲結構為例，回顧一下歸并操作。由此可以看出，若兩個有序表的長度分別為m、n，為了把它們歸并為一個有序表，需要大約進行m+n次比較和m+n次記錄移動，另外還需要m+n個記錄的輔助空間來存放歸并結果。如果把歸并操作的思想用于排序，就形成了歸并排序方法。012301234a13911b28101416012345678c123891011141610.5歸并排序在經(jīng)過了3趟歸并排序之后，就得到了有序序列。一般地，若待排序的記錄序列長度為n，則需要進行┌l(fā)og2n┐趟。由于在每趟歸并排序中，需要比較n次，所以歸并排序的時間復雜度為O(nlog2n)。下面通過例子來加以說明。假設待排序的記錄序列如下，由于每個記錄可看成是長度為1的有序子序列，所以，可以對它們進行兩兩歸并。由于在進行歸并排序時，需要長度為n的數(shù)組暫存每一趟的歸并結果，所以歸并排序的空間復雜度為O(n)。49，38，65，97，76，13，2738，4965，9713，7627第1趟后結果38，49，65，9713，27，76第2趟后結果13，27，38，49，65，76，97第3趟后結果10.5歸并排序由前面的例子可以看出，當用歸并排序?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鍵字為278，109，013，930，589，184，505，269，018，083或者為WORK，HEAD，F(xiàn)OUR，TEAM，BELL，…的記錄序列，除了用前面介紹的各種排序方法外，使用基數(shù)排序法可能會得到更高的效率。下面首先來分析這些關鍵字序列的特點?；鶖?shù)排序是一種按組成關鍵字的各位進行排序的方法。每個關鍵字由d位組成，其中k1為最高關鍵字位，kd為最低位。k1k2…kd各位的地位不同，當比較兩個關鍵字時，是從最高位起開始比較,若相同則比較下一位，…，直到最低位。

k1～kd有同樣的取值范圍，如第1個序列為0～9，共10個數(shù)，這個10稱為基數(shù)，基數(shù)常用rd表示。對這種記錄序列的排序有兩種思路。10.6基數(shù)排序下面以關鍵字序列278，109，013，930，589，184，505，269，018，083為例加以說明，此時d=3，rd=10。一、最高位優(yōu)先法(MSD)0123456789278109013930589184505269018083⑴按最高關鍵字位即百位將記錄分堆，每堆內(nèi)記錄的關鍵字具有相同的百位。⑵在每堆中，再按十位分成10個子堆，每個子堆內(nèi)具有相同的十位。0123456789013018083⑶在每個子堆中，再按個位分堆。012345678901301810.6基數(shù)排序0…90…9至此，如果把最下層中的記錄按順序排列起來，就得到了有序序列?？梢钥闯?，MSD是按關鍵字位逐層分成若干子堆，而每堆的排序是獨立進行的。0…90…90…9…………0…90…9……按k1按k210.6基數(shù)排序下面以關鍵字序列278，109，013，930，589，184，505，269，018，083為例加以說明，此時d=3，rd=10。二、最低位優(yōu)先法(LSD)0123456789278109013930589184505269018083⑴按最低關鍵字位即個位將記錄分成若干堆，每堆內(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方法是一個分配和收集交替進行的過程，分配和收集的次數(shù)取決于關鍵字的位數(shù)d。10.6基數(shù)排序基數(shù)排序法就是基于LSD原理實現(xiàn)的。在基數(shù)排序法中，待排記錄序列保存在靜態(tài)鏈表中；需要進行d次分配與收集工作;

為了記錄分配結果，建立了rd個鏈隊列，f[i]、e[i]分別表示第i個隊列的隊頭、隊尾指針。下面結合P287圖10.14的例子來介紹基數(shù)排序法。在本例中，由于每個關鍵字有d=3位，所以要進行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]