內(nèi)部排序課件

內(nèi)部排序9.1排序的基本概念9.2插入類排序9.3交換類排序法9.4選擇類排序法9.5歸并排序9.6分配類排序9.7各種排序方法的綜合比較9.8總結(jié)與提高練習題9.1排序的基本概念排序：有n個記錄的序列{R1，R2，…，Rn}，其相應關(guān)鍵字的序列是{K1，K2，…，Kn}，相應的下標序列為1，2，…，n。通過排序，要求找出當前下標序列1，2，…，n的一種排列p1，p2，…，pn，使得相應關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系，即：Kp1≤Kp2≤…≤Kpn

，這樣就得到一個按關(guān)鍵字有序的記錄序列：{Rp1，Rp2，…，Rpn}。

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

外部排序：由于待排序記錄數(shù)據(jù)量太大，內(nèi)存無法容納全部數(shù)據(jù)，排序需要借助外部存儲設(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)定的

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

在排序過程中，一般進行兩種基本操作：（1）比較兩個關(guān)鍵字的大??；

（2）將記錄從一個位置移動到另一個位置。

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

9.2.1直接插入排序基本操作是將第i個記錄插入到前面i-1個已排好序的記錄中，具體過程為：將第i個記錄的關(guān)鍵字Ki順次與其前面記錄的關(guān)鍵字Ki-1，Ki-2，…K1進行比較，將所有關(guān)鍵字大于Ki的記錄依次向后移動一個位置，直到遇見一個關(guān)鍵字小于或者等于Ki的記錄Kj，此時Kj后面必為空位置，將第i個記錄插入空位置即可。

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

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

voidInsSort(RecordTyper[],intlength)/*對記錄數(shù)組r做直接插入排序，length為數(shù)組的長度*/{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*/

直接插入排序算法對于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：該算法的要點是：①使用監(jiān)視哨r[0]臨時保存待插入的記錄。②從后往前查找應插入的位置。③查找與移動用同一循環(huán)完成。

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

從時間耗費角度來看，主要時間耗費在關(guān)鍵字比較和移動元素上。

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

9.2.2折半插入排序voidBinSort(RecordTyper[],intlength)/*對記錄數(shù)組r進行折半插入排序，length為數(shù)組的長度*/{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];/*記錄依次向后移動*/r[low]=x;/*插入記錄*/}}14364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r9.2.3希爾排序（又稱縮小增量排序）

基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。

所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。具體做法為：將記錄序列分成若干子序列，分別對每個子序列進行插入排序。

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

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

算法分析：例如：162512304711233691831

第一趟希爾排序，設(shè)增量d=5112312918162536304731第二趟希爾排序，設(shè)增量d=3918

121123

162531

304736第三趟希爾排序，設(shè)增量d=1911121618232530313647voidShellInsert(RecordTyper[],intlength,intdelta)

{

for(i=1+delta;i<=length;++i)

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

{r[0]=r[i];//暫存在R[0]

for(j=i-delta;j>0&&(r[0].key<r[j].key);j-=delta)L.r[j+delta]=r[j];//記錄后移，查找插入位置

r[j+delta]=r[0];//插入

}}//ShellInsertvoidShellSort(RecordTyper[],intlength,intdelta[],intn){//增量為delta[]的希爾排序,n為delta[]的長度

for(i=0;i<n-1;++i)ShellInsert(r,length,delta[i]);//一趟增量為delta[k]的插入排序}//ShellSort9.3交換類排序法9.3.1冒泡排序假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：第i趟起泡排序無序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到

n-i+1的位置上時間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進行一趟起泡“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進行n-1趟起泡“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：n-19.3.2快速排序

目標：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)樞軸

(i+1≤j≤t)。一、一趟快速排序（一次劃分）stlowhigh設(shè)R[s]=52為樞軸

將R[high].key和樞軸的關(guān)鍵字進行比較，要求R[high].key≥

樞軸的關(guān)鍵字

將R[low].key和樞軸的關(guān)鍵字進行比較，要求R[low].key≤

樞軸的關(guān)鍵字high23low80high14low52例如R[0]52lowhighhighhighlow

可見，經(jīng)過“一次劃分”，將關(guān)鍵字序列

52,49,80,36,14,58,61,97,23,75調(diào)整為:23,49,14,36,(52)58,61,97,80,75

在調(diào)整過程中，設(shè)立了兩個指針：low

和high，它們的初值分別為：s和t，

之后逐漸減小high，增加low，并保證

R[high].key≥52，和R[low].key≤52,否則進行記錄的“交換”。intQKPass(RecordTyper[],intleft,intright){ RecordTypex=r[left]; intlow,high; low=left;high=right; while(low<high) { while(low<high&&r[high].key>=x.key)high--; if(low<high){r[low]=r[high];low++;} while(low<high&&r[low].key<x.key)low++; if(low<high){r[high]=r[low];high--;} } r[low]=x;returnlow;}二、快速排序

首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進行快速排序voidQKSort(RecordTyper[],intlow,inthigh){ if(low<high) { pos=QKPass(r,low,high); QKSort(r,low,pos-1); QKSort(r,pos+1,high); }}結(jié)論:快速排序的時間復雜度為O(nlogn)9.4選擇類排序法

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

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

簡單選擇排序的算法描述如下：voidSelectSort(RecordTyper[],intlength)/*對記錄數(shù)組r做簡單選擇排序，length為數(shù)組的長度*/{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*/簡單選擇排序算法分析：

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

9.4.2樹型選擇排序

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

n/2

個較小者中，采用同樣的方法進行比較選出每兩個中的較小者，如此反復，直至選出最小關(guān)鍵字記錄為止。

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

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

log2n

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

log2n

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

算法分析：9.4.3堆排序

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

具體做法：

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

i/2

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

n/2

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

堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小根堆不是堆(小根堆)(大根堆)rir2i

r2i+1

若將該數(shù)列視作完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498例如:14{12,36,27,65,40,14,98,81,73,55,49}堆排序的過程主要需要解決兩個問題：(1)按堆定義建初堆（2）去掉最大元之后重建堆，得到次大元。

問題1:當堆頂元素改變時，如何重建堆?

首先將完全二叉樹根結(jié)點中的記錄移出，該記錄稱為待調(diào)整記錄。此時根結(jié)點相當于空結(jié)點。從空結(jié)點的左、右子中選出一個關(guān)鍵字較小的記錄，如果該記錄的關(guān)鍵字小于待調(diào)整記錄的關(guān)鍵字，則將該記錄上移至空結(jié)點中。此時，原來那個關(guān)鍵字較小的子結(jié)點相當于空結(jié)點。重復上述移動過程，直到空結(jié)點左、右子的關(guān)鍵字均不小于待調(diào)整記錄的關(guān)鍵字。此時，將待調(diào)整記錄放入空結(jié)點即可。上述調(diào)整方法相當于把待調(diào)整記錄逐步向下“篩”的過程，所以一般稱為“篩選”法。

所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。堆堆篩選98814973556412362740例如:是大根堆12但在98和12進行互換之后，它就不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較篩選算法為：voidsift（RecordTyper[],int

ｋ，intｍ）

/*假設(shè)ｒ[k..m]是以ｒ[k]為根的完全二叉樹，且分別以ｒ[2k]和ｒ[2k+1]為根的左、右子樹為大根堆，調(diào)整r[k]，使整個序列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]填入到恰當?shù)奈恢?/}/*sift*/問題2:如何由一個任意序列建初堆？

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

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

;i>=1;--i)/*自第個記錄開始進行篩選建堆*/sift(r，i，n)；}問題3:如何利用堆進行排序？

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

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

堆排序的算法為：voidHeapSort（RecordTyper[],intlength）

/*對r[1..n]進行堆排序，執(zhí)行本算法后，r中記錄按關(guān)鍵字由大到小有序排列*/{crt_heap（r,length）；n=length;for(i=n;i>=2;--i){b=r[1];/*將堆頂記錄和堆中的最后一個記錄互換*/r[1]=r[i]r[i]=b;sift(r，1，i-1)；/*進行調(diào)整，使r[1..i-1]變成堆*/}}/*HeapSort*/建堆是一個從下往上進行“篩選”的過程。40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355

現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。98494064361227堆排序算法分析：

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

log2n

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

2(

log2(n-1)

+

log2(n-2)

+…+

log22

<2n

log2n

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

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

9.5歸并排序在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]

歸并排序的過程基于下列基本思想進行：

將兩個或兩個以上的有序子序列“歸并”為一個有序序列。有序子序列R[m+1..n]歸并排序的示例為：(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-路歸并排序法的基本操作是將待排序列中相鄰的兩個有序子序列合并成一個有序序列。合并算法描述如下：voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper[])/*已知r1[low..mid]和r1[mid+1..high]分別按關(guān)鍵字有序排列，將它們合并成一個有序序列，存放在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-路歸并排序可以采用遞歸方法實現(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]中前后相鄰且長度為h的有序段進行兩兩歸并，得到前后相鄰、長度為2h的有序段，并存放在r[1…n]中，其

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

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

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

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

9.6分配類排序

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

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

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

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

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

具體實現(xiàn)時，一般采用鏈式基數(shù)排序。我們首先通過一個具體的例子來說明鏈式基數(shù)排序的基本過程。

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

(b)第一趟分配之后

(c)第一趟收集之后

(d)第二趟分配之后

(e)第二趟收集之后

(f)第三趟分配之后

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

鏈式基數(shù)排序示例

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

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

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

鏈式基數(shù)排序的有關(guān)算法描述如下：

voidDistribute(RecordType1r[],inti,PVector

head,PVector

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

tail[j]=p；p=r[p].next；}}/*Distribute*/voidCollect(RecordTyper[],PVector

head,PVector

tail)/*本算法從0到RADIX-1

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

while((j<RADIX-1)&&(head[j]==0))/*找下一個非空隊列*/++j；if(head[j]!=0)/*鏈接非空隊列*/{r[t].next=head[j]；t=tail[j]；}}r[t].next=0;/*t指向最后一個非空隊列中的最后一個結(jié)點*/}/*Collect*/voidRadixSort(RecordTyper[],intlength)/*length個記錄存放在數(shù)組r中，執(zhí)行本算法進行基數(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)鍵字開始，進行d趟分配和收集*/{Distribute(r，i，head，tail)；/*第i趟分配*/Collect(r，head，tail)/*第i趟收集*/}}/*RadixSort*/基數(shù)排序的算法分析：

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

9.6.3

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

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

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

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

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

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

+1。n=7時一個最好情況的初始排列實例為：[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：荷蘭國旗問題假設(shè)有一個僅由紅、白、藍三種顏色的條塊組成的序列，需要在O(n)時間內(nèi)將這些條塊按紅、白、藍的順序排好，即排成荷蘭國旗圖案。例如，給定彩色條塊序列為：﹛藍、白、紅、白、藍、紅、白、白、紅、藍﹜則要求排列結(jié)果為：﹛紅、紅、紅、白、白、白、白、藍、藍、藍﹜

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

方法一：采用簡單選擇排序思想

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

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

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

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

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

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

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

【算法思想】上述算法思想比較簡單，但使用了兩個幾乎完全一樣的循環(huán)，使得算法顯得過于冗長。下面利用快速排序中對序列進行劃分的思想，這樣用一個循環(huán)就可以了。具體方法是：設(shè)置3個整型變量r、w、b，其中r指向紅色條塊區(qū)的下一個單元，w指向白色條塊區(qū)的下一個單元，b指向藍色條塊區(qū)的前一個單元。開始時令r和w為0，b為n-1。w相當于快速排序中的low指針，b相當于快速排序中的high指針。最終L[0..r-1]存放紅色條塊區(qū)，L[r..w-1]存放白色條塊區(qū)，L[w..n-1]存放藍色條塊區(qū)。檢查L[w]的值，有下列三種情況：(1)如果L[w]=2，則它已經(jīng)在白色區(qū)末尾，w直接加1；（2）

(2)如果L[w]=3，在將它加到藍色區(qū)頭部，即L[w]與L[b]交換，且b減1；（3）(3)如果L[w]=1，此時先將白色區(qū)第一個元素（即紅色區(qū)的下一個單元）移到白色區(qū)末尾，再將它加到紅色區(qū)的下一個單元，即L[w]與L[r]交換，且r和w同時加1。重復這個過程，直到w>b為止。

【算法描述】voidSort(intL[],intn)/*條塊顏色依次存放在L[0..n-1]中，本算法利用快速排序思想，將整個序列按紅、白、藍進行排序。*/﹛intx;intr;/*r指向紅色條塊區(qū)的下一個單元（同時也是白色條塊區(qū)的第一個單元）*/intw;/*w指向白色條塊區(qū)的下一個單元（同時也相當于快速排序中的low指針）*/intb;/*b指向藍色條塊區(qū)的前一個單元（同時也相當于快速排序中的high指針）*/r=w=0;/*相當于low=0*/b=n-1;/*相當于high=n-1*/while(w<=b)﹛

x=L[w];if(x==1)/*L[w]是紅色條塊，并且在白色條塊區(qū)的下一個單元*/﹛L[w]=L[r];/*L[r]是第一個白色條塊，將其移到白色條塊區(qū)最后*/w++;/*w指向白色條塊區(qū)的下一個單元*/L[r]=x;/*將紅色條塊x放到紅色條塊區(qū)的下一個單元*/r++;/*r指向紅色條塊區(qū)的下一個單元*/

﹜elseif(x==2)/*L[w]是白色條塊，并且恰好在白色條塊區(qū)的下一個單元*/w++;/*w指向白色條塊區(qū)的下一個單元*