第9章-排序案例

第九章排序10.1概述10.2插入排序10.3快速排序10.4堆排序10.5歸并排序10.6各種排序方法的綜合比較10.1概述一、排序的定義二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,97

一般情況下，假設(shè)含n個(gè)記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系：

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為

{Rp1,Rp2,

…，Rpn}的操作稱作排序。二、內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題為內(nèi)部排序；

反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類排序問(wèn)題為外部排序。三、內(nèi)部排序的方法

內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。經(jīng)過(guò)一趟排序有序序列區(qū)無(wú)序序列區(qū)有序序列區(qū)無(wú)序序列區(qū)

基于不同的“擴(kuò)大”

有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分下列幾種類型：插入類交換類選擇類

歸并類待排記錄的數(shù)據(jù)類型定義如下:#defineMAXSIZE1000

//待排順序表最大長(zhǎng)度typedefintKeyType;

//關(guān)鍵字類型為整數(shù)類型typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RcdType;//記錄類型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置

intlength;//順序表長(zhǎng)度}SqList;//順序表類型

10.2插入排序有序序列R[1..i-1]R[i]無(wú)序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]無(wú)序序列R[i+1..n]實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．將R[i]插入(復(fù)制)到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．在R[1..i-1]中查找R[i]的插入位置，

R[1..j].keyR[i].key<R[j+1..i-1].key；直接插入排序（基于順序查找）希爾排序（基于逐趟縮小增量）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序（基于折半查找）一、直接插入排序

利用“順序查找”實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”算法的實(shí)現(xiàn)要點(diǎn)：

對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置令i=2，3，…,n,實(shí)現(xiàn)整個(gè)序列的排序。for(i=2;i<=n;++i)

if(R[i].key<R[i-1].key)

{在

R[1..i-1]中查找R[i]的插入位置;

插入R[i];

}初始關(guān)鍵字序列：【13】，6，3，31，9，27，5，11第一次排序：【6,13】,3,31,9,27,5,11第二次排序：【3,6,13】,31,9,27,5,11第三次排序：【3,6,13，31】,9,27,5,11第四次排序：

【3,6,9,13，31】,27,5,11第五次排序：【3,6,9,13，27,31】,5,11第六次排序：

【3,5,6,9,13，27,31】,11第七次排序：【3,5,6,9,11，13，27,31】

例：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請(qǐng)寫出直接插入排序的中間過(guò)程序列。注：方括號(hào)【】中為已排序記錄的關(guān)鍵字，下劃?rùn)M線的關(guān)鍵字表示它對(duì)應(yīng)的記錄后移一個(gè)位置。voidInsertionSort(SqList&L){//對(duì)順序表L作直接插入排序。

for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){

}}//InsertSortL.r[0]=L.r[i];//復(fù)制為監(jiān)視哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置內(nèi)部排序的時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)：（2）“移動(dòng)”記錄。（1）“比較”序列中兩個(gè)關(guān)鍵字的大?。粚?duì)于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：時(shí)間效率：因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下也要考慮移動(dòng)元素的次數(shù)。故時(shí)間復(fù)雜度為O(n2)空間效率：僅占用1個(gè)緩沖單元——O（1）算法的穩(wěn)定性：穩(wěn)定

因?yàn)镽[1..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉６?、折半插入排序voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//將L.r[i]暫存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移L.r[high+1]=L.r[0];//插入low=1;high=i-1;while

(low<=high)

{}m=(low+high)/2;//折半if

(L.r[0].key<L.r[m].key)

high=m-1;//插入點(diǎn)在低半?yún)^(qū)else

low=m+1;//插入點(diǎn)在高半?yún)^(qū)14364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r

三、希爾排序（又稱縮小增量排序）

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

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

稱為增量，它的值在排序過(guò)程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個(gè)記錄分成d個(gè)子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}例如：162512304711233691831

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

12

9

181625

36

30

4731

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

121123

162531

304736第三趟希爾排序，設(shè)增量d=1

911121618232530313647voidShellInsert(SqList&L,intdk){

for(i=dk+1;i<=n;++i)

if(L.r[i].key<L.r[i-dk].key){

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

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

j-=dk)L.r[j+dk]=L.r[j];//記錄后移，查找插入位置

L.r[j+dk]=L.r[0];//插入

}//if}//ShellInsertvoidShellSort(SqList&L,intdlta[],intt){//增量為dlta[]的希爾排序

for(k=0;k<t;++t)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort開(kāi)始時(shí)d的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，d值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)記錄已基本有序，所以排序速度仍然很快。時(shí)間效率：O(n(log2n)2)空間效率：O（1）—因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：不穩(wěn)定算法分析：練習(xí)：1.

欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母升序重排，則初始步長(zhǎng)為4的希爾排序一趟的結(jié)果是？答：原始序列：

Q,H,C,Y,P,A,M,S,R,D,F,X

shell一趟后：P,Q,R,A,D,H,C,F,M,S,X,Y2.

以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（取d=5,3,1）算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。

解：原始序列:

256，301，751，129，937，863，742，694，076，438第1趟d=5第2趟d=3第3趟d=1256，301，694，076，438，863，742，751，129，937076，301，129，256，438，694，742，751，863，937076，129，256，301，438，694，742，751，863，937希爾排序10.3快速排序一、起泡排序二、一趟快速排序三、快速排序四、快速排序的時(shí)間分析一、起泡排序

假設(shè)在排序過(guò)程中，記錄序列R[1..n]的狀態(tài)為：第i趟起泡排序無(wú)序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無(wú)序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到

n-i+1的位置上例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)按從小到大的順序，寫出冒泡排序的具體實(shí)現(xiàn)過(guò)程。初態(tài)：第1趟第2趟第3趟第4趟第5趟21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49voidBubbleSort(ElemR[],intn){

while(i>1){

}

//while}//BubbleSorti=n;i=lastExchangeIndex;//本趟進(jìn)行過(guò)交換的

//最后一個(gè)記錄的位置if(R[j+1].key<R[j].key)

{

Swap(R[j],R[j+1]);

lastExchangeIndex=j;//記下進(jìn)行交換的記錄位置

}

//iffor(j=1;j<i;j++)lastExchangeIndex=1;注意:2.一般情況下，每經(jīng)過(guò)一趟“起泡”，“i減一”，但并不是每趟都如此。例如:2553157989i=7i=6for(j=1;j<i;j++)if(R[j+1].key<R[j].key)…13i=21.起泡排序的結(jié)束條件為，

最后一趟沒(méi)有進(jìn)行“交換記錄”。時(shí)間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進(jìn)行一趟起泡“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進(jìn)行n-1趟起泡“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：n-1二、一趟快速排序（一次劃分）

目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無(wú)序序列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)鍵字進(jìn)行比較，要求R[high].key≥

樞軸的關(guān)鍵字

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

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

可見(jiàn)，經(jīng)過(guò)“一次劃分”，將關(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)整過(guò)程中，設(shè)立了兩個(gè)指針：low

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

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

R[high].key≥52，和R[low].key≤52,否則進(jìn)行記錄的“交換”。intPartition(RedTypeR[],intlow,inthigh)

{}//Partition

R[0]=R[low];pivotkey=R[low].key;//樞軸while(low<high){}while(low<high&&

R[high].key>=pivotkey)--high;//從右向左搜索R[low]=R[high];while(low<high&&

R[low].key<=pivotkey)++low;//從左向右搜索R[high]=R[low];R[low]=R[0];

returnlow;三、快速排序

首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。無(wú)序的記錄序列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸一次劃分分別進(jìn)行快速排序void

QSort(RedType&R[],ints,intt)

{

//對(duì)記錄序列R[s..t]進(jìn)行快速排序

if(s<t-1){

//長(zhǎng)度大于1

}}//QSortpivotloc=Partition(R,s,t);

//對(duì)R[s..t]進(jìn)行一次劃分QSort(R,s,pivotloc-1);

//對(duì)低子序列遞歸排序，pivotloc是樞軸位置QSort(R,pivotloc+1,t);

//對(duì)高子序列遞歸排序voidQuickSort(SqList&L){

//對(duì)順序表進(jìn)行快速排序

QSort(L.r,1,L.length);}//QuickSort

第一次調(diào)用函數(shù)Qsort時(shí)，待排序記錄序列的上、下界分別為1和L.length。四、快速排序的時(shí)間分析時(shí)間效率：O(nlog2n)—因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O（log2n）—因?yàn)檫f歸要用棧(存每層low，high和pivot)穩(wěn)定性：

不穩(wěn)定—因?yàn)橛刑S式交換。

若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判颍鋾r(shí)間復(fù)雜度為O(n2)。

為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“予處理”，即：

先對(duì)R(s).key,R(t).key和R[(s+t)/2].key，進(jìn)行相互比較，然后取關(guān)鍵字為

“三者之中”的記錄為樞軸記錄。10.4堆排序簡(jiǎn)單選擇排序堆排序一、簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無(wú)序序列R[i..n]

第i趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R[1..i]無(wú)序序列

R[i+1..n]例：關(guān)鍵字序列T=（21，25，49，25*，16，08），請(qǐng)給出簡(jiǎn)單選擇排序的具體實(shí)現(xiàn)過(guò)程。原始序列：

21，25，49，25*，16，08直接選擇排序第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,

49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49簡(jiǎn)單選擇排序的算法描述如下：voidSelectSort(ElemR[],intn){

//對(duì)記錄序列R[1..n]作簡(jiǎn)單選擇排序。

for(i=1;i<n;++i){

//選擇第i小的記錄，并交換到位

}}//SelectSortj=SelectMinKey(R,i);

//在R[i..n]中選擇關(guān)鍵字最小的記錄if(i!=j)R[i]←→R[j];

//與第i個(gè)記錄交換時(shí)間性能分析時(shí)間效率：

O(n2)——雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多?？臻g效率：O（1）——沒(méi)有附加單元（僅用到1個(gè)temp)算法的穩(wěn)定性：不穩(wěn)定10.5歸并排序

歸并排序的過(guò)程基于下列基本思想進(jìn)行：

將兩個(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]這個(gè)操作對(duì)順序表而言，是輕而易舉的。voidMerge(RcdTypeSR[],RcdType&TR[],

inti,intm,intn){

//將有序的記錄序列SR[i..m]和SR[m+1..n]//歸并為有序的記錄序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k)

{

//將SR中記錄由小到大地并入TR

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];

}

……

if(i<=m)TR[k..n]=SR[i..m];//將剩余的SR[i..m]復(fù)制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復(fù)制到TR歸并排序的算法如果記錄無(wú)序序列R[s..t]的兩部分

R[s..(s+t)/2]和R[(s+t)/2+1..t]分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。

由此，應(yīng)該先分別對(duì)這兩部分進(jìn)行2-路歸并排序。例如：52,23,80,36,68,14(s=1,t=6)[52,23,80]

[36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]void

Msort(RcdTypeSR[],RcdType&TR1[],ints,intt)

{

//將SR[s..t]歸并排序?yàn)門R1[s..t]

if(s==t)TR1[s]=SR[s];

else

{}}//Msort……m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1..t]Msort(SR,TR2,s,m);//遞歸地將SR[s..m]歸并為有序的TR2[s..m]Msort(SR,TR2,m+1,t);//遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]voidMergeSort(SqList&L){//對(duì)順序表L作2-路歸并排序

MSort(L.r,L.r,1,L.length);}//MergeSort二路歸并排序算法分析：

時(shí)間效率：O(nlog2n)因?yàn)樵谶f歸的歸并排序算法中，函數(shù)Merge()做一趟兩路歸并排序，需要調(diào)用merge()函數(shù)n/(2len)

O(n/len)次，而每次merge()要執(zhí)行比較O(len)次，另外整個(gè)歸并過(guò)程有l(wèi)og2n“層”，所以算法總的時(shí)間復(fù)雜度為O(nlog2n)?？臻g效率：O(n)因?yàn)樾枰粋€(gè)與原始序列同樣大小的輔助序列。這正是此算法的缺點(diǎn)。穩(wěn)定性：穩(wěn)定10.6各種排序方法的綜合比較一、時(shí)間性能1.平均的時(shí)間性能基數(shù)排序時(shí)間復(fù)雜度為O(nlog2n)：快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為O(n2)：直接插入排序、起泡排序和簡(jiǎn)單選擇排序時(shí)間復(fù)雜度為O(n):2.當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3.

簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。

直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度，

快速排序的時(shí)間性能蛻化為O(n2)

。二、空間性能指的是排序過(guò)程中所需的輔助空間大小1.

所有的簡(jiǎn)單排序方法(包括：直接插入、起泡和簡(jiǎn)單選擇)和堆排序的空間復(fù)雜度為O(1)；2.

快速排序?yàn)镺(log2n)，為遞歸程序執(zhí)行過(guò)程中，棧所需的輔助空間；3.

歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);4.鏈