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

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

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

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

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

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

2.直接插入排序舉例

例9.1

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

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

(2)插入記錄。

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

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

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]; /*將待插入記錄插入到已排序的序列中*/

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

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

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

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

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

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];

/*記錄依次向后移動(dòng)*/

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

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

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

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

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

n/2

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

h1/2

，將待排序序列中所有間隔為h2的元素放在同一組中進(jìn)行排序；依此類推，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.希爾排序算法及分析進(jìn)行一趟希爾排序的算法與一趟直接插入排序相比，做了如下修改：前后記錄位置的增量是h，而不是1；r[0]只是暫存單元，而不是監(jiān)視哨。當(dāng)j≤0時(shí)，插入位置已找到。希爾排序算法用C語言描述如下：voidShellSort(RecordTyper[],intn)/*用希爾排序方法對(duì)r[1],…,r[n]進(jìn)行排序,r[0]為暫存單元*/{

inti,j,h;

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

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

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

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

例9.3

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

voidBubbleSort(RecordTyper[],intn)

/*用冒泡排序法對(duì)r[1],…,r[n]進(jìn)行排序*/

{

int,i,m,flag；

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

m=n; /*每趟排出的最大值存放的位置，也就是每趟參與排序的元素個(gè)數(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個(gè)記錄順序存儲(chǔ)在r[1],…,r[n]中，r[0]用作臨時(shí)存儲(chǔ)空間，外層for循環(huán)控制排序的執(zhí)行次數(shù)，內(nèi)層for循環(huán)用于控制在一次排序中相鄰記錄的比較和交換。flag為標(biāo)志量，當(dāng)flag?=?1時(shí)，表明在一次排序過程中，至少進(jìn)行了一次記錄的交換，反之，當(dāng)flag?=?0時(shí)，則表明在前次排序過程中，沒有任何記錄交換位置，排序結(jié)束。冒泡排序的時(shí)間復(fù)雜度為O(n2)，它是一種穩(wěn)定的排序方法。9.3.2快速排序

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

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

(2)將i逐漸增大，并逐次比較r(i)與T，直到發(fā)現(xiàn)一個(gè)r(i)＞T為止，將r(i)移到r(j)的位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置(即i==j)為止，此時(shí)將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)/*對(duì)記錄r[m]，…，r[n]進(jìn)行分割，返回分界線位置*/{

inti,j；

RecordTypet；

i=m；

j=n；

t=r[i]； /*選擇基準(zhǔn)記錄*/

while(i<j)

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

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

if(i<j)

/*找到小于t.key的記錄，則進(jìn)行交換*/{

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的記錄，則進(jìn)行交換*/{ r[j]=r[i]；

j=j-1；

}}

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

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

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

{

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

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

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

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

例9.5

初始關(guān)鍵字序列為(15，27，8，21，40，21*，10，36)，直接選擇排序過程如圖9.6所示。方括號(hào)內(nèi)表示待排序的數(shù)據(jù)。圖9.6直接選擇排序示意直接選擇排序算法用C語言描述如下：voidSelectSort(RecordTyper[],intn)/*用直接選擇排序方法對(duì)r[1],…,r[n]進(jì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]用作臨時(shí)變量，交換r[i]和r[k]*/r[i]=r[k]；

r[k]=r[0]；

}

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

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

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

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

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

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

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

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

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

n/2

。因此，“篩選”須從第

n/2

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

例9.6

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

解：在此，n?=?8，所以應(yīng)從第４個(gè)結(jié)點(diǎn)77開始篩選。建堆過程如圖9.9所示。圖中箭頭所指為當(dāng)前待篩結(jié)點(diǎn)。圖9.9建初始堆過程示例(a)初始無序序列，準(zhǔn)備篩77；(b)?77篩完后，準(zhǔn)備篩35；(c)?35篩完后，準(zhǔn)備篩62；(d)?62篩完后，準(zhǔn)備篩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]為根的左、右子樹都是大根堆，通過篩選，使整個(gè)序列r[k,…,m]滿足堆的性質(zhì)*/{

inti,j;

RecordTypex；

i=k；

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

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

while(j<=m){

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

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

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

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

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

j=2*i；

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

}

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

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

n/2

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

inti；

RecordTypew；

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

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

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

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

r[i]=r[1]；

r[1]=w；

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

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

n/2

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

例9.7

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

例9.8

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

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

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

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

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

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

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

。

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

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

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

排序法。

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)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(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.排序方法中，從未排序序列中依次取出元素與已排序序列(初始時(shí)為空)中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為

。

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

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

7.用一種排序方法對(duì)線性表(25，84，21，47，15，27，68，35，20)進(jìn)行排序時(shí)，元素序列的變化情況如下：初始：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.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是

。

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

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

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

。

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

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

二、解決下列問題

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

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

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

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

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

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

b=0; /*比較計(jì)數(shù)器初值為0*/y=0; /*移動(dòng)計(jì)數(shù)器初值為0*/for(i=2;i<=n;i++) /*認(rèn)為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é)束的最后一次比較計(jì)數(shù)加1*/r[j+1]=r[0];/*將待插入記錄插入到已排序的序列中*/y++;}printf("比較%d次,移動(dòng)%d次\n",b,y);}/*InsertSort*/voidBubbleSort(intr[],intn)/*用冒泡排序法對(duì)r[1],…,r[n]進(jìn)行排序*/{inti,m,b,y,flag;b=0; /*比較計(jì)數(shù)器初值為0*/y=0; /*移動(dòng)計(jì)數(shù)器初值為0*/ flag=1; /*標(biāo)志量。交換發(fā)生時(shí)為1*/m=n; /*每趟排出的最大值存放的位置，也就是每趟參與排序的元素個(gè)數(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; /*交換作移動(dòng)3次*/}b++;}m--;}printf("比較%d次,移動(dòng)%d次\n",b,y);}intsplit(intr[],intm,intn,int*pb,int*py)/*對(duì)記錄數(shù)組r[m]，…，r[n]進(jìn)行分割，返回分界線位置，參數(shù)pb、py返回比較和移動(dòng)次數(shù)*/{inti,j;intt;i=m;j=n;t=r[i]; /*選擇基準(zhǔn)記錄*/(*py)++;/*移動(dòng)計(jì)數(shù)*/while(i<j){while((i<j)&&(r[j]>=t))/*j從右到左找小于t的記錄*/{j=j-1;(*pb)++;/*比較計(jì)數(shù)*/}if(i<j) /*找到小于t的記錄，則進(jìn)行交換*/{r[i]=r[j];(*py)++;i=i+1;}while((i<j)&&(r[i]<=t)) /*i從左到右找大于t的記錄*/{i=i+1;(*pb)++;}if(i<j)/*找到大于t的記錄，則進(jìn)行交換*/{r[j]=r[i];(*py)++;j=j-1;}}r[i]=t; /*將基準(zhǔn)記錄保存到i=j的位置*/(*py)++; return(i); /*返回基準(zhǔn)記錄的位置*/}voidQkSort(intr[],intm,intn,int*pb,int*py)/*對(duì)記錄數(shù)組r[m]，…，r[n]用快速排序算法進(jìn)行排序，參數(shù)pb、py返回比較和移動(dòng)的次數(shù)*/{inti;if(m<n)/*子表不空*/

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

}}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òng)%d次\n",b,y);}}

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

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

1—輸入

2—按選手編號(hào)排序

3—按成績排序

4—按選手編號(hào)查詢

5—按編號(hào)輸出

6—按名次輸出

0—退出

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

inti;for(i=1;i<=n;i++){printf("r[%d]的編號(hào)成績:\n",i);scanf("%d%f",&r[i].number,&r[i].score);}}voidSelectSort(RecordTyper[],intn)/*用直接選擇排序方法對(duì)r[1],…,r[n]按選手編號(hào)進(jì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]用作臨時(shí)變量，交換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]為根的左、右子樹都是大根堆，通過篩選，使整個(gè)序列r[k,…,m]滿足堆的性質(zhì)*/{inti,j;RecordTypex;i=k;j=2*i; /*r[j]是r[i]的左孩子*/x=r[i]; /*移出根結(jié)點(diǎn)*/while(j<=m){ if(j<m&&r[j].score<r[j+1].score) j++; /*若右孩子較大，則把j修改為右孩子的下標(biāo)*/ if(x.score<r[j].score) /*若父結(jié)點(diǎn)小于孩子結(jié)點(diǎn)*/ { r[i]=r[j]; /*將r[j]上移到父結(jié)點(diǎn)的位置上*/

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