數(shù)據(jù)結(jié)構(gòu)-C語言描述（第三版）課件：內(nèi)部排序

內(nèi)部排序9.1排序的基本概念9.2插入類排序9.3交換類排序法9.4選擇類排序法9.5歸并排序9.6分配類排序9.7各種排序方法的綜合比較9.8總結(jié)與提高9.1排序的基本概念排序：有n個(gè)記錄的序列{R1，R2，…，Rn}，其相應(yīng)關(guān)鍵字的序列是{K1，K2，…，Kn}，相應(yīng)的下標(biāo)序列為1，2，…，n。通過排序，要求找出當(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}。

內(nèi)部排序：整個(gè)排序過程完全在內(nèi)存中進(jìn)行，稱為內(nèi)部排序。

外部排序：由于待排序記錄數(shù)據(jù)量太大，內(nèi)存無法容納全部數(shù)據(jù)，排序需要借助外部存儲(chǔ)設(shè)備才能完成，稱為外部排序。

穩(wěn)定排序和不穩(wě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)定的

；反之，當(dāng)相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中發(fā)生變化者，則稱所用的排序方法是不穩(wěn)定的。

在排序過程中，一般進(jìn)行兩種基本操作：（1）比較兩個(gè)關(guān)鍵字的大?。?/p>

（2）將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。

對(duì)于第二種操作，需要采用適當(dāng)?shù)卮鎯?chǔ)方式，即向量結(jié)構(gòu)、鏈表結(jié)構(gòu)以及記錄向量與地址向量結(jié)合的表示方法。我們重點(diǎn)來討論在向量存儲(chǔ)結(jié)構(gòu)上各種排序方法的實(shí)現(xiàn)。9.2插入類排序基本思想：在一個(gè)已排好序的記錄子集的基礎(chǔ)上，每一步將下一個(gè)待排序的記錄有序插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。

9.2.1直接插入排序基本操作是將第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è)記錄插入空位置即可。

{48}62357755143598{4862}357755143598{354862}7755143598{35486277}55143598{3548556277}143598{143548556277}3598{14353548556277}98{1435354855627798}下面給出了一個(gè)完整的直接插入排序?qū)嵗?。圖中大括號(hào)內(nèi)為當(dāng)前已排好序的記錄子集合。

假設(shè)待排序記錄存放在r[1..n]之中，為了提高效率，我們附設(shè)一個(gè)監(jiān)視哨r[0]，使得r[0]始終存放待插入的記錄。

voidInsSort(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r做直接插入排序，length為數(shù)組的長(zhǎng)度*/{for(i=2;i<length;i++){r[0]=r[i];j=i-1; /*將待插入記錄存放到r[0]中*/while(r[0].key<r[j].key)/*尋找插入位置*/{r[j+1]=r[j];j=j-1;}r[j+1]=r[0]; /*將待插入記錄插入到已排序的序列中*/}}/*InsSort*/

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

直接插入排序算法分析：從空間角度來看，它只需要一個(gè)輔助空間r[0]。

從時(shí)間耗費(fèi)角度來看，主要時(shí)間耗費(fèi)在關(guān)鍵字比較和移動(dòng)元素上。

直接插入排序方法是穩(wěn)定的排序方法。

9.2.2折半插入排序voidBinSort(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長(zhǎng)度*/{for(i=2;i<=length;++i){x=r[i];low=1;high=i-1;while(low<=high)/*確定插入位置l*/{mid=(low+high)/2;if(x.key<r[mid].key)high=mid-1;elselow=mid+1;}for(j=i-1;j>=low;--j)r[j+1]=r[j];/*記錄依次向后移動(dòng)*/r[low]=x;/*插入記錄*/}}

采用折半插入排序法，可減少關(guān)鍵字的比較次數(shù)。每插入一個(gè)元素，需要比較的次數(shù)最大為折半判定樹的深度，如插入第i個(gè)元素時(shí)，設(shè)i=2j,則需進(jìn)行l(wèi)og2i次比較，因此插入n-1個(gè)元素的平均關(guān)鍵字的比較次數(shù)為O(nlog2n)。

雖然折半插入排序法與直接插入排序法相比較，改善了算法中比較次數(shù)的數(shù)量級(jí)，但其并未改變移動(dòng)元素的時(shí)間耗費(fèi)，所以折半插入排序的總的時(shí)間復(fù)雜度仍然是O(n2)。

算法分析：9.2.3表插入排序

表插入排序是采用鏈表存儲(chǔ)結(jié)構(gòu)進(jìn)行插入排序的方法。表插入排序的基本思想是：先在待插入記錄之前的有序子鏈表中查找應(yīng)插入位置，然后將待插入記錄插入鏈表。

typedefintKeyType;typedefstruct{ KeyTypekey; OtherTypeother_data;intnext; }RecordType1;

類型說明如下：voidSLinkListSort(RecordType1r[],intlength){intn=length;r[0].next=n;r[n].next=0;for(i=n-1;i>=1;--i){p=

r[0].next；q=0;while(p>0&&r[p].key<

r[i].key)/*尋找插入位置*/{q=p;p=

r[p].next;}r[q].next=i; r[i].next=p;

/*修改指針，完成插入*/}}/*SLinkListSort*/

表插入排序算法算法分析：每插入一條記錄，最大的比較次數(shù)等于已排好序的記錄個(gè)數(shù)，即當(dāng)前循環(huán)鏈表長(zhǎng)度?？偟谋容^次數(shù)為：∑i＝i=1n-12n(n-1)≈2n2因此表插入排序的時(shí)間復(fù)雜度為T(n)=O(n2)。

9.4選擇類排序法

選擇排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。

9.4.1簡(jiǎn)單選擇排序基本思想：第i趟簡(jiǎn)單選擇排序是指通過n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。共需進(jìn)行i-1趟比較，直到所有記錄排序完成為止。

選擇排序示例見P240的圖9.5所示。簡(jiǎn)單選擇排序的算法描述如下：voidSelectSort(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，length為數(shù)組的長(zhǎng)度*/{n=length;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){x=r[i]；r[i]=r[k]；r[k]=x;}}}/*SelectSort*/簡(jiǎn)單選擇排序算法分析：

在簡(jiǎn)單選擇排序過程中，所需移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄。最壞情況下，即待排序記錄初始狀態(tài)是按逆序排列的，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。進(jìn)行比較操作的時(shí)間復(fù)雜度為O(n2)。

9.4.2樹型選擇排序

樹型選擇排序也稱作錦標(biāo)賽排序。它的基本思想是：先把待排序的n個(gè)記錄的關(guān)鍵字兩兩進(jìn)行比較，取出較小者。然后再在

n/2

個(gè)較小者中，采用同樣的方法進(jìn)行比較選出每?jī)蓚€(gè)中的較小者，如此反復(fù)，直至選出最小關(guān)鍵字記錄為止。

例如p241的圖9.6所示的樹型選擇排序38491389765654922727137613381313(a)選出最小關(guān)鍵字1338491389765654922727∞7676382727(b)選出次小關(guān)鍵字27

在樹型選擇排序中，被選中的關(guān)鍵字都是走了一條由葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的比較的過程,由于含有n個(gè)葉子節(jié)點(diǎn)的完全二叉數(shù)的深度為

log2n

+1，則在樹型選擇排序中，每選擇一個(gè)小關(guān)鍵字需要進(jìn)行

log2n

次比較，因此其時(shí)間復(fù)雜度為O(nlog2n)。移動(dòng)記錄次數(shù)不超過比較次數(shù)，故總的算法時(shí)間復(fù)雜度為O(nlog2n)。

算法分析：9.4.3堆排序

堆排序是對(duì)樹型選擇排序的進(jìn)一步改進(jìn)。采用堆排序時(shí)，只需要一個(gè)記錄大小的輔助空間。堆排序是在排序過程中，將向量中存儲(chǔ)的數(shù)據(jù)看成一棵完全二叉樹，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇關(guān)鍵字最小的記錄，即待排序記錄仍采用向量數(shù)組方式存儲(chǔ)，并非采用樹的存儲(chǔ)結(jié)構(gòu)，而僅僅是采用完全二叉樹的順序結(jié)構(gòu)的特征進(jìn)行分析而已。

具體做法：

把待排序的記錄的關(guān)鍵字存放在數(shù)組r[1..n]之中，將r看成是一棵完全二叉樹的順序表示，每個(gè)結(jié)點(diǎn)表示一個(gè)記錄，第一個(gè)記錄r[1]作為二叉樹的根，以下各記錄r[2...n]依次逐層從左到右順序排列，任意結(jié)點(diǎn)r[i]的左孩子是r[2i],右孩子是r[2i+1],雙親是r[

i/2

]。對(duì)這棵完全二叉樹進(jìn)行調(diào)整，使各結(jié)點(diǎn)的關(guān)鍵字值滿足下列條件：r[i].key≥r[2i].key并且r[i].key≥r[2i+1].key(i=1,2,...

n/2

)，滿足這個(gè)條件的完全二叉樹為堆。

堆中根結(jié)點(diǎn)的關(guān)鍵字最大，稱為大根堆。反之，如果這棵完全二叉樹中任意結(jié)點(diǎn)的關(guān)鍵字大于或者等于其左孩子和右孩子的關(guān)鍵字（當(dāng)有左孩子或右孩子時(shí)），對(duì)應(yīng)的堆為小根堆。

一個(gè)大根堆和一個(gè)小根堆的示例見p242的圖9.7所示。98773562551435

48(a)一個(gè)大根堆14483562559835

77(b)一個(gè)小根堆堆排序的過程主要需要解決兩個(gè)問題：(1)按堆定義建初堆（2）去掉最大元之后重建堆，得到次大元。

問題1:當(dāng)堆頂元素改變時(shí)，如何重建堆?

首先將完全二叉樹根結(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)中。此時(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)即可。上述調(diào)整方法相當(dāng)于把待調(diào)整記錄逐步向下“篩”的過程，所以一般稱為“篩選”法。

篩選過程示例見p243的圖9.8所示。篩選算法為：voidsift（RecordTyper[],intｋ，intｍ）

/*假設(shè)ｒ[k..m]是以ｒ[k]為根的完全二叉樹，且分別以ｒ[2k]和ｒ[2k+1]為根的左、右子樹為大根堆，調(diào)整r[k]，使整個(gè)序列r[k..m]滿足堆的性質(zhì)*/{t=r[k]；/*暫存“根”記錄r[k]*/x=r[k].key；i=k；j=2*i；finished=FALSE；

while(j<=m&&!finished){if(j<m&&r[j].key<r[j+1].key)j=j+1；

/*若存在右子樹，且右子樹根的關(guān)鍵字大，則沿右分支“篩選”*/

if(x>=r[j].key)finished=TRUE；/*篩選完畢*/else{r[i]=r[j]；i=j；j=2*i；}/*繼續(xù)篩選*/}r[i]=t;/*r[k]填入到恰當(dāng)?shù)奈恢?/}/*sift*/問題2:如何由一個(gè)任意序列建初堆？

一個(gè)任意序列看成是對(duì)應(yīng)的完全二叉樹，由于葉結(jié)點(diǎn)可以視為單元素的堆，因而可以反復(fù)利用“篩選”法，自底向上逐層把所有子樹調(diào)整為堆，直到將整個(gè)完全二叉樹調(diào)整為堆。

建堆算法如下：voidcrt_heap(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r建堆，length為數(shù)組的長(zhǎng)度*/{n=length;for(i=n/2

;i>=1;--i)/*自第個(gè)記錄開始進(jìn)行篩選建堆*/sift(r，i，n)；}例如，已知關(guān)鍵字序列：｛48，62，35，77，55，14，35

，98｝，要求將其篩選為一個(gè)堆。在此，n=8，所以應(yīng)從第４個(gè)結(jié)點(diǎn)77開始篩選。建堆過程見P244的圖9.9。圖中箭頭所指為當(dāng)前待篩結(jié)點(diǎn)。

問題3:如何利用堆進(jìn)行排序？

進(jìn)行堆排序的步驟：①將待排序記錄按照堆的定義建初堆（算法9.10），并輸出堆頂元素；②調(diào)整剩余的記錄序列，利用篩選法將前n-i個(gè)元素重新篩選建成為一個(gè)新堆，再輸出堆頂元素；③重復(fù)執(zhí)行步驟②n-1次進(jìn)行篩選,

新篩選成的堆會(huì)越來越小，而新堆后面的有序關(guān)鍵字會(huì)越來越多，最后使待排序記錄序列成為一個(gè)有序的序列，這個(gè)過程稱之為堆排序。

完整的堆排序過程見p246的圖9.10,圖中箭頭所指為當(dāng)前堆尾結(jié)點(diǎn)。堆排序的算法為：voidHeapSort（RecordTyper[],intlength）

/*對(duì)r[1..n]進(jìn)行堆排序，執(zhí)行本算法后，r中記錄按關(guān)鍵字由大到小有序排列*/{crt_heap（r,length）；n=length;for(i=n;i>=2;--i){b=r[1];/*將堆頂記錄和堆中的最后一個(gè)記錄互換*/r[1]=r[i]r[i]=b;sift(r，1，i-1)；/*進(jìn)行調(diào)整，使r[1..i-1]變成堆*/}}/*HeapSort*/堆排序算法分析：

堆排序的時(shí)間主要耗費(fèi)在建初始堆和調(diào)整建新堆時(shí)進(jìn)行的反復(fù)“篩選”上。對(duì)深度為k的堆，篩選算法中進(jìn)行的關(guān)鍵字的比較次數(shù)至多為2（k-1）次，則在建含n個(gè)元素、深度為h的堆時(shí)，總共進(jìn)行的關(guān)鍵字比較次數(shù)不超過4n。另外，n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：

log2n

+1，則調(diào)整建新堆時(shí)調(diào)用sift過程n-1次總共進(jìn)行的比較次數(shù)不超過：

2(

log2(n-1)

+

log2(n-2)

+…+

log22

<2n

log2n

因此，堆排序在最壞情況下，其時(shí)間復(fù)雜度也為O(nlog2n)，這是堆排序的最大優(yōu)點(diǎn)。

堆排序是一種不穩(wěn)定的排序方法，它不適用于待排序記錄個(gè)數(shù)n較少的情況，但對(duì)于n較大的文件還是很有效的。

9.5歸并排序基本思想是將兩個(gè)或兩個(gè)以上有序表合并成一個(gè)新的有序表。假設(shè)初始序列含有n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到

n/2

個(gè)長(zhǎng)度為2（n為奇數(shù)時(shí)，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列；在此基礎(chǔ)上，再進(jìn)行兩兩歸并，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。這種方法被稱作2-路歸并排序。

歸并排序的示例為：(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13,19,27)(01,16,26,31)(01,05,13,16,19,26,27,31)2-路歸并排序法的基本操作是將待排序列中相鄰的兩個(gè)有序子序列合并成一個(gè)有序序列。合并算法描述如下：voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper[])/*已知r1[low..mid]和r1[mid+1..high]分別按關(guān)鍵字有序排列，將它們合并成一個(gè)有序序列，存放在r[low..high]*/{i=low；j=mid+1；k=low；while((i<=mid)&&(j<=high)){if(r1[i].key<=r1[j].key){r[k]=r1[i]；++i；}else {r[k]=r1[j]；++j；}++k；}if(i<=mid)r[k..high]=r1[i..mid]；if(j<=high)r[k..high]=r1[j..high]；}/*Merge*/2-路歸并排序可以采用遞歸方法實(shí)現(xiàn)，具體描述如下：

voidMergeSort(RecordTyper1[],intlow,inthigh,RecordTyper[])/*r1[low..high]經(jīng)過排序后放在r[low..high]中，r2[low..high]為輔助空間*/{RecordType*r2；

r2=(RecordType*)malloc(sizeof(RecordType)*(hight-low+1));if(low==high

)r[low]=r1[low]；else{mid=(low+high)/2；MergeSort(r1，low，mid,r2)；

MergeSort(r1，mid+1，high,r2)；Merge(r2，low，mid，high，r)；}free(r2);}/*MergeSort*/歸并排序的算法分析：歸并排序中一趟歸并中要多次用到2-路歸并算法，一趟歸并排序的操作是調(diào)用

n/2h

次算法merge將r1[1…n]中前后相鄰且長(zhǎng)度為h的有序段進(jìn)行兩兩歸并，得到前后相鄰、長(zhǎng)度為2h的有序段，并存放在r[1…n]中，其

時(shí)間復(fù)雜度為O(n)。整個(gè)歸并排序需進(jìn)行m（m=log2n）趟2-路歸并，所以歸并排序總的時(shí)間復(fù)雜度為O（nlog2n）。在實(shí)現(xiàn)歸并排序時(shí)，需要和待排記錄等數(shù)量的輔助空間，空間復(fù)雜度為O(n)。

歸并排序的最大特點(diǎn)是，它是一種穩(wěn)定的排序方法。

類似2-路歸并排序，可設(shè)計(jì)多路歸并排序法，歸并的思想主要用于外部排序。外部排序可分兩步，①待排序記錄分批讀入內(nèi)存，用某種方法在內(nèi)存排序，組成有序的子文件，再按某種策略存入外存。②子文件多路歸并，成為較長(zhǎng)有序子文件，再記入外存，如此反復(fù)，直到整個(gè)待排序文件有序。

外部排序可使用外存、磁帶、磁盤，最初形成有序子文件長(zhǎng)取決于內(nèi)存所能提供排序區(qū)大小和最初排序策略，歸并路數(shù)取決于所能提供排序的外部設(shè)備數(shù)。

9.6分配類排序

分配類排序則利用分配和收集兩種基本操作，基數(shù)類排序就是典型的分配類排序。

9.6.1多關(guān)鍵字排序

例如：我們可以將一副撲克牌的排序過程看成由花色和面值兩個(gè)關(guān)鍵字進(jìn)行排序的問題。若規(guī)定花色和面值的順序如下：花色：梅花<方塊<紅桃<黑桃面值：A<2<3<…<10<J<Q<K并進(jìn)一步規(guī)定花色的優(yōu)先級(jí)高于面值，則一副撲克牌從小到大的順序?yàn)椋好坊ˋ，梅花2，…，梅花K；方塊A，方塊2，…，方塊K；紅桃A，紅桃2，…，紅桃K；黑桃A，黑桃2，…，黑桃K。具體進(jìn)行排序時(shí)有兩種做法，其中一種是：先按花色分成有序的四類，然后再按面值對(duì)每一類從小到大排序。該方法稱為“高位優(yōu)先”排序法。另一種做法是分配與收集交替進(jìn)行。首先按面值從小到大把牌擺成13疊（每疊4張牌），然后將每疊牌按面值的次序收集到一起，再對(duì)這些牌按花色擺成4疊，每疊有13張牌，最后把這4疊牌按花色的次序收集到一起，于是就得到了上述有序序列。該方法稱為“低位優(yōu)先”排序法。撲克牌的洗牌過程9.6.2鏈?zhǔn)交鶖?shù)排序

基數(shù)排序?qū)儆谏鲜觥暗臀粌?yōu)先”排序法，通過反復(fù)進(jìn)行分配與收集操作完成排序。

排序時(shí)先按最低位的值對(duì)記錄進(jìn)行初步排序，在此基礎(chǔ)上再按次低位的值進(jìn)行進(jìn)一步排序。依此類推，由低位到高位，每一趟都是在前一趟的基礎(chǔ)上，根據(jù)關(guān)鍵字的某一位對(duì)所有記錄進(jìn)行排序，直至最高位，這樣就完成了基數(shù)排序的全過程。

具體實(shí)現(xiàn)時(shí)，一般采用鏈?zhǔn)交鶖?shù)排序。我們首先通過一個(gè)具體的例子來說明鏈?zhǔn)交鶖?shù)排序的基本過程。

(a)初始狀態(tài)

(b)第一趟分配之后

(c)第一趟收集之后

(d)第二趟分配之后

(e)第二趟收集之后

(f)第三趟分配之后

(g)第三趟收集之后的有序文件

鏈?zhǔn)交鶖?shù)排序示例

為了有效地存儲(chǔ)和重排記錄，算法采用靜態(tài)鏈表。有關(guān)數(shù)據(jù)類型的定義如下：

#defineRADIX10#defineKEY_SIZE6#defineLIST_SIZE20typedefintKeyType;typedefstruct{ KeyTypekeys[KEY_SIZE];/*子關(guān)鍵字?jǐn)?shù)組*/ OtherTypeother_data;/*其它數(shù)據(jù)項(xiàng)*/

intnext;/*靜態(tài)鏈域*/ }RecordType1;typedefstruct{RecordType1r[LIST_SIZE+1];/*r[0]為頭結(jié)點(diǎn)*/ intlength; intkeynum;}SLinkList;/*靜態(tài)鏈表*/typedefintPVector[RADIX];

鏈?zhǔn)交鶖?shù)排序的有關(guān)算法描述如下：

voidDistribute(RecordType1r[],inti,PVectorhead,PVectortail)/*記錄數(shù)組r中記錄已按低位關(guān)鍵字key[i+1]，…，key[d]進(jìn)行過“低位優(yōu)先”排序。本算法按第i位關(guān)鍵字key[i]建立RADIX個(gè)隊(duì)列，同一個(gè)隊(duì)列中記錄的key[i]相同。head[j]和tail[j]分別指向各隊(duì)列中第一個(gè)和最后一個(gè)記錄（j=0，1，2，…，RADIX-1）。head[j]=0表示相應(yīng)隊(duì)列為空隊(duì)列*/{for(j=0;j<=RADIX-1;++j)head[j]=0；/*將RADIX個(gè)隊(duì)列初始化為空隊(duì)列*/p=r[0].next；/*p指向鏈表中的第一個(gè)記錄*/while(p!=0){j=Order(r[p].key[i])；/*用記錄中第i位關(guān)鍵字求相應(yīng)隊(duì)列號(hào)*/if(head[j]==0)head[j]=p;/*將p所指向的結(jié)點(diǎn)加入第j個(gè)隊(duì)列中*/elser[tail[j]].next=p；

tail[j]=p；p=r[p].next；}}/*Distribute*/voidCollect(RecordTyper[],PVectorhead,PVectortail)/*本算法從0到RADIX-1

掃描各隊(duì)列，將所有非空隊(duì)列首尾相接，重新鏈接成一個(gè)鏈表*/{j=0；while(head[j]==0)/*找第一個(gè)非空隊(duì)列*/++j；r[0].next=head[j]；t=tail[j]；while(j<RADIX-1)/*尋找并串接所有非空隊(duì)列*/{++j；

while((j<RADIX-1)&&(head[j]==0))/*找下一個(gè)非空隊(duì)列*/++j；if(head[j]!=0)/*鏈接非空隊(duì)列*/{r[t].next=head[j]；t=tail[j]；}}r[t].next=0;/*t指向最后一個(gè)非空隊(duì)列中的最后一個(gè)結(jié)點(diǎn)*/}/*Collect*/voidRadixSort(RecordTyper[],intlength)/*length個(gè)記錄存放在數(shù)組r中，執(zhí)行本算法進(jìn)行基數(shù)排序后，鏈表中的記錄將按關(guān)鍵字從小到大的順序相鏈接。*/{n=length；for(i=0;i<=n-1;++i)r[i].next=i+1；/*構(gòu)造靜態(tài)鏈表*/r[n].next=0；d=keynum；for(i=d-1;i>=0;--i)/*從最低位子關(guān)鍵字開始，進(jìn)行d趟分配和收集*/{Distribute(r，i，head，tail)；/*第i趟分配*/Collect(r，head，tail)/*第i趟收集*/}}/*RadixSort*/基數(shù)排序的算法分析：

對(duì)于ｎ個(gè)記錄（每個(gè)記錄含ｄ個(gè)子關(guān)鍵字，每個(gè)子關(guān)鍵字的取值范圍為RADIX個(gè)值）進(jìn)行鏈?zhǔn)脚判虻臅r(shí)間復(fù)雜度為Ｏ(ｄ(ｎ＋RADIX))，其中每一趟分配算法的時(shí)間復(fù)雜度為Ｏ(ｎ)，每一趟收集算法的時(shí)間復(fù)雜度為Ｏ(RADIX)，整個(gè)排序進(jìn)行ｄ趟分配和收集，所需輔助空間為２×RADIX個(gè)隊(duì)列指針。當(dāng)然，由于需要鏈表作為存儲(chǔ)結(jié)構(gòu)，則相對(duì)于其它以順序結(jié)構(gòu)存儲(chǔ)記錄的排序方法而言，還增加了ｎ個(gè)指針域空間。

9.6.3

基數(shù)排序的順序表結(jié)構(gòu)基數(shù)排序法也可以利用順序方式實(shí)現(xiàn)。例如：關(guān)鍵字k1k2k3，先按k3掃描一遍，分別記下k3位為0的記錄個(gè)數(shù)，為1的記錄個(gè)數(shù)，…為9的記錄個(gè)數(shù)。之后形成兩個(gè)計(jì)數(shù)數(shù)組num[10]和cpos[10]，對(duì)上例中按k3位統(tǒng)計(jì)的結(jié)果下所示：0123456789num[]1002110023cpos[]01224566689.7各種排序方法的綜合比較首先從算法的平均時(shí)間復(fù)雜度、

最壞時(shí)間復(fù)雜度、以及算法所需的輔助存儲(chǔ)空間三方面，對(duì)各種排序方法加以比較。排序方法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度輔助存儲(chǔ)空間簡(jiǎn)單排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序O(nlogn)O(nlogn)O(1)歸并排序O(nlogn)O(nlogn)O(n)基數(shù)排序O(d(n+rd))O(d(n+rd))O(rd)各種排序方法的性能比較通過分析和比較，可以得出以下結(jié)論：簡(jiǎn)單排序一般只用于n值較小的情況；歸并排序適用于n值較大的情況；基數(shù)排序適用于n值很大而關(guān)鍵字的位數(shù)d較小的序列；快速排序是排序方法中最好的方法。從排序的穩(wěn)定性來看，基數(shù)排序是穩(wěn)定的，除了簡(jiǎn)單選擇排序，其它各種簡(jiǎn)單排序法也是穩(wěn)定的。多數(shù)情況下，排序是按記錄的主關(guān)鍵字進(jìn)行的，此時(shí)不用考慮排序方法的穩(wěn)定性。如果排序是按記錄的次關(guān)鍵字進(jìn)行的，則應(yīng)充分考慮排序方法的穩(wěn)定性。9.8總結(jié)與提高9.8.1主要知識(shí)點(diǎn)1.本章共介紹了插入、交換、選擇、、歸并、分配這5類內(nèi)排序算法，均為基于比較的排序，即排序過程的實(shí)現(xiàn)主要靠關(guān)鍵字的關(guān)系大小比較。理解各類排序的基本方法非常重要。2.熟練掌握三種簡(jiǎn)單排序方法（直接插入、冒泡排序、簡(jiǎn)單選擇）的基本思想和算法描述,掌握這些排序法的特點(diǎn)和適用情況，并能應(yīng)用分析。3.掌握三種改進(jìn)排序方法（希爾排序、快速排序、堆排序）的基本思路,掌握這些排序法的特點(diǎn)和適用情況，并能根據(jù)特點(diǎn)給出應(yīng)用分析。4.理解歸并排序法的基本思想和算法描述。5.掌握基數(shù)排序法基本思想和兩種實(shí)現(xiàn)途徑。6.證明一種排序方法是穩(wěn)定的，要從算法本身的步驟中加以證明。證明排序方法是不穩(wěn)定的，只需給出一個(gè)反例說明。

9.8.2典型題例例1：排序方法選擇①設(shè)有10000個(gè)無序元素，僅要求找出前10個(gè)最小元素，在下列排序方法中（歸并排序、基數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？

解：待排序元素1萬，僅需找出前10個(gè)最小元素，因此并不需要整個(gè)排序；在所給定的方法中，調(diào)用堆排序中的一趟排序，即可通過最小堆找出一個(gè)最小值，每趟排序只需僅需10次調(diào)用一趟排序，即可達(dá)到要求結(jié)果。而其他的歸并排序、基數(shù)排序、快速排序、插入排序方法均要全部排好才可達(dá)到要求,因此選擇堆排序最好。

②對(duì)長(zhǎng)度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這n個(gè)元素的初始排列。分析其最壞與最好情況，對(duì)n=7給出一個(gè)最好情況的初始排列實(shí)例。

解：快速排序算法是平均排序性能最好的算法之一。快速排序最壞情況是序列有序，每次以樞軸元素為界，序列分為兩個(gè)子表，一個(gè)子表為空，另一個(gè)子表為n-1個(gè)元素，快速排序蛻變?yōu)槊芭菖判颉？焖倥判蜃詈们闆r是這樣的排列，每次的樞軸元素放置的位置在表中間，正好能夠?qū)⑿蛄蟹譃閮蓚€(gè)長(zhǎng)度相當(dāng)?shù)淖颖?，此時(shí)快速排序性能類同折半判定樹的分析。其趟數(shù)為log2n」

+1。n=7時(shí)一個(gè)最好情況的初始排列實(shí)例為：[4，1，3，2，6，5，7]第一趟劃分結(jié)果為：[2，1，3]4[6，5，7]第二趟劃分結(jié)果為：[1]，2，[3]4[5]，6，[7]

最終的排序結(jié)果為：

1，2，3，

4，5，6，7例2：荷蘭國(guó)旗問題假設(shè)有一個(gè)僅由紅、白、藍(lán)三種顏色的條塊組成的序列，需要在O(n)時(shí)間內(nèi)將這些條塊按紅、白、藍(lán)的順序排好，即排成荷蘭國(guó)旗圖案。例如，給定彩色條塊序列為：﹛藍(lán)、白、紅、白、藍(lán)、紅、白、白、紅、藍(lán)﹜則要求排列結(jié)果為：﹛紅、紅、紅、白、白、白、白、藍(lán)、藍(lán)、藍(lán)﹜

【問題分析】這個(gè)問題實(shí)際上是一種排序的問題，它要按顏色值（紅<白<藍(lán)）的順序?qū)@些條塊序列進(jìn)行排序。如果用1、2、3分別代表紅、白、藍(lán)三種顏色，那么就可以直接使用比較運(yùn)算符進(jìn)行比較，利用本章的排序算法進(jìn)行排序。但是一般的排序算法的時(shí)間復(fù)雜度都大于O(n)，因此不能直接使用，必須加以改進(jìn)。

方法一：采用簡(jiǎn)單選擇排序思想

【算法思想】假設(shè)這些條塊顏色依次存放在L[0..n-1]中，利用簡(jiǎn)單選擇排序思想，首先從序列中選取所有的紅色條塊，依次放到序列的前面，然后再?gòu)氖Ｓ嗟男蛄兄羞x取所有的白色條塊，依次放到紅色條塊后面。這樣經(jīng)過兩趟選擇后，整個(gè)序列就按紅、白、藍(lán)有序。由于每一趟選擇的時(shí)間復(fù)雜度為O(n)，所以整個(gè)過程的時(shí)間復(fù)雜度也為O(n)。

【算法描述】voidSort(intL[],intn)/*條塊顏色依次存放在L[0..n-1]中，本算法利用簡(jiǎn)單選擇排序思想，將整個(gè)序列按紅、白、藍(lán)進(jìn)行排序。*/﹛inti,j,x;i=0;/*i指向第一個(gè)紅色條塊應(yīng)該放的位置*/for(j=i;j<n;j++)

/*j掃描所有尚未放置好的條塊，尋找紅色條塊*/if(L[j]==1)

/*找到一個(gè)紅色條塊*/﹛if(j!=i)

/*找到的紅色條塊不在下一個(gè)紅色條塊應(yīng)該放的位置則換位*/{x=L[j];L[j]=L[i];L[i]=x;}i++;/*i指向下一個(gè)紅色條塊應(yīng)該放的位置*/﹜

/*退出前面循環(huán)后，i指向第一個(gè)白色條塊應(yīng)該放的位置*/for(j=i;j<n;j++)/*j掃描所有尚未放置好的條塊，尋找白色條塊*/if(L[j]==2)/*找到一個(gè)白色條塊*/﹛if(j!=i)/*找到的白色條塊不在下一個(gè)白色條塊應(yīng)該放的位置則換位*/﹛x=L[j];L[j]=L[i];L[i]=x;﹜i++;/*i指向下一個(gè)白色條塊應(yīng)該放的位置*/﹜﹜

方法二：采用快速排序思想

【算法思想】上述算法思想比較簡(jiǎn)單，但使用了兩個(gè)幾乎完全一樣的循環(huán)，使得算法顯得過于冗長(zhǎng)。下面利用快速排序中對(duì)序列進(jìn)行劃分的思想，這樣用一個(gè)循環(huán)就可以了。具體方法是：設(shè)置3個(gè)整型變