《數(shù)據(jù)結(jié)構(gòu)》課件第9章

第9章排序9.1排序的基本概念9.2插入排序9.3交換排序9.4選擇排序9.5歸井排序9.6基數(shù)排序9.7排序算法本章小結(jié)習(xí)題九實訓(xùn)9-1內(nèi)部排序算法時間復(fù)雜度分析實訓(xùn)9-2排序算法的應(yīng)用

【教學(xué)目標】通過對本章的學(xué)習(xí)，要求掌握排序的基本概念；熟練掌握直接插入排序、直接選擇排序、冒泡排序、快速排序，掌握希爾排序、堆排序、歸并排序、基數(shù)排序的基本思想、排序過程及實現(xiàn)算法；了解各種排序方法的穩(wěn)定性與時間復(fù)雜度。排序(Sorting)是計算機程序設(shè)計中的一種重要操作，也是日常生活中經(jīng)常遇到的問題，如高考錄取按總分從高到低進行，奧運跨欄決賽按成績由快到慢排定名次，都是按某種次序進行的。排序就是將一組無序的序列按指定的關(guān)鍵字重新排列成一個有序的序列。排序的方法很多，本章只介紹一些常用的排序方法及實現(xiàn)算法。9.1排序的基本概念9.1.1排序從上一章的討論中容易看出，為了查找方便，通常希望計算機中的表是按關(guān)鍵字有序的。因為有序的順序表可以采用查找效率較高的折半查找法，其平均查找長度為O(log2n),而無序的順序表只能進行順序查找，其平均查找長度為(n+1)/2。又如建造二叉排序樹的過程本身就是一個排序的過程。例如，表9-1為某班學(xué)生考試情況表，表中每個學(xué)生的情況包括學(xué)號、姓名、三門課的考試成績以及這三門課的平均成績。表9-1學(xué)?習(xí)?成?績?表如果希望按學(xué)號對學(xué)生考試成績表進行排序，則學(xué)號就是其排序關(guān)鍵字；如果希望按考試的平均成績對該表進行排序，則平均成績就是其排序關(guān)鍵字?？梢姡瑪?shù)據(jù)元素序列的排序可以根據(jù)實際需要，選取其任一數(shù)據(jù)項作為排序關(guān)鍵字。所謂排序，就是對于有n個記錄的序列：{R1，R2，…，Rn}其相應(yīng)關(guān)鍵字的序列是：{K1，K2，…，Kn}通過排序，找出當(dāng)前下標序列為1，2，…，n的一種排列p1，p2，…，pn，使得相應(yīng)關(guān)鍵字滿足如下的非遞減(或非遞增)關(guān)系，即：Kp1≤Kp2≤…≤Kpn這樣就得到一個按關(guān)鍵字有序的記錄序列：{Rp1，Rp2，…，Rpn}9.1.2穩(wěn)定排序與不穩(wěn)定排序假定待排序的序列中存在多個記錄具有相同的鍵值。若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即對任意兩個鍵值相同的記錄在無序序列中Ki=Kj，且i＜j，而在排序后的序列中Ri仍在Rj之前，則稱這種排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。無論是穩(wěn)定排序還是不穩(wěn)定排序，均能排好序。在應(yīng)用排序的某些場合，如選舉和比賽等，對排序的穩(wěn)定性是有特殊要求的。需要強調(diào)的是，證明一種排序方法是穩(wěn)定的，要從算法本身的步驟中加以證明，而證明排序方法是不穩(wěn)定的，只需給出一個反例說明即可。例如，一組記錄對應(yīng)的關(guān)鍵字序列為(2，27，36，8，6，8*)，可以看出，關(guān)鍵字8的記錄有兩個(第二個加*以示區(qū)別)。若采用一種排序方法得到結(jié)果序列(2，6，8，8*，27，36)，那么這種排序方法是穩(wěn)定的；若采用另一種排序方法得到結(jié)果序列(2，6，8*，8，27，36)，那么這種排序方法是不穩(wěn)定的。9.1.3內(nèi)部排序和外部排序根據(jù)排序過程中所使用的存儲設(shè)備的不同，排序可以分成內(nèi)部排序(InternalSorting)和外部排序(ExternalSorting)兩大類。內(nèi)部排序是指在排序的整個過程中，數(shù)據(jù)全部存放在計算機的內(nèi)存儲器中，并且在內(nèi)存儲器中調(diào)整記錄間的相對位置，在此期間沒有進行內(nèi)、外存儲器的數(shù)據(jù)交換。外部排序是指在排序的過程中，數(shù)據(jù)的主要部分存放在外存儲器上，借助于內(nèi)存儲器逐步調(diào)整記錄之間的相對位置，在這個過程中，需要不斷地在內(nèi)、外存儲器之間進行數(shù)據(jù)的交換。本章僅討論內(nèi)部排序的各種典型方法和算法。內(nèi)部排序的方法有很多，按照采用的策略不同，主要有插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序五類。為了討論方便，假設(shè)待排記錄的關(guān)鍵字均為整數(shù)，且都采用順序存儲，均從數(shù)組中下標為1的位置開始存儲，下標為0的位置存儲監(jiān)視哨，或空閑不用。下面用C語言描述：#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey; /*關(guān)鍵字項*/

OtherTypeother-data; /*其他數(shù)據(jù)項*/}RecordType; /*記錄類型*/typedefstruct{RecordTyper[MAXSIZE+1];

/*r[0]閑置或用作監(jiān)視哨*/intlength; /*順序表長度*/}Sqlist;9.2插入排序插入排序的基本思想是：在一個已排好序的記錄子集的基礎(chǔ)上，每一步將下一個待排序的記錄有序地插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。打撲克牌時的抓牌就是插入排序的一個很好的例子，每抓一張牌，插入到合適位置，直到抓完牌為止，即可得到一個有序序列。常用的插入排序算法有直接插入排序、折半插入排序和希爾排序三種。9.2.1直接插入排序

1.直接插入排序的基本思想直接插入排序(StraightInsertionSort)是一種最基本的插入排序方法，其基本操作是將第i個記錄插入到前面i-1個已排好序的記錄中。具體過程為：將第i個記錄的關(guān)鍵字Ki順次與其前面記錄的關(guān)鍵字Ki-1，Ki-2，…，K1進行比較，將所有關(guān)鍵字大于Ki的記錄依次向后移動一個位置，直到遇見一個關(guān)鍵字小于或者等于Ki的記錄Kj，此時Kj后面必為空位置，將第i個記錄插入空位置即可。完整的直接插入排序是從i?=?2開始的，也就是說，將第1個記錄視為已排好序的單元素子集合，然后將第2個記錄插入到單元素子集合中，i從2循環(huán)到n，即可實現(xiàn)完整的直接插入排序。

2.直接插入排序舉例

例9.1

關(guān)鍵字序列(15，8，27，21，40，27*，48)用直接插入排序的過程如圖9.1所示。圖9.1直接插入排序過程示意圖由此可見，對有n條記錄的序列進行直接插入排序，需重復(fù)以下步驟n-1次：

(1)根據(jù)關(guān)鍵字值的大小，查找插入位置。

(2)插入記錄。

3.直接插入排序算法假設(shè)待排序記錄存放在r[1],r[2],…,r[n]之中，為了提高效率，附設(shè)一個監(jiān)視哨r[0]，使得r[0]始終存放待插入的記錄。監(jiān)視哨的作用有兩個：一是備份待插入的記錄，以便前面關(guān)鍵字較大的記錄后移；二是防止越界。直接插入排序算法用C語言描述如下：voidInsertSort(RecordTyper[],intn)

/*用直接插入排序方法對r[1]，…，r[n-1]進行排序*/{

inti,j

for(i=2;i<=n;i++)

{r[0]=r[i]; /*將待插入記錄存放到r[0]中*/for(j=i-1;r[0].key<r[j].key;j--) /*尋找插入位置*/

r[j+1]=r[j];r[j+1]=r[0]; /*將待插入記錄插入到已排序的序列中*/

}}該算法的要點是：①使用監(jiān)視哨r[0]臨時保存待插入的記錄；②從后往前查找應(yīng)插入的位置；③查找與移動在同一循環(huán)中完成。

4.直接插入排序算法分析從空間角度來看，它只需要一個輔助空間r[0]。從時間耗費角度來看，主要時間耗費在關(guān)鍵字比較和移動元素上。對于一次插入排序，算法中的while循環(huán)的次數(shù)主要取決于待插記錄與前i-1個記錄的關(guān)鍵字的關(guān)系。分兩種情況來考慮：

(1)原始序列中各記錄已經(jīng)按關(guān)鍵字遞增的順序有序排列(順序)。在這種情況下，while循環(huán)次數(shù)為零，因此在一次排序中，關(guān)鍵字的比較次數(shù)為1，記錄的移動次數(shù)為2(r[0]?=?r[i]和r[j?+?1]?=?r[0])，整個序列的排序所需的記錄關(guān)鍵字比較次數(shù)以及記錄的移動次數(shù)分別為比較次數(shù)?=?n-1

移動次數(shù)?=?2(n-1)

(2)原始序列中各記錄按關(guān)鍵字遞減的順序逆序排列(逆序)。在這種情況下，第i次排序時，while的循環(huán)次數(shù)為i，因此關(guān)鍵字的比較次數(shù)為i?+?1，記錄的移動次數(shù)為(i?+?2)，整個序列排序所需的關(guān)鍵字比較次數(shù)以及記錄的移動次數(shù)分別為比較次數(shù)?=?∑(i?+?1)?=?(n-1)(n-2)/2移動次數(shù)?=?∑(i?+?2)?=?(n-1)(n?+?4)/2上述兩種情況是最好和最壞的兩種極端情況?？梢宰C明，原始序列越接近有序，該算法的效率也越高，如果原始序列中各記錄的排列次序是隨機的，則關(guān)鍵字的期望比較次數(shù)和記錄的期望移動次數(shù)均約為n2/4，因此，直接插入排序的時間復(fù)雜度為O(n2)。從算法的空間復(fù)雜度來看，在整個排序過程只需一個記錄的輔助空間，所以其空間復(fù)雜度為O(1)。這種排序方法是穩(wěn)定的。直接插入排序算法簡便，比較適用于待排序記錄數(shù)目較少且基本有序的情況。當(dāng)待排記錄數(shù)目較大時，直接插入排序的性能就不好，為此，可以對直接插入排序做進一步的改進。在直接插入排序法的基礎(chǔ)上，從減少“比較關(guān)鍵字”和“移動記錄”兩種操作的次數(shù)著手來進行改進。9.2.2折半插入排序?qū)τ谥苯硬迦肱判颍趯⒌趇個記錄插入適當(dāng)位置的操作中，首先要在第1個記錄至第i-1個記錄中找到第i個記錄應(yīng)當(dāng)插入的位置。實際上前i-1個記錄已經(jīng)是一個有序表，所以在查找第i個記錄的插入位置時，可以采用“折半查找”方法來實現(xiàn)，用這種方法進行的插入排序稱為折半插入排序(BinaryInsertionSort)。折半插入排序算法用C語言描述如下：voidBinSort(RecordTyper[],intn)/*用折半插入排序方法對r[1]，…，r[n-1]進行排序*/{

intlow,high,mid,i,j

for(i=2;i<=n;++i)

{r[0]=r[i]; /*r[i]暫存在r[0]中*/low=1;high=i-1;while(low<=high) /*確定插入位置*/{

mid=(low+high)/2;if(r[0].key<r[mid].key)

high=mid-1;

else

low=mid+1;

}

for(j=i-1;j>=low;--j)r[j+1]=r[j];

/*記錄依次向后移動*/

r[low]=r[0]; /*插入記錄*/

}}折半插入排序比直接插入排序有效。為確定r[i]的插入位置，最多只需要比較log2i次，總的比較次數(shù)最多為log22?+?log23?+?…?+?log2n?=?log2n!。而log2n!≤nlog2n，因此插入n-1個元素的平均關(guān)鍵字的比較次數(shù)為O(nlog2n)。雖然折半插入排序法與直接插入排序法相比較，改善了算法中比較次數(shù)的數(shù)量級，但其并未改變移動元素的時間耗費，所以折半插入排序的總的時間復(fù)雜度仍然是O(n2)。顯然，折半插入排序的空間復(fù)雜度為O(1)。折半插入排序是一種穩(wěn)定的排序方法。9.2.3希爾排序

1.希爾排序的基本思想希爾排序(Shell’sSort)又稱做縮小增量排序(DiminishingIncrementSort)，是D.L.Shell在1959年提出的一種排序方法。從對直接插入排序的分析得知：

(1)原始序列接近有序，其時間復(fù)雜度可提高至O(n)；

(2)當(dāng)n的值較小時，效率也比較高。希爾排序正是從這兩點分析出發(fā)對直接插入排序進行改進得到的一種插入排序方法。它的基本思想是：把待排序的序列分成若干小組，對同一組內(nèi)的數(shù)據(jù)元素采用直接插入排序方法進行排序，在分組時，始終保證當(dāng)前組的數(shù)據(jù)元素個數(shù)超過前面分組排序時組內(nèi)數(shù)據(jù)元素的個數(shù)，直至最后所有數(shù)據(jù)元素成為一組。一般情況下，具體的作法是：先設(shè)置一個增量h1=

n/2

，將待排序序列中所有間隔為h1的元素放在同一組中，然后對各組內(nèi)元素分別進行直接插入排序；再設(shè)置一個增量h2?=?

h1/2

，將待排序序列中所有間隔為h2的元素放在同一組中進行排序；依此類推，h3=

h2/2

,…,直至hi=1(i=1，2，…，log2n)為止。

2.希爾排序舉例

例9.2

關(guān)鍵字初始序列為(15，27，8，21，40，21*，10，36，30，17，32，25)，采用希爾排序方法，過程如圖9.2所示。圖9.2希爾排序過程示意

3.希爾排序算法及分析進行一趟希爾排序的算法與一趟直接插入排序相比，做了如下修改：前后記錄位置的增量是h，而不是1；r[0]只是暫存單元，而不是監(jiān)視哨。當(dāng)j≤0時，插入位置已找到。希爾排序算法用C語言描述如下：voidShellSort(RecordTyper[],intn)/*用希爾排序方法對r[1],…,r[n]進行排序,r[0]為暫存單元*/{

inti,j,h;

h=n/2; /*增量置初值*/

while(h>0) /*增量為正整數(shù)，其最小值為1*/{

for(i=h+1;i<=n;i++) /*h+1為第一個子序列的第二個元素的下標*/

if(r[i].key<r[i-h].key)

{

r[0]=r[i]; /*備份r[i](不做監(jiān)視哨)*/

for(j=i-h;j>0&&(r[0].key<r[j].key);j=j-h)

r[j+h]=r[j];

r[j+h]=r[0];}

h=h/2; /*減小增量*/

}}希爾排序算法的速度取決于所選增量hi。增量序列的選取到目前為止沒有一個最佳值，但不管hi的值如何選取，最后一個值必須是1，因此，希爾排序算法的時間復(fù)雜度的估算比較復(fù)雜，大量研究說明，希爾排序算法的時間復(fù)雜度在O(nlog2n)～O(n2)之間。希爾排序適合于中等規(guī)模的記錄序列進行排序的情況。由圖9.3可知，希爾排序是一種不穩(wěn)定的排序。9.3交換排序交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，并交換不滿足順序要求的那些偶對，直到全部滿足為止。常用的交換排序算法有冒泡排序和快速排序兩種。9.3.1冒泡排序冒泡排序(BubbleSort)又稱為相鄰比序法，以遞增排序為例，其基本思想是：將相鄰的數(shù)據(jù)元素的關(guān)鍵字進行比較，若前面元素的關(guān)鍵字大于后面元素的關(guān)鍵字，則將它們互換，否則不交換。

例9.3

無序關(guān)鍵字序列(763246805546*)，用冒泡法排序過程如圖9.3所示。由圖9.3可知，n個元素要進行n-1趟排序，但若在一趟排序中相鄰元素進行比較時沒有交換發(fā)生，則可認為已經(jīng)排好序了。圖9.3冒泡排序過程(a)第一趟冒泡排序過程及結(jié)果；(b)各趟冒泡排序結(jié)果冒泡排序算法用C語言描述如下：

voidBubbleSort(RecordTyper[],intn)

/*用冒泡排序法對r[1],…,r[n]進行排序*/

{

int,i,m,flag；

flag=1； /*標志量。交換發(fā)生時為1*/

m=n; /*每趟排出的最大值存放的位置，也就是每趟參與排序的元素個數(shù)*/

while(m>1&&flag){

flag=0；

for(i=1；i<m；i++)

if(r[i].key>r[i+1].key)

{

flag=1；

r[0]=r[i]；

r[i]=r[i+1]；

r[i+1]=r[0]；

} m--;

}}在該函數(shù)中，待排序序列中n個記錄順序存儲在r[1],…,r[n]中，r[0]用作臨時存儲空間，外層for循環(huán)控制排序的執(zhí)行次數(shù)，內(nèi)層for循環(huán)用于控制在一次排序中相鄰記錄的比較和交換。flag為標志量，當(dāng)flag?=?1時，表明在一次排序過程中，至少進行了一次記錄的交換，反之，當(dāng)flag?=?0時，則表明在前次排序過程中，沒有任何記錄交換位置，排序結(jié)束。冒泡排序的時間復(fù)雜度為O(n2)，它是一種穩(wěn)定的排序方法。9.3.2快速排序

1.快速排序的基本思想圖9.4快速排序中表的分割快速排序(QuickSort)是冒泡排序的一種改進方法。其基本思想是：從待排序序列中選取一個記錄T(通?？蛇x第一個記錄)，然后將T的關(guān)鍵字和待排序序列中其余記錄的關(guān)鍵字進行比較，關(guān)鍵字小的記錄移到T的前面，關(guān)鍵字大的記錄移到T的后面。經(jīng)過一趟比較后就將待排序序列分成了兩部分(稱為兩個子表)，T記錄就是這兩個子表的分界線，前面子表中的所有記錄的關(guān)鍵字均不大于T的關(guān)鍵字，而后面子表中的所有記錄的關(guān)鍵字均不小于T的關(guān)鍵字。繼續(xù)對分割后的各子表按上述原則進行分割，直到所有子表只有一個記錄為止，則此時的排序序列就變成了有序表。這個過程如圖9.4所示。圖9.4快速排序中表的分割在對待排序序列或子表進行分割時，可以按如下步驟進行：首先，選取表中的第一個元素(也可選取表中的其它某個元素作為分割表的基準)，并將該元素賦給臨時變量T。然后設(shè)置兩個指針i和j分別指向表的起始與最后的位置。反復(fù)做以下兩種操作：

(1)將j逐漸減小，并逐次比較r(j)與T，直到發(fā)現(xiàn)一個r(j)＜T為止，并將r(j)移到r(i)的位置上。

(2)將i逐漸增大，并逐次比較r(i)與T，直到發(fā)現(xiàn)一個r(i)＞T為止，將r(i)移到r(j)的位置上。上述兩個操作交替進行，直到指針i與j指向同一個位置(即i==j)為止，此時將T移到r(i)的位置上。

2.快速排序舉例

例9.4

關(guān)鍵字值序列為(48,62,35,77,55,14,35,98)，快速排序過程如圖9.5所示。圖9.5快速排序示例(a)一趟快速排序；(b)快速排序全過程

3.快速排序算法及分析快速排序中一趟排序的算法用C語言描述如下：intsplit(RecordTyper[],intm,intn)/*對記錄r[m]，…，r[n]進行分割，返回分界線位置*/{

inti,j；

RecordTypet；

i=m；

j=n；

t=r[i]； /*選擇基準記錄*/

while(i<j)

{while((i<j)&&(r[j].key>=t.key))

/*j從右到左找小于t.key的記錄*/j=j-1；

if(i<j)

/*找到小于t.key的記錄，則進行交換*/{

r[i]=r[j]；

i=i+1；}while((i<j)&&(r[i].key<=t.key))

/*i從左到右找大于t.key的記錄*/

i=i+1；if(i<j) /*找到大于t.key的記錄，則進行交換*/{ r[j]=r[i]；

j=j-1；

}}

r[i]=t；/*將基準記錄保存到i=j的位置*/

return(i)；/*返回基準記錄的位置*/}快速排序算法用C語言描述如下：voidQkSort(RecordTyper[],intm,intn,)/*對記錄r[m],…,r[n]用快速排序算法進行排序*/{inti；

if(m<n)/*子表不空*/

{

i=split(r,m,n)； /*分割*/QkSort(r,m,i–1)； /*對前面子表進行快速排序*/QkSort(r,i+1,n)； /*對后面子表進行快速排序*/

}}在冒泡排序中，記錄的比較和交換是在相鄰的單元中進行的，記錄每次交換只能上移或下移一個位置，故總的比較和移動次數(shù)較多。而在快速排序中，記錄的比較和交換是從兩端向中間進行的，當(dāng)前記錄“總是和與它相距最遠的且沒有比較過的記錄”相比較，記錄移動的距離較遠，故可減少總的比較次數(shù)和移動次數(shù)。快速排序的平均時間復(fù)雜度為O(nlog2n)。但是若初始記錄序列按關(guān)鍵字有序或基本有序時，快速排序?qū)⑼懽優(yōu)槊芭菖判?，其時間復(fù)雜度為O(n2)。當(dāng)n較大時，快速排序是目前為止在平均情況下速度最快的一種排序方法。它是一種不穩(wěn)定的排序方法。9.4選擇排序選擇排序的基本思想是：每步從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排序的記錄序列的最后，直到全部排完為止。選擇排序算法最常用的有兩種：直接選擇排序和堆排序。9.4.1直接選擇排序直接選擇排序(StraightSelectionSort)是一種最簡單的排序方法。它的基本思想是：首先在待排序的所有記錄中選出關(guān)鍵字最小的記錄，把它與第一個記錄進行交換，然后在其余的記錄中再選出關(guān)鍵字最小的記錄與第二個記錄進行交換。依此類推，直至所有記錄排序完成。有n個數(shù)據(jù)元素，必須要重復(fù)n-1趟選擇，其中第i(i?=?1,2,…,n-1)趟選擇過程如下：

(1)在待排序序列(r[i]，…，r[n])中選擇關(guān)鍵字最小的元素r[k]。

(2)?r[k]與待排序序列的第一個元素r[i]交換位置。

例9.5

初始關(guān)鍵字序列為(15，27，8，21，40，21*，10，36)，直接選擇排序過程如圖9.6所示。方括號內(nèi)表示待排序的數(shù)據(jù)。圖9.6直接選擇排序示意直接選擇排序算法用C語言描述如下：voidSelectSort(RecordTyper[],intn)/*用直接選擇排序方法對r[1],…,r[n]進行排序*/{

inti,j,k；

for(i=1；i<n；i++)

{

k=i；

for(j=i+1；j<=n；j++)

if(r[j].key<r[k].key)

k=j；

if(k!=i){r[0]=r[i]； /*r[0]用作臨時變量，交換r[i]和r[k]*/r[i]=r[k]；

r[k]=r[0]；

}

}}從算法中可以看出，在直接選擇排序中，第一次排序要進行n-1次比較，第二次排序時要進行n-2次比較，…，所以總的比較次數(shù)為

(n-1)?+?(n-2)?+?…?+?1?=?(n-1)n/2由此可知，直接選擇排序的時間復(fù)雜度為O(n2)。直接選擇排序是一種穩(wěn)定的排序。9.4.2堆排序堆排序(HeapSort)是在直接選擇排序法的基礎(chǔ)上借助完全二叉樹結(jié)構(gòu)而形成的一種排序方法。在直接選擇排序中，為找出關(guān)鍵字最小的記錄，需要做n-1次比較，然后為尋找關(guān)鍵字次小的記錄要對剩下的n-1個記錄進行n-2次比較。在這n-2次比較中，有許多次比較在第一次排序的n-1次比較中已做過了。事實上，直接選擇排序的每次排序除了找到當(dāng)前關(guān)鍵字最小的記錄外，還產(chǎn)生了許多比較結(jié)果信息，這些信息在以后的各次排序中還有用，但由于沒有保存這些信息，因此每次排序都要對剩余的全部記錄的關(guān)鍵字重新進行一遍比較，這樣大大增加了時間開銷。堆排序是針對直接選擇排序所存在的上述問題而形成的一種改進方法。它在尋找當(dāng)前關(guān)鍵字最小的記錄的同時，還保存了本趟排序過程所產(chǎn)生的其它比較信息。

1.堆的概念堆的定義：具有n個元素的序列(R1，R2，…，Rn)，相應(yīng)的關(guān)鍵字序列(K1，K2，…，Kn)當(dāng)且僅當(dāng)滿足或(i=1,2,…,n/2)時稱之為堆，前者稱為大根堆，后者稱為小根堆。由堆的定義可以看出，堆頂元素(即第一個元素)必為最大值(或最小值)。在實際處理中，可以用一維數(shù)組存儲堆序列中的元素，也可用完全二叉樹直觀地表示堆的結(jié)構(gòu)。例如，序列(98，77，35，62，55，14，35，48)是一個大根堆，序列(14，48，35，62，55，98，35，77)是一個小根堆，它們所對應(yīng)的完全二叉樹如圖9.7所示。在用完全二叉樹表示堆時，樹中的所有非葉子結(jié)點的關(guān)鍵字值均不小于(或不大于)其左、右子樹的根結(jié)點的關(guān)鍵字值。本節(jié)將以大根堆為例進行討論。圖9.7堆的示例(a)大根堆；(b)小根堆

2.堆排序的方法若在輸出堆頂?shù)淖畲笾岛?，使得剩余n-1個元素的序列又重建成一個堆，則得到n個元素中的次大值。如此反復(fù)執(zhí)行，便能得到一個有序序列，這個過程稱之為堆排序?？梢园匆韵虏襟E實現(xiàn)堆排序：

(1)將n個記錄存放在一個一維數(shù)組中；

(2)將一維數(shù)組中的n個記錄調(diào)整成堆；

(3)將看成的完全二叉樹的根(第1個數(shù)組元素位置上的記錄)與最后一個記錄對調(diào)；

(4)將第1至第n-i(1≤i≤n-1)個記錄再構(gòu)成堆；

(5)重復(fù)(3)至(4)步，直到i?=?n-1。實現(xiàn)堆排序需要解決兩個問題：①如何由一個無序序列建成一個堆？②如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？下面先討論第二個問題，然后再討論第一個問題。以一維數(shù)組r[1,…,n]存儲待排序記錄，r[0]作為臨時存儲單元。問題1:輸出堆頂元素后，如何重建堆?以從圖9.8(a)的大根堆中輸出最大元素為例。首先將完全二叉樹根結(jié)點中的記錄r[1]與最后一個記錄r[n]對調(diào)，后面的操作將不再考慮交換下來的原來堆頂元素，只將其余元素r[1]～r[n-1]構(gòu)成堆。在這些元素對應(yīng)的完全二叉樹中，根結(jié)點的左、右子樹均為堆，只有根可能不符合堆的要求。如圖9.8(b)所示。將新的根結(jié)點記錄移出，該記錄稱為待調(diào)整記錄，此時根結(jié)點相當(dāng)于空結(jié)點。從空結(jié)點的左、右孩子中選出一個關(guān)鍵字較大的記錄，如果該記錄的關(guān)鍵字大于待調(diào)整記錄的關(guān)鍵字，則將該記錄上移至空結(jié)點中。如圖9.8(c)所示。此時，原來那個關(guān)鍵字較大的子結(jié)點相當(dāng)于空結(jié)點。重復(fù)上述移動過程，直到空結(jié)點左、右子樹的關(guān)鍵字均不大于待調(diào)整記錄的關(guān)鍵字，此時將待調(diào)整記錄放入空結(jié)點即可。如圖9.8(d)至圖9.8(f)所示。上述調(diào)整方法相當(dāng)于把待調(diào)整記錄逐步向下“篩”的過程，所以稱這個自堆頂至葉子的調(diào)整過程為“篩選”。圖9.8輸出堆頂元素并調(diào)整建新堆過程(a)大根堆；(b)交換48與98；(c)?48移出，77準備上移；(d)77上移后，62準備上移；(e)?62上移后，48準備移入空記錄；(f)?48移入空記錄得到篩選后的堆問題2：如何由一個任意序列建成堆？一個任意序列看成是對應(yīng)的完全二叉樹，由于葉子結(jié)點可以視為單元素的堆，因而可以反復(fù)利用“篩選”法，自底向上逐層把所有以非葉子結(jié)點為根的子樹調(diào)整為堆，直到將整個完全二叉樹調(diào)整為堆。如果二叉樹結(jié)點數(shù)目為n，則最后一個葉子結(jié)點的編號為n，而它的雙親就是最后一個非葉子結(jié)點，其編號為

n/2

。因此，“篩選”須從第

n/2

個元素開始，逐層向上倒退，直到根結(jié)點。

例9.6

已知關(guān)鍵字序列：｛48，62，35，77，55，14，35，98｝，要求將其篩選為一個堆。

解：在此，n?=?8，所以應(yīng)從第４個結(jié)點77開始篩選。建堆過程如圖9.9所示。圖中箭頭所指為當(dāng)前待篩結(jié)點。圖9.9建初始堆過程示例(a)初始無序序列，準備篩77；(b)?77篩完后，準備篩35；(c)?35篩完后，準備篩62；(d)?62篩完后，準備篩48；(e)?48篩完后，得到大根堆

3.堆排序的算法及分析首先利用篩選算法建初始堆，移出最大元素后再利用篩選算法重建堆，重復(fù)n-1次移出再重建的過程，完成排序。待排序元素存放在數(shù)組r[1,…,n]中。

(1)篩選的算法用C語言描述如下：

voidsift(RecordTyper[],intk,intm)

/*假設(shè)r[k,…,m]是以r[k]為根的完全二叉樹，且分別以r[2k]和r[2k+1]為根的左、右子樹都是大根堆，通過篩選，使整個序列r[k,…,m]滿足堆的性質(zhì)*/{

inti,j;

RecordTypex；

i=k；

j=2*i； /*r[j]是r[i]的左孩子*/

x=r[i]； /*移出根結(jié)點*/

while(j<=m){

if(j<m&&r[j].key<r[j+1].key)

j++； /*若右孩子較大，則把j修改為右孩子的下標*/

if(x.key<r[j].key) /*若父結(jié)點小于孩子結(jié)點*/{

r[i]=r[j]； /*將r[j]上移到父結(jié)點的位置上*/

i=j； /*以上移子結(jié)點的原位置為新的父結(jié)點位置，繼續(xù)向下篩*/

j=2*i；

}elsej=m+1；/*父結(jié)點不小于子結(jié)點，篩選運算完成，令j=m+1，以便中止循環(huán)*/

}

r[i]=x；/*被篩結(jié)點的值放入最終位置*/}

(2)堆排序算法：利用篩選函數(shù)，從第

n/2

個元素開始，向上倒退，直到根結(jié)點r[1]，建立初始堆。將已有堆中的根與最后一個葉子交換，利用篩選函數(shù)，進一步恢復(fù)堆，直到一棵樹只剩一個根為止。堆排序算法用C語言描述如下：voidHeapSort(RecordTyper[],intn){

inti；

RecordTypew；

for(i=n/2；i>=1；i--) /*建立初始堆*/

sift(r,i,n)；for(i=n；i>=2；i--)

/*進行n-1次循環(huán)，完成堆排序*/{

w=r[i]； /*將第一個元素同當(dāng)前區(qū)間內(nèi)最后一個元素對換*/

r[i]=r[1]；

r[1]=w；

sift(r,1,i-1)； /*r[i]結(jié)點為已移出者，r[1]～r[i-1]結(jié)點重建堆*/

}}堆排序算法的時間復(fù)雜度是O(nlog2n)。堆排序是一種不穩(wěn)定的排序方法。9.5歸并排序歸并排序(MergingSort)的基本思想是：將兩個有序的序列合并成一個有序的序列。如果無序序列中有n個記錄，則可以把它看成n個有序的子序列，每個子序列只包含一個記錄，歸并排序先將每個相鄰的兩個子序列合并，得到

n/2

個有序子序列，每個子序中包含2個或1個記錄，然后再將這些子序列中相鄰的子序列兩兩歸并。依此類推，直到合并成一個有序的序列為止。由于在排序過程中，子序列總是兩兩歸并，因此歸并排序也稱為二路歸并排序。

例9.7

關(guān)鍵字序列為：(36，62，22，58，72，10，22*，89，55，33)，采用二路歸并排序過程如圖9.10所示。圖9.10二路歸并排序過程歸并排序法的基本操作是將待排序列中相鄰的兩個有序子序列合并成一個有序序列，通過遞歸調(diào)用兩兩合并的函數(shù)來實現(xiàn)。兩兩合并的算法在例2.2中已經(jīng)詳細介紹，這里不再重復(fù)。歸并排序法的時間復(fù)雜度為O(nlog2n)。歸并排序是一種穩(wěn)定的排序方法，這是它與快速排序和堆排序相比的最大特點。一般情況下，由于要求附加與待排記錄等數(shù)量的輔助空間，因此歸并排序較少用于內(nèi)部排序，而主要用于外部排序。9.6基數(shù)排序基數(shù)排序(RadixSort)又稱為吊桶排序，是和前面介紹的各種排序方法完全不同的一種排序方法。前面介紹的排序方法中，主要是通過關(guān)鍵字間的比較和移動記錄這兩個操作來實現(xiàn)排序，而基數(shù)排序不需要進行記錄關(guān)鍵字間的比較，它是借助“分配”和“收集”兩種操作對單邏輯關(guān)鍵字進行排序的一種內(nèi)部排序方法。基數(shù)排序有鏈式基數(shù)排序和多關(guān)鍵字排序等方法。本節(jié)只介紹鏈式基數(shù)排序。假設(shè)記錄r[i]的關(guān)鍵字為keyi，keyi是由d位十進制數(shù)字構(gòu)成的，即keyi?=?Ki1Ki2…Kid，其中Ki1是最高位，Kid是最低位，每一位的值都在0≤Kij≤9的范圍內(nèi)，此時基數(shù)rd?=?10。如果keyi是由d個小寫英文字母構(gòu)成的，即'a'≤Kij≤'z'，則基數(shù)rd?=?26。鏈式基數(shù)排序?qū)儆凇暗臀粌?yōu)先”排序法，即從最低位開始，按關(guān)鍵字每位的不同值將序列中的記錄“分配”到rd個隊列當(dāng)中，再按順序“收集”，如此重復(fù)d次，通過反復(fù)進行分配與收集操作來完成排序。

例9.8

關(guān)鍵字序列{278，109，63，930，589，184，505，269，8，83}，采用鏈式基數(shù)排序的過程如圖9.11所示。f[j]和e[j]分別代表第j個分配隊列的頭尾指針。對于n個記錄(每個記錄關(guān)鍵字最多含d位，每位的取值范圍為rd個值)進行鏈式排序的時間復(fù)雜度為O(d(n?+?rd))。鏈式基數(shù)排序是穩(wěn)定的排序方法，適合于n值很大而關(guān)鍵字位數(shù)較少的序列。圖9.11鏈式基數(shù)排序示例(a)初始狀態(tài)；(b)第一趟分配之后；(c)第一趟收集之后；圖9.11鏈式基數(shù)排序示例(d)第二趟分配之后；(e)第二趟收集之后；(f)第三趟分配之后；(g)第三趟收集之后的有序記錄9.7排序算法9.7.1各種排序算法的比較在各種排序方法中，沒有哪一種是絕對最優(yōu)的，在實際使用時需根據(jù)不同情況適當(dāng)選擇所需的排序方法，甚至可將多種方法結(jié)合起來使用。幾種常用排序方法的比較如表9.2所示。表9-2幾種常用排序方法比較9.7.2排序方法的選擇上面對各種排序方法進行了綜合比較和分析，那么在實際應(yīng)用中究竟如何選擇合適的排序方法呢？一般來說，首先應(yīng)從穩(wěn)定性方面進行分析。若要求算法穩(wěn)定，則只能在穩(wěn)定方法中選擇，否則可從所有排序方法中進行選擇，也可從待排序的記錄數(shù)n的大小上進行考慮。若n較大，首先在改進的排序方法中進行選擇，然后再考慮其他因素。綜上所述，列出以下幾種選擇方法，僅供讀者參考：

(1)當(dāng)待排序的結(jié)點數(shù)n較大、關(guān)鍵字分布比較均勻且對算法的穩(wěn)定性不作要求時，宜選擇快速排序法。

(2)當(dāng)待排序的結(jié)點數(shù)n較大、關(guān)鍵字分布可能出現(xiàn)正序或逆序的情況且對算法的穩(wěn)定性不作要求時，宜采用堆排序或歸并排序。

(3)當(dāng)排序的結(jié)點數(shù)n較大、內(nèi)存空間較大且要求算法穩(wěn)定時，宜采用歸并排序。

(4)當(dāng)待排序的結(jié)點數(shù)n較小，對排序的穩(wěn)定性不作要求時，宜采用直接選擇排序。若關(guān)鍵字不接近逆序，也可采用直接插入排序。

(5)當(dāng)待排序的結(jié)點數(shù)n較大，關(guān)鍵字基本有序或分布較均勻且要求算法穩(wěn)定時，采用直接插入排序。在實際應(yīng)用中，可根據(jù)實際要求進行選擇。本章小結(jié)本章首先介紹了排序及其相關(guān)的基本概念，然后介紹了直接插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、排序過程及實現(xiàn)算法，并對這些算法的效率進行了分析和比較。一個好的排序算法所需要的比較次數(shù)和存儲空間都應(yīng)該較少，但通過本章的學(xué)習(xí)可以看出，不存在一個“十全十美”的排序算法能夠適合于不同的場合，每一種排序算法各有優(yōu)缺點。在實際應(yīng)用中，應(yīng)根據(jù)問題的規(guī)模大小、排序的穩(wěn)定性、算法的效率等方面進行分析和比較，從而針對不同的應(yīng)用場合選擇合適的排序算法。習(xí)題九一、單選題

1.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是

。

A.希爾排序 B.冒泡排序

C.直接插入排序 D.直接選擇排序

2.設(shè)有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用

排序法。

A.冒泡排序 B.堆排序

C.快速排序 D.基數(shù)排序

3.排序的元素序列基本有序的前提下，效率最高的排序方法是

。

A.直接插入排序 B.直接選擇排序

C.快速排序 D.歸并排序

4.一組記錄的排序碼為(46，79，56，38，40，84)，則利用堆排序的方法建立的初始堆為

。

A.?79，46，56，38，40，80

B.?84，79，56，38，40，46

C.?84，79，56，46，40，38

D.?84，56，79，40，46，38

5.一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為

。

A.?38，40，46，56，79，84

B.?40，38，46，79，56，84

C.?40，38，46，56，79，84

D.?40，38，46，84，56，79

6.排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為

。

A.希爾排序 B.歸并排序

C.插入排序D.選擇排序

7.用一種排序方法對線性表(25，84，21，47，15，27，68，35，20)進行排序時，元素序列的變化情況如下：初始：25，84，21，47，15，27，68，35，20第一趟：20，15，21，25，47，27，68，35，84第二趟：15，20，21，25，35，27，47，68，84第三趟：15，20，21，25，27，35，47，68，84則所采用的排序方法是

。

A.選擇排序 B.希爾排序

C.歸并排序 D.快速排序

8.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是

。

A.?O(1) B.?O(n)

C.?O(n2) D.?O(nlog2n)

9.給定n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是

。

A.?O(1) B.?O(n)

C.?O(n2) D.?O(nlog2n)

二、解決下列問題

1.已知序列(17，18，60，40，7，32，73，65，85)，請給出采用冒泡排序法對該序列作升序排序時每一趟的結(jié)果。

2.已知序列(503，87，512，61，908，170，897，275，653，462)，請給出采用堆排序法對該序列作升序排序時每一趟的結(jié)果。

3.已知序列(503，87，512，61，908，170，897，275，653，462)，請給出采用基數(shù)排序法對該序列作升序排序時每一趟的結(jié)果。

4.已知序列(503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94)，請給出采用快速排序法對該序列作升序排序時每一趟的結(jié)果。實訓(xùn)9-1內(nèi)部排序算法時間復(fù)雜度分析【實訓(xùn)目的】掌握常用內(nèi)部排序算法，并對各種內(nèi)部排序算法時間復(fù)雜度進行分析。【實訓(xùn)要求】

1.對以下3種常用排序算法比較其關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)(關(guān)鍵字交換計為3次移動)：直接插入排序、冒泡排序、快速排序。

2.待排序表的表長不少于100，其中的數(shù)據(jù)用偽隨機數(shù)，至少要用5組不同的輸入數(shù)據(jù)做比較?！舅惴ǚ治觥吭诔绦蜻m當(dāng)?shù)牡胤讲迦胗嫈?shù)操作?！境绦蚯鍐巍?include<stdlib.h>#defineMAXSIZE100voidInsertSort(intr[],intn)/*用直接插入排序方法對r[1]，…，r[n-1]進行排序*/{inti,j,b,y;

b=0; /*比較計數(shù)器初值為0*/y=0; /*移動計數(shù)器初值為0*/for(i=2;i<=n;i++) /*認為r[1]是已排好的初始序列*/{r[0]=r[i]; /*將待插入記錄存放到r[0]中*/y++;for(j=i-1;r[0]<r[j];j--)/尋找插入位置*/{r[j+1]=r[j];b++;y++;}b++;/*使循環(huán)結(jié)束的最后一次比較計數(shù)加1*/r[j+1]=r[0];/*將待插入記錄插入到已排序的序列中*/y++;}printf("比較%d次,移動%d次\n",b,y);}/*InsertSort*/voidBubbleSort(intr[],intn)/*用冒泡排序法對r[1],…,r[n]進行排序*/{inti,m,b,y,flag;b=0; /*比較計數(shù)器初值為0*/y=0; /*移動計數(shù)器初值為0*/ flag=1; /*標志量。交換發(fā)生時為1*/m=n; /*每趟排出的最大值存放的位置，也就是每趟參與排序的元素個數(shù)*/while(m>1&&flag){flag=0;for(i=1;i<m;i++)

{if(r[i]>r[i+1]){flag=1;r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];

y+=3; /*交換作移動3次*/}b++;}m--;}printf("比較%d次,移動%d次\n",b,y);}intsplit(intr[],intm,intn,int*pb,int*py)/*對記錄數(shù)組r[m]，…，r[n]進行分割，返回分界線位置，參數(shù)pb、py返回比較和移動次數(shù)*/{inti,j;intt;i=m;j=n;t=r[i]; /*選擇基準記錄*/(*py)++;/*移動計數(shù)*/while(i<j){while((i<j)&&(r[j]>=t))/*j從右到左找小于t的記錄*/{j=j-1;(*pb)++;/*比較計數(shù)*/}if(i<j) /*找到小于t的記錄，則進行交換*/{r[i]=r[j];(*py)++;i=i+1;}while((i<j)&&(r[i]<=t)) /*i從左到右找大于t的記錄*/{i=i+1;(*pb)++;}if(i<j)/*找到大于t的記錄，則進行交換*/{r[j]=r[i];(*py)++;j=j-1;}}r[i]=t; /*將基準記錄保存到i=j的位置*/(*py)++; return(i); /*返回基準記錄的位置*/}voidQkSort(intr[],intm,intn,int*pb,int*py)/*對記錄數(shù)組r[m]，…，r[n]用快速排序算法進行排序，參數(shù)pb、py返回比較和移動的次數(shù)*/{inti;if(m<n)/*子表不空*/

{i=split(r,m,n,pb,py); /*分割*/QkSort(r,m,i-1,pb,py); /*對前面子表進行快速排序*/QkSort(r,i+1,n,pb,py); /*對后面子表進行快速排序*/

}}main(){inti,j,r[MAXSIZE];intb,y;for(i=1;i<=5;i++){printf("\n第%d組數(shù)據(jù)\n",i);for(j=1;j<=100;j++)r[j]=rand();printf("直接插入排序:\t");InsertSort(r,100);printf("冒泡排序:\t");BubbleSort(r,100);b=0;y=0;printf("快速排序:\t");QkSort(r,1,100,&b,&y);printf("比較%d次,移動%d次\n",b,y);}}

程序運行結(jié)果如下：觀察結(jié)果會發(fā)現(xiàn)，冒泡排序、快速排序的比較和移動次數(shù)總是不變，且冒泡排序的效率最高，比較次數(shù)僅為99，移動次數(shù)為0。如果將冒泡函數(shù)BubbleSort()中的“flag?=?0;”一句刪除，即無論是否發(fā)生交換都不中止排序，則發(fā)現(xiàn)冒泡比較4950次，移動0次。這是因為偽隨機函數(shù)rand()所產(chǎn)生的是一個有序序列，冒泡排序過程中不會發(fā)生交換。此時快速排序退化為冒泡排序，所以比較4950次。且由于每趟快速排序時都要經(jīng)過保存和寫回基準記錄r[i]的步驟，所以移動次數(shù)為2*99?=?198。實訓(xùn)9-2排序算法的應(yīng)用【實訓(xùn)目的】運用各種排序算法解決實際問題?！緦嵱?xùn)內(nèi)容】為奧運會男子110米欄比賽設(shè)計排序和查詢系統(tǒng)，可分別按選手編號和成績排序，并提供按編號查詢、按編號和名次輸出的功能。【實訓(xùn)要求】

1.編寫完整程序，主函數(shù)顯示如下菜單：

1—輸入

2—按選手編號排序

3—按成績排序

4—按選手編號查詢

5—按編號輸出

6—按名次輸出

0—退出

2.編寫輸入、按選手編號排序(直接選擇排序)、按成績排序(堆排序)、按選手編號查詢(折半查找)和輸出5個函數(shù)。【算法分析】記錄至少包括選手編號、成績等數(shù)據(jù)項，以數(shù)組形式存儲。分別以編號和成績?yōu)殛P(guān)鍵字排序，并將排序結(jié)果分別用另外的數(shù)組保存。按選手編號進行折半查找要在排序后的結(jié)果中進行?！境绦蚯鍐巍?include<stdio.h>#defineMAXSIZE100typedefstruct{intnumber;floatscore;}RecordType;voidinput(RecordTyper[],intn){

inti;for(i=1;i<=n;i++){printf("r[%d]的編號成績:\n",i);scanf("%d%f",&r[i].number,&r[i].score);}}voidSelectSort(RecordTyper[],intn)/*用直接選擇排序方法對r[1],…,r[n]按選手編號進行排序*/{inti,j,k;for(i=1;i<n;i++) { k=i; for(j=i+1;j<=n;j++) if(r[j].number<r[k].number) k=j; if(k!=i) {

r[0]=r[i]; /*r[0]用作臨時變量，交換r[i]和r[k]*/r[i]=r[k];r[k]=r[0];}}}voidsift(RecordTyper[],intk,intm)/*假設(shè)ｒ[k,…,m]是以ｒ[k]為根的完全二叉樹，且分別以r[2k]和r[2k+1]為根的左、右子樹都是大根堆，通過篩選，使整個序列r[k,…,m]滿足堆的性質(zhì)*/{inti,j;RecordTypex;i=k;j=2*i; /*r[j]是r[i]的左孩子*/x=r[i]; /*移出根結(jié)點*/while(j<=m){ if(j<m&&r[j].score<r[j+1].score) j++; /*若右孩子較大，則把j修改為右孩子的下標*/ if(x.score<r[j].score) /*若父結(jié)點小于孩子結(jié)點*/ { r[i]=r[j]; /*將r[j]上移到父結(jié)點的位置上*/

i=j; /*以上移子結(jié)點的原位置為新的父結(jié)點位置，繼續(xù)向下篩*/ j=