8.1基本概念

8.2插入排序

8.3交換排序

8.4選擇排序

8.5二路歸并排序

8.6基數(shù)排序

8.7排序方法的比較

小結(jié)

習(xí)題

實(shí)訓(xùn)指導(dǎo)第8章排序

問題引入

我們?cè)谏詈凸ぷ髦袝?huì)遇到大量的排序問題，因?yàn)橛行蛐蛄袝?huì)使問題的處理變得簡(jiǎn)單和高效。我們?cè)诟呒?jí)語(yǔ)言中也學(xué)過有關(guān)數(shù)組元素的排序問題，掌握了一些排序的方法，但實(shí)際應(yīng)用中的問題和要求是多樣和復(fù)雜的，需要有多種不同的途徑和方法來解決。那么除了已學(xué)過的冒泡排序和選擇排序方法，還有哪些其他方法呢？本章我們就來學(xué)習(xí)有關(guān)解決排序問題的常見方法。

知識(shí)要點(diǎn)

(1)插入排序是在前n個(gè)有序記錄的基礎(chǔ)上，插入第n+1個(gè)記錄，將有序記錄的個(gè)數(shù)變?yōu)閚+1個(gè)。

(2)交換排序是通過兩兩比較待排記錄的關(guān)鍵字，若與排序要求相逆，則交換待排記錄。

(3)選擇排序是在剩余的記錄中選取關(guān)鍵字最小的記錄作為有序序列的當(dāng)前記錄。

(4)歸并排序是將若干個(gè)已排序的子序列合并成一個(gè)有序的序列。

(5)基數(shù)排序是借助于“分配”和“收集”兩種操作來實(shí)現(xiàn)對(duì)單邏輯關(guān)鍵字的排序。

能力要求針對(duì)不同的問題和要求使用各種排序方法解決計(jì)算機(jī)應(yīng)用中的排序問題。排序在計(jì)算機(jī)科學(xué)中占有相當(dāng)重要的地位，排序本身就有著廣闊的應(yīng)用前景。排序，用一個(gè)比較通俗的說法就是排隊(duì)，可以理解為按規(guī)定的次序重新安排給定的一組對(duì)象。排序的目的是便于以后在已排好序的記錄集合中查找或檢索某一數(shù)據(jù)元素。8.1基本概念日常生活中有關(guān)排序的例子隨處可見。如大家非常熟悉的全班同學(xué)按照身高的高低由低到高來依次排隊(duì)。其實(shí)不僅是日常生活中有對(duì)排序的需要，在計(jì)算機(jī)系統(tǒng)中，對(duì)于大量數(shù)據(jù)的處理工作，排序也是其最基本的運(yùn)算之一，如高級(jí)語(yǔ)言中學(xué)過有關(guān)數(shù)組元素的排序問題。為了便于本章的學(xué)習(xí)，先給出排序的相關(guān)概念。

1．排序

有n個(gè)記錄的序列{R1，R2，…，Rn}，其相應(yīng)關(guān)鍵字的序列是{K1，K2，…，Kn}。將這些記錄重新排序?yàn)閧Ri1，Ri2，…，Rin}，使得相應(yīng)的關(guān)鍵字值滿足條件Ki1≤Ki2≤…≤Kin，這樣的一種操作稱為排序。由此可見：在排序過程中，一般進(jìn)行兩種基本操作：比較兩個(gè)關(guān)鍵字的大小和移動(dòng)記錄的位置。

2．內(nèi)部排序與外部排序根據(jù)排序時(shí)記錄所占用內(nèi)存的不同，可將排序分為兩類。一類是整個(gè)排序過程完全在內(nèi)存中進(jìn)行，稱為內(nèi)部排序；另一類是待排序記錄數(shù)量太大，內(nèi)存無法容納全部記錄，排序需要借助外部存儲(chǔ)設(shè)備才能完成，稱為外部排序。

3．穩(wěn)定排序與不穩(wěn)定排序上面所說的關(guān)鍵字Ki可以是記錄Ri的主關(guān)鍵字，也可以是次關(guān)鍵字，甚至可以是記錄中若干數(shù)據(jù)項(xiàng)的組合。若Ki是主關(guān)鍵字，則任何一個(gè)無序的記錄序列經(jīng)排序后得到的有序序列是唯一的；若Ki是次關(guān)鍵字或是記錄中若干數(shù)據(jù)項(xiàng)的組合，得到的排序結(jié)果將是不唯一的，因?yàn)榇判蛴涗浀男蛄兄写嬖趦蓚€(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。假設(shè)Ki?=?Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri領(lǐng)先于Rj(即i<j)，經(jīng)過排序后得到的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若在排序后的序列中Rj領(lǐng)先于Ri，則稱所用的排序方法是不穩(wěn)定的。

4．排序記錄的存儲(chǔ)表示方法對(duì)于待排序的記錄，有四種常見的存儲(chǔ)方法。

(1)向量存儲(chǔ)方法。向量存儲(chǔ)方法也稱為順序存儲(chǔ)方法，該方法將待排序的記錄存放在一組地址連續(xù)的存儲(chǔ)單元中。由于這種存儲(chǔ)方式中記錄之間的次序關(guān)系由其存儲(chǔ)位置來決定，所以排序過程中一般要移動(dòng)記錄才行。

(2)鏈接存儲(chǔ)方法。在該方法中，記錄之間邏輯上的相鄰性是靠指針來維持的，在排序時(shí)，不用移動(dòng)記錄元素，只需要修改指針。

(3)索引存儲(chǔ)方法。該方法在建立記錄信息的同時(shí)，還需要建立附加的索引表。索引表中索引項(xiàng)的指針能夠指示出記錄或一組記錄所在的起始存儲(chǔ)位置。

(4)散列存儲(chǔ)方法。該方法是根據(jù)記錄的關(guān)鍵字以某種運(yùn)算方法直接計(jì)算出該記錄的存儲(chǔ)地址。由此可見，同一邏輯結(jié)構(gòu)可以采用不同的存儲(chǔ)方法，這四種存儲(chǔ)方法既可單獨(dú)使用，也可以組合起來使用。本章主要討論在向量存儲(chǔ)方法上各種排序方法的實(shí)現(xiàn)。為了討論方便，假設(shè)待排序記錄的關(guān)鍵字均為整數(shù)，均從數(shù)組中下標(biāo)為1的位置開始存儲(chǔ)，下標(biāo)為0的位置存儲(chǔ)監(jiān)視哨或空閑不用。在本章的各種排序方法中，假定待排序的數(shù)據(jù)存放在如下定義的存儲(chǔ)結(jié)構(gòu)上，使用C語(yǔ)言，將數(shù)據(jù)類型描述如下：

結(jié)構(gòu)8-1

待排序記錄。

#defineMaxsize100 //假設(shè)待排序記錄最多為100個(gè)元素

typedefintDatatype; //假設(shè)待排序記錄關(guān)鍵字的數(shù)據(jù)類型為整型

typedefstruct

{Datatypekey;

otherdata…; //待排序記錄中的其他數(shù)據(jù)類型

}Recnode;

Recnoder[Maxsize];8.2插入排序

插入排序的基本思想是：在一個(gè)已排好序的記錄子集基礎(chǔ)上，一步一步將下一個(gè)待排序的記錄有序插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。8.2.1直接插入排序直接插入排序是一種比較簡(jiǎn)單的排序方法。其基本思想是：依次將記錄序列中的每一個(gè)記錄插入到有序段中，使有序段的長(zhǎng)度不斷地?cái)U(kuò)大。其具體的排序過程可以描述如下：首先將待排序記錄序列中的第一個(gè)記錄作為一個(gè)有序段；將記錄序列中的第二個(gè)記錄插入到上述有序段中形成由兩個(gè)記錄組成的有序段；再將記錄序列中的第三個(gè)記錄插入到這個(gè)有序段中，形成由三個(gè)記錄組成的有序段；依此類推。每一趟都是將一個(gè)記錄插入到前面的有序段中。假設(shè)當(dāng)前欲處理第i個(gè)記錄，則應(yīng)該將這個(gè)記錄插入到由前i-1個(gè)記錄組成的有序段中，從而形成一個(gè)由i個(gè)記錄組成的按關(guān)鍵字值排列的有序序列，直到所有記錄都插入到有序段中。一共需要經(jīng)過n-1趟就可以將初始序列的n個(gè)記錄重新排列成按關(guān)鍵字大小排列的有序序列。

圖8-1是利用直接插入排序向有序記錄中插入一個(gè)記錄的過程示意圖，待排序序列存放在r數(shù)組中。具體方法是將待插入記錄r[5]放入監(jiān)視哨r[0]中，然后從后向前依次與監(jiān)視哨r[0]的關(guān)鍵字進(jìn)行比較，直到將監(jiān)視哨r[0]存放到記錄數(shù)組中的相應(yīng)位置，使整個(gè)記錄序列有序。圖8-1向有序記錄中插入一個(gè)記錄的示意圖直接插入排序是在前i-1個(gè)有序記錄的基礎(chǔ)上，插入第i個(gè)記錄，將有序記錄的個(gè)數(shù)變?yōu)閕個(gè)。算法描述如下：

算法8-1

直接插入排序。

voidinsertsort(Recnoder[],intn)

//對(duì)記錄數(shù)組r做直接插入排序，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始

{

inti,j;

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

{

r[0]=r[i]; //將待插入記錄存放到監(jiān)視哨r[0]中

j=i-1; while(r[0].key<r[j].key) //尋找插入位置

{

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

}}由此可見，直接插入排序是利用監(jiān)視哨r[0]臨時(shí)保存待插入的記錄，同時(shí)從后往前查找應(yīng)插入的位置；查找與移動(dòng)用同一循環(huán)完成。直接插入排序從空間角度來看，只需要一個(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)系上。最好情況即順序：r[i].key>r[i-1].key，則while循環(huán)中關(guān)鍵字比較次數(shù)為1次，while循環(huán)執(zhí)行0次，不移動(dòng)記錄。最壞情況即逆序：r[i].key<r[1].key，則while循環(huán)中關(guān)鍵字比較次數(shù)和移動(dòng)記錄的次數(shù)為i-1。平均情況時(shí)，算法的時(shí)間復(fù)雜度為O(n2)。直接插入排序是穩(wěn)定排序。8.2.2希爾排序希爾排序又稱縮小增量排序，是在1959年由希爾(D.L.Shell)提出的，是對(duì)直接插入排序的一種改進(jìn)方法。其基本思想是：先選定一個(gè)間隔數(shù)d，將整個(gè)記錄序列按此間隔數(shù)從第一個(gè)記錄開始分成若干個(gè)子序列，即分別將所有間隔為d的記錄組成若干個(gè)子序列，在各個(gè)子序列中采用直接插入法進(jìn)行排序；然后縮小間隔數(shù)d，重新將整個(gè)記錄序列按新的d分成若干子序列，再分別對(duì)各個(gè)子序列進(jìn)行排序；如此下去，直到間隔數(shù)d為0時(shí)停止。間隔數(shù)d一般的取法為：初始為整個(gè)記錄個(gè)數(shù)的一半，以后每次都縮小一半。圖8-2是希爾排序的過程示意圖，待排序記錄存放在數(shù)組r中。開始時(shí)初始間隔數(shù)d為4，將整個(gè)記錄序列分為A、B、C、D四個(gè)子序列，每個(gè)子序列有兩個(gè)記錄，并對(duì)各個(gè)子序列采用直接插入法進(jìn)行排序。然后使間隔數(shù)d縮小一半為2，又將整個(gè)記錄序列分為E、F2個(gè)子序列，每個(gè)子序列有4個(gè)記錄，分別為{3、19、8、86}和{10、21、12、38}，并對(duì)這2個(gè)子序列采用直接插入法進(jìn)行排序。最后使間隔數(shù)d再縮小為1，將整個(gè)記錄序列作為一個(gè)序列，采用直接插入法進(jìn)行排序。此時(shí)整個(gè)記錄序列已經(jīng)完全有序，希爾排序結(jié)束。圖8-2希爾排序的示意圖由此可見，希爾排序法的主要特點(diǎn)是：首先確定間隔數(shù)d并且依此間隔數(shù)劃分子序列，當(dāng)d很大時(shí)，被移動(dòng)的記錄是跳躍式進(jìn)行的；當(dāng)d為1時(shí)，序列幾乎已經(jīng)有序，基本不需要進(jìn)行記錄的移動(dòng)，最終對(duì)整個(gè)記錄序列實(shí)現(xiàn)了排序。希爾排序是依據(jù)間隔數(shù)劃分子序列，對(duì)各個(gè)子序列采用直接插入法進(jìn)行排序，并不斷縮小間隔數(shù)實(shí)現(xiàn)最終的排序。算法描述如下：

算法8-2

希爾排序。voidshellsort(Recnoder[],intn)//對(duì)記錄數(shù)組r做希爾排序，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始{

inti,j;

intd; //d為間隔數(shù)

Recnodetemp;

d=n/2; //初始間隔數(shù)d為整個(gè)記錄個(gè)數(shù)的一半

while(d!=0) //間隔數(shù)d不為0時(shí)，進(jìn)行子序列的劃分

{

for(i=d+1;i<=n;i++)//子序列采用直接插入法進(jìn)行排序

{ temp=r[i]; j=i-d; while(j>0&&temp.key<r[j].key)//j>0為了確保不對(duì)記錄數(shù)組r的0下標(biāo)進(jìn)行訪問

{r[j+d]=r[j]; j=j-d;

} r[j+d]=temp;

} d=d/2;}}希爾排序的時(shí)效分析很難，關(guān)鍵字的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于間隔數(shù)d的選取和縮小方法。希爾排序開始間隔數(shù)較大，子序列較多，每個(gè)子序列的記錄少，故各個(gè)子序列內(nèi)采用直接插入法進(jìn)行排序也較快，后來隨著間隔數(shù)的逐漸縮小，子序列也逐漸減少，子序列的記錄數(shù)目逐漸增多，但由于各個(gè)子序列已經(jīng)基本有序，所以新一趟排序過程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進(jìn)。希爾排序是不穩(wěn)定排序。8.3交換排序

交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，若與排序要求相逆，則交換待排序記錄。8.3.1冒泡排序冒泡排序是一種簡(jiǎn)單的交換排序方法，它是通過相鄰記錄的交換，逐步將待排序序列變成有序序列的過程。冒泡排序的基本思想是：從頭至尾掃描待排序記錄序列，在掃描的過程中依次比較相鄰記錄關(guān)鍵字的大小，在不滿足條件的情況下進(jìn)行交換。以升序?yàn)槔?，在第一趟排序中，?duì)n個(gè)記錄進(jìn)行如下操作：比較相鄰兩個(gè)記錄的關(guān)鍵字，逆序時(shí)就交換位置。在掃描的過程中，不斷地將相鄰兩個(gè)記錄中關(guān)鍵字大的記錄向后移動(dòng)，最后將待排序記錄序列中的最大關(guān)鍵字記錄交換到待排序記錄序列的末尾，這也正是最大關(guān)鍵字記錄應(yīng)在的位置。冒泡排序的具體過程描述如下：

(1)對(duì)全部的n個(gè)記錄，從前向后依次比較相鄰兩個(gè)記錄的關(guān)鍵字(共需比較n-1次)，將關(guān)鍵字小的記錄交換到前面(將關(guān)鍵字大的記錄交換到后面)，逐次比較，直到將關(guān)鍵字最大的記錄移動(dòng)到最后的位置，此時(shí)將關(guān)鍵字最大的記錄固定下來(目前固定了1個(gè)記錄)。

(2)對(duì)前面的n-1個(gè)記錄，從前向后依次比較相鄰兩個(gè)記錄的關(guān)鍵字(共需比較n-2次)，將關(guān)鍵字小的記錄交換到前面(將關(guān)鍵字大的記錄交換到后面)，逐次比較，直到將關(guān)鍵字次大的記錄移動(dòng)到倒數(shù)第二個(gè)位置，此時(shí)將關(guān)鍵字次大的記錄也固定下來(目前固定了2個(gè)記錄)。

(3)參照第(1)步和第(2)步方法，依此類推，直到將所有記錄的關(guān)鍵字都按照由小到大的順序排好為止。圖8-3是冒泡排序的過程示意圖，待排序記錄存放在r數(shù)組中。在排序過程中，依次比較相鄰記錄關(guān)鍵字的大小，在不滿足條件時(shí)進(jìn)行相鄰記錄的交換，逐步將待排序序列變成有序序列。圖8-3冒泡排序的示意圖由此可見，每一趟排序總能夠確定一個(gè)記錄的位置。在第一趟排序后就能夠把關(guān)鍵字最大的記錄排到最后的位置，然后除去此記錄(因?yàn)橐汛_定好位置)，余下的記錄再如此反復(fù)，直到將所有的記錄都排好序?yàn)橹?。如果在某一趟冒泡過程中沒有進(jìn)行一次記錄的交換，則可提前結(jié)束冒泡排序，所以冒泡過程最多進(jìn)行n-1趟。冒泡排序是從頭至尾掃描待排序記錄序列，在掃描的過程中依次比較相鄰記錄關(guān)鍵字的大小，在不滿足條件的情況下進(jìn)行交換。算法描述如下：

算法8-3

冒泡排序。

voidbubblesort(Recnoder[],intn)

//對(duì)記錄數(shù)組r做冒泡排序，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始

{

inti,j;

intflag=1;//標(biāo)識(shí)每趟排序中有無交換，1有交換，0沒有交換

Recnodetemp;

for(i=1;i<n&&flag;i++)

{flag=0; for(j=1;j<=n-i;j++) if(r[j].key>r[j+1].key)

{ temp=r[j]; r[j]=r[j+1];

r[j+1]=temp; flag=1; }}}從空間角度來看，冒泡排序只需要一個(gè)輔助空間。從時(shí)間耗費(fèi)角度來看，冒泡排序總共要進(jìn)行n-1趟冒泡，對(duì)i個(gè)記錄進(jìn)行一趟冒泡需要i-1次關(guān)鍵字比較?？偟谋容^次數(shù)為冒泡排序是穩(wěn)定排序。8.3.2快速排序在冒泡排序中，由于掃描過程中只對(duì)相鄰的兩個(gè)記錄進(jìn)行比較，因此在互換兩個(gè)相鄰記錄時(shí)只能消除一個(gè)逆序。如果通過兩個(gè)(不相鄰的)記錄的交換，能夠消除待排序記錄中的多個(gè)逆序，則會(huì)大大加快排序的速度?？焖倥判蚍椒ň褪峭ㄟ^一次交換而消除多個(gè)逆序?？焖倥判蚴菍?duì)冒泡排序方法的一種改進(jìn)。在各種排序方法中，快速排序方法對(duì)記錄之間比較次數(shù)較少，因而速度也就比較快，被認(rèn)為是目前最好的排序方法之一?？焖倥判虻幕舅枷胧牵涸谝判虻膎個(gè)記錄中，任意取一個(gè)記錄(假如取第一個(gè)記錄),以這個(gè)記錄的關(guān)鍵字為標(biāo)準(zhǔn)(該記錄稱為支點(diǎn))，將所有記錄分為兩組，使得第一組中各記錄的關(guān)鍵字均小于或等于該關(guān)鍵字，第二組中各記錄的關(guān)鍵字均大于該關(guān)鍵字。然后把該記錄就排在這兩組的中間(這也是該記錄最終的位置)。此稱為一趟快速排序(或一次劃分)，對(duì)所分成的兩組記錄分別重復(fù)上述方法，直到所有記錄都排在適當(dāng)位置為止。一趟快速排序的具體過程描述如下：假設(shè)待排序列的下界和上界分別是low和high，并設(shè)r[low]是支點(diǎn)記錄。

(1)將r[low]中的記錄(支點(diǎn)記錄)復(fù)制到temp變量中，i和j兩個(gè)整型變量分別指向low和high所在位置上的記錄。

(2)首先從j所指向的記錄起向前依次將關(guān)鍵字與temp.key進(jìn)行比較，當(dāng)找到第一個(gè)關(guān)鍵字小于等于temp.key的記錄時(shí)，將此記錄復(fù)制到i所指的位置上。

(3)然后從i+1所指向的記錄起向后依次將關(guān)鍵字與temp.key進(jìn)行比較，當(dāng)找到第一個(gè)關(guān)鍵字大于temp.key的記錄時(shí)，將此記錄復(fù)制到j(luò)所指的位置上。

(4)然后從j-1所指向的記錄重復(fù)上面的(2)和(3)兩步，直到i和j相等為止，將temp中的記錄放回到i或j的位置上。至此，一趟快速排序完成，將記錄數(shù)組分為r[low]，…，r[i-1]和r[i+1]，…，r[high]兩部分。圖8-4是快速排序的示意圖，待排序記錄存放在r數(shù)組中。取r[1]為支點(diǎn)記錄，并將其保存在temp中，然后從后向前依次進(jìn)行r[j].key和temp.key的比較,直至找到滿足r[j].key<=temp.key的記錄時(shí)將r[j]復(fù)制到r[i]中；再?gòu)那跋蚝笠来芜M(jìn)行r[i].key和temp.key的比較，直至找到滿足r[i].key>temp.key的記錄時(shí)將r[i]復(fù)制到r[j]中；之后重復(fù)上述過程，最終直到i和j相等，此時(shí)i便是記錄temp所應(yīng)在的位置，一趟快速排序結(jié)束。同時(shí)，圖8-4也展示了整個(gè)快速排序的全過程。圖8-4快速排序的示意圖

算法8-4

快速排序?？焖倥判蚴且阅硞€(gè)記錄為支點(diǎn)，將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵字小于或等于支點(diǎn)記錄的關(guān)鍵字，另一部分所有記錄的關(guān)鍵字大于支點(diǎn)記錄的關(guān)鍵字。然后對(duì)所分成的兩部分重復(fù)上述方法，直到所有記錄都排在適當(dāng)位置為止。算法描述如下：

intPartition(Recnode*r,intlow,inthigh) //一趟快速排序算法

//將記錄數(shù)組r分成兩部分，low為起始下標(biāo)，high為結(jié)束下標(biāo)

{inti,j;

Recnodetemp;

i=low;

j=high;

temp=r[i]; //支點(diǎn)記錄保存在temp中

do

{while((r[j].key>temp.key)&&(i<j)) j--; //下標(biāo)為j的記錄和支點(diǎn)記錄比較

if(i<j) { r[i]=r[j]; i++; } while((r[i].key<=temp.key)&&(i<j)) i++; //下標(biāo)為i的記錄和支點(diǎn)記錄比較

if(i<j){r[j]=r[i]; j--; }}while(i!=j);r[i]=temp;returni;}//完整的快速排序算法描述如下voidquicksort(Recnode*r,intstart,intend)//對(duì)記錄數(shù)組r做快速排序，start為起始下標(biāo)，end為結(jié)束下標(biāo){inti;if(start<end){i=Partition(r,start,end); quicksort(r,start,i-1); quicksort(r,i+1,end);}}快速排序的最好情況是每趟將待排序列分成兩個(gè)獨(dú)立的長(zhǎng)度幾乎相等的子序列；最差情況是每趟將待排序列分成一個(gè)子序列中無記錄，而另一個(gè)子序列中有n-1個(gè)記錄?？梢宰C明：快速排序的平均時(shí)間復(fù)雜度也是O(nlog2n)，它是目前基于“記錄比較”操作的內(nèi)部排序方法中速度最快的，快速排序也因此而得名?？焖倥判蚴遣环€(wěn)定排序。8.4選擇排序

選擇排序的基本思想是：每一趟在剩余的n-i+1(i=1，2，…，n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。8.4.1簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的主要思想是：每一趟排序從待排序列的n-i+1(i=1，2，…，n-1)個(gè)記錄中選擇一個(gè)關(guān)鍵字最小的記錄與該n-i+1個(gè)記錄的第1個(gè)記錄交換位置，即與整個(gè)序列的第i個(gè)位置的記錄交換。簡(jiǎn)單選擇排序的具體過程描述如下：

(1)將全部的n個(gè)記錄，從前向后依次進(jìn)行比較并保留關(guān)鍵字最小記錄的下標(biāo)(位置)，然后將關(guān)鍵字最小的記錄和待排序列的第1個(gè)記錄交換位置，此時(shí)將關(guān)鍵字最小的記錄固定下來(目前固定了1個(gè)記錄)。

(2)將后面的n-1個(gè)記錄，從前向后依次進(jìn)行比較并保留關(guān)鍵字最小記錄的下標(biāo)(位置)，然后將關(guān)鍵字次小的記錄和待排序列的第2個(gè)記錄交換位置,此時(shí)將關(guān)鍵字次小的記錄固定下來(目前固定了2個(gè)記錄)。

(3)參照第(1)步和第(2)步方法，依此類推，直到將所有記錄的關(guān)鍵字都按照由小到大的順序排好為止。圖8-5是簡(jiǎn)單選擇排序的過程示意圖，待排序記錄存放在r數(shù)組中。在每一趟排序過程中，都是從待排序列記錄中選擇一個(gè)關(guān)鍵字最小的記錄與此時(shí)待排序記錄中的第一個(gè)記錄交換位置。圖8-5簡(jiǎn)單選擇排序的示意圖由圖8-5可見，每一趟排序總能夠確定一個(gè)記錄的位置。在第一趟排序就能夠把關(guān)鍵字最小的記錄排到第一個(gè)位置，然后除去此記錄(因?yàn)橐汛_定好位置)，余下的記錄再如此反復(fù)，直到將所有的記錄都排好序?yàn)橹?。?jiǎn)單選擇排序是在待排序列中選擇一個(gè)關(guān)鍵字最小的記錄與此時(shí)待排序列中的第一個(gè)記錄進(jìn)行交換。算法描述如下：

算法8-5

簡(jiǎn)單選擇排序。

voidselectsort(Recnoder[],intn)

//對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始

{inti,j,k;

Recnodetemp;

for(i=1;i<n;i++) //i代表每趟待排序列中第一個(gè)記錄的下標(biāo)

{k=i; //k代表待排序列中關(guān)鍵字最小記錄的下標(biāo)for(j=i+1;j<=n;j++) if(r[j].key<r[k].key) k=j; if(k!=i) { temp=r[i];

r[i]=r[k];

r[k]=temp; }}}簡(jiǎn)單選擇排序記錄的移動(dòng)次數(shù)較少，但關(guān)鍵字的比較次數(shù)依然是n(n+1)/2，所以時(shí)間復(fù)雜度仍為O(n2)。簡(jiǎn)單選擇排序是不穩(wěn)定排序。8.4.2樹形選擇排序樹形選擇排序是在簡(jiǎn)單選擇排序的基礎(chǔ)上發(fā)展而來的，比簡(jiǎn)單選擇排序的效率高。簡(jiǎn)單選擇排序的主要操作是對(duì)記錄中的關(guān)鍵字進(jìn)行比較，如果能減少比較次數(shù)完成排序，就能提高排序的速度。顯然在n個(gè)記錄中選出關(guān)鍵字最小的記錄，至少要進(jìn)行n-1次比較；而在剩下的n-1個(gè)記錄中選擇次小者并非一定要進(jìn)行n-2次比較，如果能利用前面n-1次比較的信息，就可以減少以后各趟選擇排序中的比較次數(shù)。圖8-6是樹形選擇排序的過程示意圖，按照錦標(biāo)賽淘汰制的方法從n個(gè)記錄選擇關(guān)鍵字最小的記錄。圖8-6(a)中的13就是記錄中關(guān)鍵字的最小值，共對(duì)記錄進(jìn)行了n-1=7次比較。而選擇記錄中關(guān)鍵字的次小值時(shí)可以利用前面的比較信息，將序列中記錄的最小關(guān)鍵字13改為最大值∞(或機(jī)器所允許的最大值)，然后再進(jìn)行比較，如圖8-6(b)中進(jìn)行3次比較，就選擇出了關(guān)鍵字為21的次小記錄。從上例中可看到選擇記錄中的次小值就不需要n-2次而只需要次比較。再將序列中最小關(guān)鍵字21改為最大值∞，選擇記錄中下一個(gè)關(guān)鍵字的次小值過程如圖8-6(c)所示。這種方法稱為樹形選擇排序方法。除了選擇第一個(gè)關(guān)鍵字最小的記錄需要對(duì)n個(gè)記錄進(jìn)行n-1次比較外，每選擇一個(gè)關(guān)鍵字次小的記錄都只需次比較，因此排序時(shí)間大大縮短。時(shí)間復(fù)雜度為O(nlog2n)。樹形選擇排序方法的缺點(diǎn)是輔助空間占用較多，和最大值∞的比較也是多余的。圖8-6樹形選擇排序的示意圖8.4.3堆排序堆排序是在樹形選擇排序的基礎(chǔ)上發(fā)展而來的，比樹形選擇排序的效率高。堆排序除了是一種排序方法之外，還涉及堆的概念。設(shè)有n個(gè)記錄，其關(guān)鍵字的序列為{k1，k2，…，kn}，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆：ki≤k2i，且ki≤k2i+1(i=1，2，…，)或ki≥k2i，且ki≥k2i+1(i=1，2，…，)前者建立的堆，堆頂?shù)年P(guān)鍵字最小，稱為小堆；后者建立的堆，堆頂?shù)年P(guān)鍵字最大，稱為大堆。若將堆看成是一棵以k1為根的完全二叉樹，則這棵完全二叉樹中的每個(gè)非終端結(jié)點(diǎn)的值均不大于(或不小于)其左、右孩子結(jié)點(diǎn)的值。由此可以看出，若一棵完全二叉樹是堆，則根結(jié)點(diǎn)一定是這n個(gè)結(jié)點(diǎn)中的最小者或最大者。大堆和小堆如圖8-7所示。若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)的值是最小(或最大)的。本小節(jié)中以下的例子和算法都是以大堆定義為基礎(chǔ)來介紹的。圖8-7大堆和小堆示意圖設(shè)有n個(gè)記錄，將其按關(guān)鍵字排序。首先將這n個(gè)記錄按關(guān)鍵字建成堆，將堆頂元素輸出，得到n個(gè)元素中關(guān)鍵字最大的元素。然后，再對(duì)剩下的n-1個(gè)元素建成堆，輸出堆頂元素，得到n個(gè)元素中關(guān)鍵字次大的元素。如此反復(fù)，便得到一個(gè)按關(guān)鍵字有序排列的序列。這個(gè)過程稱為堆排序。因此，實(shí)現(xiàn)堆排序需解決兩個(gè)問題：

(1)如何將n個(gè)元素的序列按關(guān)鍵字建成堆；

(2)輸出堆頂元素后，怎樣調(diào)整剩余n-1個(gè)元素，使其按關(guān)鍵字成為一個(gè)新堆。首先解決輸出堆頂元素后，對(duì)剩余元素重新建成堆的調(diào)整過程。調(diào)整方法：設(shè)有n個(gè)元素的堆，輸出堆頂元素后，剩下n-1個(gè)元素。將最后一個(gè)元素賦給堆頂，堆被破壞，其原因僅僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。將根結(jié)點(diǎn)與左、右子樹中根結(jié)點(diǎn)的關(guān)鍵字較大者進(jìn)行交換。若與左子樹的根交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)；若與右子樹的根交換，則右子樹堆被破壞，且僅右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。繼續(xù)對(duì)不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。稱這個(gè)從堆頂結(jié)點(diǎn)到葉子結(jié)點(diǎn)的自上而下的調(diào)整過程為“篩選”。圖8-8是在堆的基礎(chǔ)上，將堆頂元素和最后一個(gè)元素交換之后的調(diào)整過程。圖8-8調(diào)整剩余元素為新堆的示意圖現(xiàn)在解決如何將n個(gè)元素的序列按關(guān)鍵字建成堆。對(duì)初始序列建堆的過程，其實(shí)就是一個(gè)反復(fù)進(jìn)行篩選的過程。對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹，則最后一個(gè)結(jié)點(diǎn)是第個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)。對(duì)第個(gè)結(jié)點(diǎn)為根的子樹篩選，使該子樹成為堆，之后向前依次對(duì)各結(jié)點(diǎn)為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)，建堆完成。這一整個(gè)過程從第個(gè)結(jié)點(diǎn)開始，是一個(gè)自下而上的過程。圖8-9是初始序列建堆的過程。圖8-9初始建堆的過程示意圖堆排序主要由建立初始堆和反復(fù)重新調(diào)整堆這兩個(gè)部分組成，算法描述如下：

算法8-6

堆排序。

voidheapsift(Recnode*r,inti,intm) //堆的調(diào)整算法

//i是根結(jié)點(diǎn)的編號(hào)，m是以i為根的子樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)

{

intj;

Recnodetemp;

temp=r[i];

j=2*i; //j為i根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)

while(j<=m)

{

if((r[j].key<r[j+1].key)&&(j<m)) j++; //當(dāng)i結(jié)點(diǎn)有左右孩子時(shí)，j取較大孩子結(jié)點(diǎn)的編號(hào)

if(temp.key<r[j].key) //按堆定義調(diào)整并向下層篩選調(diào)整

{ r[i]=r[j]; i=j; j=2*i;

}

else break; //篩選調(diào)整完畢，跳出循環(huán)

}

r[i]=temp;

}

//完整的堆排序算法描述如下

voidheapsort(Recnode*r,intn)

//對(duì)記錄數(shù)組r進(jìn)行堆排序，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始{inti;Recnodetemp;for(i=n/2;i>=1;i--) heapsift(r,i,n);

//對(duì)無序序列建成大堆for(i=n;i>=2;i--){ temp=r[1]; //堆頂和堆中最后一個(gè)元素交換

r[1]=r[i]; r[i]=temp; heapsift(r,1,i-1); //調(diào)整堆頂元素為新堆}}堆排序的時(shí)間主要由建立初始堆和反復(fù)重新建立堆兩部分的時(shí)間開銷構(gòu)成，它們均是通過調(diào)用heapsift函數(shù)來實(shí)現(xiàn)的。堆排序的最壞時(shí)間復(fù)雜度為O(n?log2n)。堆排序的平均性能較接近于最壞性能，這是堆排序的最大優(yōu)點(diǎn)。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的排序。堆排序是不穩(wěn)定排序。

實(shí)例8-1

在大堆排序的基礎(chǔ)上，設(shè)法利用小堆排序完成相應(yīng)的記錄排序。

解決思路：先把此無序序列建立成小堆，再交換堆頂元素和最后一個(gè)元素，接著再調(diào)整“篩選”小堆，使其滿足小堆的要求，此時(shí)最后一個(gè)元素是整個(gè)記錄的最小元素(此記錄已排好序)。然后再次重復(fù)上面的過程，直到所有的記錄都排好序?yàn)橹?，此時(shí)得到的是一個(gè)由大到小的結(jié)果。小堆排序的過程描述如圖8-10所示。圖8-10小堆排序示意圖8.5二路歸并排序

前面介紹的各類排序方法對(duì)待排序列的初始狀態(tài)都不作任何要求，而歸并排序則要求待排序列已經(jīng)部分有序。部分有序指待排序列由若干個(gè)有序的子序列組成。歸并排序利用歸并技術(shù)來進(jìn)行排序。歸并技術(shù)可以將若干個(gè)已排序的子序列合并成一個(gè)有序的序列，其基本思想是：將這些有序的子序列進(jìn)行合并，從而得到一個(gè)有序的序列。合并是一種常見運(yùn)算，其方法為比較各個(gè)子序列的第一個(gè)記錄的關(guān)鍵字，最小的一個(gè)就是排序后序列的第一個(gè)記錄的關(guān)鍵字。取出這個(gè)記錄，繼續(xù)比較各個(gè)子序列中第一個(gè)記錄的關(guān)鍵字，便可找出排序后的第二個(gè)記錄。如此繼續(xù)下去，最終可以得到排序的結(jié)果。因此，歸并排序的基礎(chǔ)是合并。二路歸并排序是將兩個(gè)有序子序列合并成一個(gè)有序的序列。二路歸并排序的基本思想是：如果序列中有n個(gè)記錄，可以先把它看成n個(gè)子序列，每個(gè)子序列中只包含一個(gè)記錄，因而都是排好序的。二路歸并排序先將每相鄰的兩個(gè)子序列合并，得到個(gè)較大的有序子序列，每個(gè)子序列包含2個(gè)記錄。再將這些子序列兩兩合并。如此反復(fù)，直到最后合并成一個(gè)有序序列，至此排序完成。圖8-11是二路歸并排序的過程示意圖，待排序記錄存放在數(shù)組r中。開始將待排序列中的10個(gè)記錄看做獨(dú)立的子序列，這些子序列都是有序序列，然后將相鄰的兩個(gè)子序列合并，得到5個(gè)有序子序列，每個(gè)子序列包含2個(gè)記錄。接著再將這些子序列兩兩合并，得到3個(gè)有序子序列。如此反復(fù)，直到最后合并成一個(gè)有序序列。圖8-11二路歸并排序示意圖兩個(gè)有序子序列合并為一個(gè)有序序列的具體過程描述如下：假設(shè)兩個(gè)有序子序列是存儲(chǔ)在同一個(gè)向量中相鄰的兩個(gè)子序列，向量低端為low，向量高端為high，一個(gè)有序子序列是從r[low]到r[m]，另一個(gè)有序子序列是從r[m+1]到r[high]，其中l(wèi)ow≤m≤high。

(1)?i和j兩個(gè)整型變量分別指向兩個(gè)有序子序列起始位置low和m+1上的記錄，同時(shí)設(shè)一輔助向量r1，并使整型變量k指向其起始位置0。

(2)合并時(shí)比較r[i]和r[j]的關(guān)鍵字，取關(guān)鍵字小的記錄復(fù)制到r1[k]中，并使k加1，同時(shí)i或j(指向關(guān)鍵字小的記錄)也加1。

(3)重復(fù)第(2)步，直到i>m或j>high，此時(shí)將某個(gè)子序列中剩余的記錄全部復(fù)制到r1的末尾合并。

(4)最后將r1向量復(fù)制到r向量中，合并結(jié)束。兩個(gè)有序子序列合并為一個(gè)有序序列就是通過比較兩個(gè)子序列中當(dāng)前記錄關(guān)鍵字的大小，以決定將哪個(gè)記錄復(fù)制到輔助向量的當(dāng)前位置中。算法描述如下：

算法8-7

兩個(gè)有序子序列合并為一個(gè)有序序列。

voidmerge(Recnode*r,intlow,intm,inthigh)

//兩個(gè)有序子序列分別為r[low]到r[m]和r[m+1]到r[high]

{inti,j,k;

Recnoder1[Maxsize];

i=low; //i開始為第一個(gè)子序列的起始下標(biāo)

j=m+1; //j開始為第二個(gè)子序列的起始下標(biāo)

k=0; //k開始為r1數(shù)組的起始下標(biāo)

while((i<=m)&&(j<=high))

{//i和j尚沒有超出各自序列的結(jié)束下標(biāo)

if(r[i].key<=r[j].key) {//i小于j(關(guān)鍵字)，將r[i]復(fù)制給r1[k]并使i和k各加1 r1[k]=r[i]; i++; k++; } else{//j小于i(關(guān)鍵字)，將r[j]復(fù)制給r1[k]并使j和k各加1

r1[k]=r[j]; j++; k++; }}while(i<=m){//j超出序列的結(jié)束下標(biāo)，將i所指的剩余記錄全部復(fù)制到r1中

r1[k]=r[i]; i++; k++;}while(j<=high){//i超出序列的結(jié)束下標(biāo)，將j所指的剩余記錄全部復(fù)制到r1中

r1[k]=r[j]; j++; k++;}for(i=low,k=0;i<=high;i++,k++) r[i]=r1[k]; //r1中的內(nèi)容復(fù)制給r}一趟二路歸并排序就是反復(fù)調(diào)用兩個(gè)有序子序列合并為一個(gè)有序序列的算法。算法描述如下：

算法8-8

一趟二路歸并排序。

voidonemerge(Recnode*r,intlenth,intn)

//lenth為子序列的長(zhǎng)度，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始

{inti=1;

while(i+2*lenth-1<=n)

{//兩個(gè)子序列長(zhǎng)度相等時(shí)，調(diào)用merge函數(shù)

merge(r,i,i+lenth-1,i+2*lenth-1); i=i+2*lenth;

}

if(i+lenth-1<=n)//序列中余留部分處理，調(diào)用merge函數(shù)

merge(r,i,i+lenth-1,n-1);

}二路歸并排序就是反復(fù)調(diào)用一趟歸并排序的算法。當(dāng)有序子序列長(zhǎng)度lenth大于整個(gè)記錄序列長(zhǎng)度n時(shí)二路歸并排序結(jié)束。算法描述如下：

算法8-9

二路歸并排序。

voidmergesort(Recnode*r,intn)

//對(duì)記錄數(shù)組r做二路歸并排序，n為數(shù)組的長(zhǎng)度，下標(biāo)從1開始

{intlenth=1;

while(lenth<=n)

{

onemerge(r,lenth,n); lenth=2*lenth;

}

}

二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)，執(zhí)行歸并排序需要附加一倍的存儲(chǔ)開銷。在n較大時(shí)，歸并排序所需時(shí)間較堆排序少，但它所需的輔助存儲(chǔ)量最多。二路歸并排序是穩(wěn)定排序，因?yàn)樵诿績(jī)蓚€(gè)有序序列的歸并過程中，若兩個(gè)按關(guān)鍵字排序的有序序列中出現(xiàn)相同的記錄，則該算法能夠使前一個(gè)序列中那個(gè)相同的記錄先被復(fù)制，從而確保這兩個(gè)相同記錄的相對(duì)次序不發(fā)生改變。二路歸并排序是穩(wěn)定排序。8.6基數(shù)排序

基數(shù)排序是與前面介紹的各類排序方法完全不同的一種排序方法。前面幾種方法主要是通過記錄關(guān)鍵字的比較和移動(dòng)(交換)記錄這兩種操作來實(shí)現(xiàn)的，而基數(shù)排序不需要進(jìn)行記錄關(guān)鍵字的比較和移動(dòng)(交換)記錄，它是基于多關(guān)鍵字排序的思路而對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種內(nèi)部排序方法。8.6.1多關(guān)鍵字排序下面通過一個(gè)實(shí)例來說明多關(guān)鍵字的排序。假定52張撲克牌的次序?yàn)??<3?<…<A?<2?<3?<…<A?<2?<3?<…<A?<2?<3?<…<A?顯然每一張撲克牌有兩個(gè)關(guān)鍵字：花色(?<?<?<?)和面值(2<3<4<…<A)，并且花色優(yōu)先于面值，這就是在比較任意兩張撲克牌的大小時(shí)，先比較花色，只有花色相同時(shí)才比較面值。若要將撲克牌整理成上面規(guī)定的次序，通常采用的方法有兩種：一種方法是先按花色分成四堆，并按花色的次序?qū)⑺亩雅藕?，然后分別對(duì)每一堆按面值從小到大整理有序，這種方法稱為最高位優(yōu)先法，簡(jiǎn)稱MSD法；另一種方法是先按面值分成13堆，并按面值大小將13堆排好，然后再將這13堆按花色的次序從小到大整理有序，這種方法稱為最低位優(yōu)先法，簡(jiǎn)稱LSD法。利用最低位優(yōu)先方法進(jìn)行排序時(shí)，可以不用前面介紹的各種通過關(guān)鍵字比較的方法，而是通過若干次“分配”和“收集”來實(shí)現(xiàn)排序，并把它用到對(duì)單邏輯關(guān)鍵字的排序上。8.6.2鏈?zhǔn)交鶖?shù)排序基數(shù)排序是借助于“分配”和“收集”兩種操作來實(shí)現(xiàn)對(duì)單邏輯關(guān)鍵字排序的一種內(nèi)部排序方法。某些關(guān)鍵字可以看成是由若干個(gè)關(guān)鍵字復(fù)合而成的。例如，若關(guān)鍵字K是數(shù)值，值在0～999之間，可把K看成由三個(gè)關(guān)鍵字(K1，K2，K3)組成，K1是百位數(shù)，K2是十位數(shù)，K3是個(gè)位數(shù)，每一個(gè)關(guān)鍵字的范圍相同(0≤K1，K2，K3≤9)。再如，若關(guān)鍵字K是由四個(gè)大寫字母組成的單詞，可把K看成由四個(gè)關(guān)鍵字(K1，K2，K3，K4)組成，K1是第四位(最高位)上的字母，K2是第三位(次高位)上的字母，依此類推，每一個(gè)關(guān)鍵字的范圍相同('A'≤K1，K2，K3，K4≤'Z')。按最低位優(yōu)先方法進(jìn)行排序：從最低位關(guān)鍵字起，按關(guān)鍵字的不同值將序列中的每個(gè)記錄“分配”到r個(gè)隊(duì)列中，然后再“收集”回到序列中，如此重復(fù)d次。其中，r是單關(guān)鍵字的取值范圍，又稱為基數(shù)，如上面實(shí)例中，數(shù)值關(guān)鍵字的r=10，字母組成關(guān)鍵字的r=26。d是K關(guān)鍵字分成的單關(guān)鍵字?jǐn)?shù)目，如上面實(shí)例中，數(shù)值關(guān)鍵字的d=3，字母組成關(guān)鍵字的d=4。圖8-12是鏈?zhǔn)交鶖?shù)排序的過程示意圖。待排序記錄的關(guān)鍵字均在0～999之間，將關(guān)鍵字K看成是由三個(gè)關(guān)鍵字(K1，K2，K3)組成的，K1是百位數(shù)，K2是十位數(shù)，K3是個(gè)位數(shù)，每一個(gè)關(guān)鍵字的范圍相同(0≤K1，K2，K3≤9)。r=10，d=3，按最低位優(yōu)先方法進(jìn)行排序。首先以動(dòng)態(tài)鏈表存儲(chǔ)所有待排序的記錄。令鏈表頭指針指向第一個(gè)記錄，并初始建立10個(gè)空的鏈隊(duì)列，如圖8-12(a)所示。第一趟“分配”：對(duì)所有記錄關(guān)鍵字的最低位即個(gè)位數(shù)進(jìn)行分配。按照每個(gè)記錄關(guān)鍵字的最低位將所有記錄分配至10個(gè)鏈隊(duì)列中，在每個(gè)鏈隊(duì)列中關(guān)鍵字的個(gè)位數(shù)相等。其中f[i]和e[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針，如圖8-12(b)所示。第一趟“收集”：鏈表頭指針指向第一個(gè)非空隊(duì)列的頭指針f[0]；修改每一個(gè)非空隊(duì)列尾指針，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，將所有非空隊(duì)列中的記錄重新鏈成一個(gè)鏈表，如圖8-12(c)所示。第二趟“分配”：先將10個(gè)隊(duì)列置空。對(duì)記錄關(guān)鍵字的十位數(shù)進(jìn)行分配。按照每個(gè)記錄關(guān)鍵字的十位數(shù)將所有記錄分配至10個(gè)鏈隊(duì)列中，在每個(gè)鏈隊(duì)列中關(guān)鍵字的十位數(shù)相等，如圖8-12(d)所示。圖8-12鏈?zhǔn)交鶖?shù)排序的示意圖第二趟“收集”：鏈表頭指針指向第一個(gè)非空隊(duì)列的頭指針f[0]。修改每一個(gè)非空隊(duì)列尾指針，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，將所有非空隊(duì)列中的記錄重新鏈成一個(gè)鏈表，如圖8-12(e)所示。第三趟“分配”、第三趟“收集”的過程和前面相同，分別如圖8-12(f)和圖8-12(g)所示。利用鏈?zhǔn)交鶖?shù)排序方法，經(jīng)過三趟“分配”和“收集”的操作最終實(shí)現(xiàn)了排序?；鶖?shù)排序的時(shí)間復(fù)雜度不僅與記錄的個(gè)數(shù)n有關(guān)，而且還與關(guān)鍵字的位數(shù)、關(guān)鍵字的基數(shù)有關(guān)。設(shè)關(guān)鍵字的基數(shù)為r，為建立r個(gè)空隊(duì)列所需的時(shí)間為O(r)。把n個(gè)記錄分配到各個(gè)隊(duì)列中并重新收集起來所需的時(shí)間為O(n)，因此一遍排序所需的時(shí)間為O(n+r)。若每個(gè)關(guān)鍵字有d位，則總共要進(jìn)行d遍排序，所以基數(shù)排序的時(shí)間復(fù)雜度就是O(d(n+r))?；鶖?shù)排序是穩(wěn)定排序。8.7排序方法的比較

1．穩(wěn)定性比較直接插入排序、冒泡排序、二路歸并和基數(shù)排序是穩(wěn)定排序。希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定排序。

2．復(fù)雜性比較排序方法時(shí)間復(fù)雜度與空間復(fù)雜度的比較如表8-1所示。表8-1各種排序方法時(shí)間復(fù)雜度與空間復(fù)雜度的比較綜上所述，可以得出如下結(jié)論：

(1)在平均情況下，希爾排序、快速排序、堆排序以及歸并排序方法都能達(dá)到較快的排序速度。進(jìn)一步分析可知，快速排序最快。從空間消耗來看，堆排序最省空間。

(2)在平均情況下，簡(jiǎn)單插入排序、冒泡排序法的排序速度較慢，但參加排序的序列開始就局部有序時(shí)，這兩種排序方法能達(dá)到較快的排序速度。最好的情況下，時(shí)間復(fù)雜度為O(n)，比上面敘述的方法要好一些，而且這兩種方法在多數(shù)情況下可根據(jù)不同情況與上述方法結(jié)合使用。

(3)從算法結(jié)構(gòu)的簡(jiǎn)單性來看，簡(jiǎn)單選擇排序法與冒泡排序比較簡(jiǎn)單和直接；希爾排序、快速排序、堆排序以及歸并排序方法都可以看做是對(duì)某一種排序法的進(jìn)一步改進(jìn)。相對(duì)而言，改進(jìn)后的排序法對(duì)應(yīng)的算法可能比較復(fù)雜。

(4)從參加排序的記錄數(shù)組的規(guī)模大小來看，n越小，采用簡(jiǎn)單排序方法的效率越高；n越大，采用改進(jìn)的排序方法的效率越高。因?yàn)閚越小，n2與log2n的差距越小，并且簡(jiǎn)單排序算法的時(shí)間復(fù)雜度的系數(shù)均小于1(除冒泡排序法的最壞情況以外)，而改進(jìn)的排序方法的時(shí)間復(fù)雜度的系數(shù)均大于1。這同時(shí)也使得它們之間的差距變小。

(5)基數(shù)排序方法需要的輔助空間較多，但其時(shí)間復(fù)雜度可以簡(jiǎn)化為O(dn)；當(dāng)K關(guān)鍵字分成的單關(guān)鍵字?jǐn)?shù)目較少時(shí)，可進(jìn)一步簡(jiǎn)化成O(n)，此時(shí)能達(dá)到較快的排序速度。小結(jié)

本章主要介紹了插入排序、交換排序、選擇排序和歸并排序，在這四種排序思想的基礎(chǔ)上解決了排序的實(shí)際應(yīng)用問題。回顧這些內(nèi)容，應(yīng)重點(diǎn)理解和掌握以下內(nèi)容：

(1)直接插入排序和希爾排序都是插入排序。直接插入排序是依次將記錄序列中的每一個(gè)記錄插入到有序段中，使有序段的長(zhǎng)度不斷擴(kuò)大，即在前i-1個(gè)有序記錄的基礎(chǔ)上，插入第i個(gè)記錄，將有序記錄的個(gè)數(shù)變?yōu)閕個(gè)。希爾排序是依據(jù)間隔數(shù)劃分子序列，對(duì)各個(gè)子序列采用直接插入法進(jìn)行排序，并不斷縮小間隔數(shù)實(shí)現(xiàn)最終的排序。

(2)冒泡排序和快速排序都是交換排序。冒泡排序是通過一次交換消除一個(gè)逆序，而快速排序是通過一次交換消除多個(gè)逆序。

(3)簡(jiǎn)單選擇排序、樹形選擇排序和堆排序都是選擇排序。簡(jiǎn)單選擇排序是在待排序列中選擇一個(gè)關(guān)鍵字最小的記錄與此時(shí)待排序列中的第一個(gè)記錄交換。而樹形選擇排序和堆排序正是在簡(jiǎn)單選擇排序的基礎(chǔ)上發(fā)展而來的，比簡(jiǎn)單選擇排序的效率高。

(4)二路歸并排序是將兩個(gè)有序的子序列合并成一個(gè)有序的序列。反復(fù)利用這種方法，可以實(shí)現(xiàn)排序。

(5)基數(shù)排序是借助于“分配”和“收集”兩種操作來實(shí)現(xiàn)對(duì)單邏輯關(guān)鍵字的排序。應(yīng)理解和掌握上述各種排序方法，會(huì)應(yīng)用上述各種排序方法進(jìn)行相應(yīng)的排序。習(xí)題

一、填空題

1．每次從無序記錄中取出一個(gè)元素，把它插入到有序記錄中的適當(dāng)位置，此種排序方法叫做

排序；每次從無序記錄中挑選出一個(gè)最小或最大元素，把它交換到有序記錄的一端，此種排序方法叫做

排序。

2．每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做

排序。

3．假定一組記錄的關(guān)鍵字為(46，79，56，38，40，80)，對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為

。

4．在簡(jiǎn)單選擇排序中，記錄比較次數(shù)的時(shí)間復(fù)雜度為

，記錄移動(dòng)次數(shù)的時(shí)間復(fù)雜度為

。

5．在快速排序方法中，進(jìn)行每次劃分時(shí)，是從當(dāng)前待排序區(qū)間的

向

依次查找出處于逆序的元素并交換之，最后將基準(zhǔn)元素交換到一個(gè)確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后兩個(gè)子區(qū)間。

6．在堆排序的過程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行

次篩選運(yùn)算，由初始堆排序結(jié)束，需要對(duì)樹根結(jié)點(diǎn)進(jìn)行

次篩選運(yùn)算。

7．假設(shè)一組記錄的關(guān)鍵字為(46，32，56，89，40，21)，則利用堆排序方法建立的初始堆為

。

8．快速排序在平均情況下的時(shí)間復(fù)雜度為

，在最壞情況下的時(shí)間復(fù)雜度為

。

9．快速排序在平均情況下的空間復(fù)雜度為

，在最壞情況下的空間復(fù)雜度為

。

10．在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩選運(yùn)算的時(shí)間復(fù)雜度為

，對(duì)整個(gè)堆排序過程的時(shí)間復(fù)雜度為

。

11．直接插入排序設(shè)置監(jiān)視哨的作用是

，希爾排序中通過

實(shí)現(xiàn)此功能。

12．快速排序在

的情況下最易發(fā)揮其長(zhǎng)處，在

情況下最不利于發(fā)揮其長(zhǎng)處。

13．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)，堆排序是一種

排序，堆實(shí)質(zhì)上是一棵

結(jié)點(diǎn)的層次序列。

14．關(guān)鍵字序列為(25，56，12，32，6，21，49，37，56，19，78，40)，按照關(guān)鍵字遞增的次序進(jìn)行排序。若采用初始間隔數(shù)為3的希爾排序，則進(jìn)行一趟排序的結(jié)果是

；若采用以第一個(gè)元素為支點(diǎn)的快速排序，則進(jìn)行一趟排序的結(jié)果是

。

15．在排序過程中，一般主要進(jìn)行的兩種基本操作是關(guān)鍵字的

和記錄的

。二、選擇題

1．每趟排序都從未排序的序列中挑選一個(gè)值最小(或最大)的記錄，然后將其與未排序的序列的第一個(gè)記錄交換位置。這種排序稱為()。

A.插入排序法 B.選擇排序法

C.冒泡排序法 D.快速排序法

2．在下述的排序方法中，不屬于內(nèi)排序方法的是()。

A.插入排序法 B.選擇排序法

C.拓?fù)渑判蚍?D.堆排序法

3．每趟排序從未排序的子序列中依次取出記錄與已經(jīng)排好序的序列中的記錄進(jìn)行比較，然后將其放在已經(jīng)有序序列的合適位置，這種排序稱為()。

A.插入排序法 B.選擇排序法

C.冒泡排序法 D.快速排序法

4．對(duì)具有n個(gè)元素的任意序列采用直接插入排序法進(jìn)行排序，排序趟數(shù)為()。

A.?n-1 B.?n

C.?n+1

D.?log2n

5．第i趟排序?qū)ε判虻那皀-i+1個(gè)記錄做如下工作：從第一個(gè)記錄開始，相鄰兩個(gè)記錄比較，若前者大于后者，這兩個(gè)記錄交換位置，否則，這兩個(gè)記錄不交換位置。這種排序稱為()。

A.插入排序法 B.選擇排序法

C.冒泡排序法 D.堆排序法

6．對(duì)數(shù)據(jù)記錄序列(49，72，68，13，38，50，97，27)進(jìn)行排序，前三趟排序的結(jié)果依次為：第一趟，49，72，68，13，38，50，97，27；第二趟，49，68，72，13，38，50，97，27；第三趟，13，49，68，72，38，50，97，27。該排序采用的方法是()。

A.插入排序法 B.選擇排序法

C.冒泡排序法 D.堆排序法

7．對(duì)序列(49，38，65，97，76，13，47，50)采用直接插入排序法進(jìn)行排序，要把第7個(gè)元素47插入到已排序中，為尋找插入的合適位置需要進(jìn)行()次元素間的比較。

A.?3

B.?4

C.?5

D.?6

8．堆可以表示為一棵()。

A.滿二叉樹 B.完全二叉樹

C.二叉排序樹 D.線索二叉樹

9．下列的排序方法中，排序的比較次數(shù)與序列的初始排序狀態(tài)無關(guān)的是()。

A.快速排序法 B.插入排序法

C.冒泡排序法 D.以上無答案

10．下列排序方法中，()可能出現(xiàn)這種情況：當(dāng)原始序列已經(jīng)有序時(shí)，排序花費(fèi)的時(shí)間反而最多。

A.插入排序法 B.選擇排序法

C.快速排序法 D.堆排序法

11．一組記錄的關(guān)鍵字為(46，79，56，38，40，84)，則利用快速排序，以第一個(gè)記錄為支點(diǎ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)

12．對(duì)下列關(guān)鍵字序列采用快速排序進(jìn)行排序時(shí)，速度最快的情形是()。

A.?(21，25，5，17，9，23，30)

B.?(25，23，30，17，21，5，9)

C.?(21，9，17，30，25，23，5)

D.?(5，9，17，21，23，25，30)

13．下列四個(gè)序列中，堆是()。

A.?75，65，30，15，25，45，20，10

B.?75，65，45，10，30，25，20，15

C.?75，45，65，30，15，25，20，10

D.?75，45，65，10，25，30，20，15

14．將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是()。

A．N B．2N-1

C．2N D．N-1

15．排序的趟數(shù)與記錄序列的初始狀態(tài)有關(guān)的排序方法是()。

A．直接插入排序 B.簡(jiǎn)單選擇排序

C.冒泡排序 D.快速排序三、問答題

1．什么是內(nèi)部排序？什么是外部排序？什么是穩(wěn)定排序？什么是不穩(wěn)定排序？

2．請(qǐng)敘述簡(jiǎn)單選擇排序和堆排序的區(qū)別。

3．一個(gè)堆可以表示為一棵完全二叉樹。請(qǐng)敘述堆與二叉排序樹的區(qū)別。

4．請(qǐng)敘述直接插入排序、冒泡排序和簡(jiǎn)單選擇排序的過程。

5．在使用非遞歸方法實(shí)現(xiàn)快速排序時(shí)，通常要利用一個(gè)棧記憶排序區(qū)間的兩個(gè)端點(diǎn)。那么能否用隊(duì)列來代替這個(gè)棧？為什么？

6．請(qǐng)敘述希爾排序和二路歸并排序的過程。四、應(yīng)用題

1．已知序列(35，78，12，26，90，44，66，58)，請(qǐng)寫出對(duì)此序列采用直接插入排序方法、希爾排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。

2．已知序列(23，76，16，25，93，46，69，55)，請(qǐng)寫出對(duì)此序列采用冒泡排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。

3．已知序列(37，87，19，26，99，47，61，59)，請(qǐng)寫出對(duì)此序列采用快速排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。

4．已知序列(30，77，16，26，98，41，67，58)，請(qǐng)寫出對(duì)此序列采用簡(jiǎn)單選擇排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。

5．已知序列(47，83，29，26，19，57，23，69)，請(qǐng)寫出對(duì)此序列采用堆排序方法進(jìn)行升序排序時(shí)各趟所對(duì)應(yīng)的堆。

6．已知序列(47，83，10，26，19，88，23，96)，請(qǐng)寫出對(duì)此序列采用二路歸并排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。實(shí)訓(xùn)指導(dǎo)

一、排序方法實(shí)現(xiàn)

【實(shí)訓(xùn)目的】

(1)理解和掌握各種排序方法的思想，尤其是直接插入排序、希爾排序、冒泡排序、快速排序和二路歸并排序。

(2)利用以上排序方法實(shí)現(xiàn)對(duì)記錄的排序。

【實(shí)訓(xùn)內(nèi)容】

(1)按提示輸入10個(gè)記錄的關(guān)鍵字(即整形數(shù)據(jù))。

(2)程序達(dá)到的功能要求對(duì)輸入的10個(gè)記錄按照關(guān)鍵字的大小進(jìn)行排序，并且將其輸出。

(3)舉例說明如下：

10個(gè)記錄的關(guān)鍵字輸入為：921636225825114582

10個(gè)記錄的關(guān)鍵字輸出為：291116222536455882

【實(shí)現(xiàn)提示】將輸入的10個(gè)記錄從小到大排序，記錄數(shù)組從下標(biāo)為1的單元來存放。利用以上排序方法實(shí)現(xiàn)記錄從小到大排序，記錄從數(shù)組的1單元來存放，并且輸出?！緦?shí)現(xiàn)過程】#include"stdio.h"#defineMaxsize100//參見結(jié)構(gòu)8-1typedefintDatatype;typedefstruct{Datatypekey;}Recnode;Recnoder[Maxsize];voidinsertsort(Recnoder[],intn);//函數(shù)說明，參見算法8-1voidshellsort(Recnoder[],intn); //函數(shù)說明，參見算法8-2voidbubblesort(Recnoder[],intn); //函數(shù)說明，參見算法8-3intPartition(Recnode*r,intlow,inthigh); //參見算法8-4voidquicksort(Recnode*r,intstart,intend); //參見算法8-4voidselectsort(Recnoder[],intn); //參見算法8-5voidmerge(Recnode*r,intlow,intm,inthigh);//參見算法8-7voidonemerge(Recnode*r,intlenth,intn);//參見算法8-8voidmergesort(Recnode*r,intn);

//參見算法8-9voidmain(){inti; intn=10; //記錄數(shù)組中元素的個(gè)數(shù)，下標(biāo)從1開始

for(i=1;i<=10;i++) //輸入記錄元素，直接插入排序并輸出結(jié)果

scanf("%d",&r[i].key); insertsort(r,10); for(i=1;i<=10;i++) printf("%3d",r[i].key); printf("\n");

for(i=1;i<=10;i++) //輸入記錄元素，希爾排序并輸出結(jié)果

scanf("%d",&r[i].key); shellsort(r,10); for(i=1;i<=10;i++) printf("%3d",r[i].key); printf("\n"); for(i=1;i<=10;i++) //輸入記錄元素，冒泡排序并輸出結(jié)果

scanf("%d",&r[i].key); bubblesort(r,10); for(i=1;i<=10;i++)

printf("%3d