第7章-排序算法案例

1

第七章：排序算法

2排序的概念排序是計(jì)算機(jī)內(nèi)常常進(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,973假設(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}的操作稱(chēng)作排序。排序的概念4內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不須要訪(fǎng)問(wèn)外存便能完成，則稱(chēng)此類(lèi)排序問(wèn)題為內(nèi)部排序；反之，若參與排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不行能在內(nèi)存中完成，則稱(chēng)此類(lèi)排序問(wèn)題為外部排序。5待排記錄的數(shù)據(jù)類(lèi)型定義#defineMAXSIZE1000//待排依次表最大長(zhǎng)度typedefintKeyType;

//關(guān)鍵字類(lèi)型為整數(shù)類(lèi)型typedefstruct{KeyTypekey;

//關(guān)鍵字項(xiàng)

InfoTypeotherinfo;

//其它數(shù)據(jù)項(xiàng)}RcdType;

//記錄類(lèi)型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置intlength;//依次表長(zhǎng)度}SqList;//依次表類(lèi)型6有序序列R[1..i-1]R[i]無(wú)序序列R[i..n]一趟干脆插入排序的基本思想有序序列R[1..i]無(wú)序序列R[i+1..n]7實(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；8干脆插入排序9voidInsertionSort(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];//插入到正確位置10干脆插入排序時(shí)間分析最好的狀況（關(guān)鍵字在記錄序列中依次有序）：“比較”的次數(shù)：最壞的狀況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：11

因?yàn)镽[1..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。折半插入排?214364952805861239775ilowhighmmlowlowmhigh14364952586180

239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r13voidBiInsertionSort(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];//插入14low=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ū)15

希爾排序

基本思想：對(duì)待排記錄序列先作“宏觀(guān)”調(diào)整，再作“微觀(guān)”調(diào)整。所謂“宏觀(guān)”調(diào)整，指的是，“跳動(dòng)式”的插入排序。具體做法為：16將記錄序列分成若干子序列，分別對(duì)每個(gè)子序列進(jìn)行插入排序。其中，d稱(chēng)為增量，它的值在排序過(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]}

希爾排序17例如：162512304711233691831

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

12

9

181625

36

30

4731

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

121123

162531

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

91112161823253031364718voidShellInsert(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}//ShellInsert19voidShellSort(SqList&L,intdlta[],intt){//增量為dlta[]的希爾排序

for(k=0;k<t;++t)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort20起泡排序假設(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的位置上21起泡排序22voidBubbleSort(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;23最好的狀況（關(guān)鍵字在記錄序列中依次有序）：只需進(jìn)行一趟起泡“比較”的次數(shù)：最壞的狀況（關(guān)鍵字在記錄序列中逆序有序）：需進(jìn)行n-1趟起泡“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：n-1冒泡排序時(shí)間分析24一趟快速排序

目標(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)。25stlowhigh設(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]52lowhighhighhighlow26intPartition(RedType&R[],intlow,inthigh)

{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[low]←→R[high];

}

returnlow;//返回樞軸所在位置}//Partition27intPartition(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;28快速排序

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

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ì)高子序列遞歸排序30快速排序的時(shí)間分析

假設(shè)一次劃分所得樞軸位置i=k，則對(duì)n個(gè)記錄進(jìn)行快排所需時(shí)間：

其中Tpass(n)為對(duì)n個(gè)記錄進(jìn)行一次劃分所需時(shí)間。若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則k取1至n中隨意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)31設(shè)Tavg(1)≤b則可得結(jié)果：結(jié)論:快速排序的時(shí)間困難度為O(nlogn)由此可得快速排序所需時(shí)間的平均值為：32若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間困難度為O(n2)?？焖倥判虻臅r(shí)間分析33簡(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]34簡(jiǎn)潔選擇排序35voidSelectSort(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è)記錄交換36簡(jiǎn)潔選擇排序時(shí)間性能分析對(duì)n個(gè)記錄進(jìn)行簡(jiǎn)潔選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)總計(jì)為：

移動(dòng)記錄的次數(shù)，最小值為0,最大值為3(n-1)。37堆排序堆是滿(mǎn)足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是最小堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(最小堆)(最大堆)38

堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法。例如：建最大堆{98,81,49,73,36,27,40,55,64,12}{12,81,49,73,36,27,40,55,64,98}交換98和12重新調(diào)整為大頂堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}經(jīng)過(guò)篩選39voidHeapSort(HeapType&H){//對(duì)依次表H進(jìn)行堆排序}//HeapSortfor(i=H.length/2;i>0;--i)

HeapAdjust(H.r,i,H.length);

//建大頂堆for(i=H.length;i>1;--i){H.r[1]←→H.r[i];//將堆頂記錄和當(dāng)前未經(jīng)排序子序列//H.r[1..i]中最終一個(gè)記錄相互交換HeapAdjust(H.r,1,i-1);//對(duì)H.r[1]進(jìn)行篩選}4098814973556412362740例如:是最大堆12但在98和12進(jìn)行互換之后，它就不是堆了，因此，須要對(duì)它進(jìn)行“篩選”。98128173641298比較比較41voidHeapAdjust(RcdType&R[],ints,intm){//已知R[s..m]中記錄的關(guān)鍵字除R[s]之外均//滿(mǎn)足堆的特征，本函數(shù)自上而下調(diào)整R[s]的//關(guān)鍵字，使R[s..m]也成為一個(gè)大頂堆}//HeapAdjustrc=R[s];//暫存R[s]for

(j=2*s;j<=m;j*=2)

{//j初值指向左孩子自上而下的篩選過(guò)程;}R[s]=rc;//將調(diào)整前的堆頂記錄插入到s位置42if(rc.key>=R[j].key)break;//再作“根”和“子樹(shù)根”之間的比較，//若“>=”成立，則說(shuō)明已找到rc的插//入位置s，不須要接著往下調(diào)整R[s]=R[j];s=j;//否則記錄上移，尚需接著往下調(diào)整if

(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子樹(shù)根”之間先進(jìn)行相互比較

//令j指示關(guān)鍵字較大記錄的位置43建堆是一個(gè)從下往上進(jìn)行“篩選”的過(guò)程40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355現(xiàn)在，左/右子樹(shù)都已經(jīng)調(diào)整為堆，最終只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。9849406436122744堆排序的時(shí)間困難度分析1.對(duì)深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3.調(diào)整“堆頂”n-1

次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò)

2(log2(n-1)+log2(n-2)+

…+log22)<2n(log2n)因此，堆排序的時(shí)間困難度為O(nlogn)。2.對(duì)

n

個(gè)關(guān)鍵字，建成深度為h(=log2n+1)的堆，

所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多4n；45通常接受的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]歸并排序46voidMerge(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中記錄由小到大地并入TRif(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}

……

47if(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ù)制到TR48歸并排序的算法假如記錄無(wú)序序列R[s..t]的兩部分R[s..(s+t)/2]和R[(s+t)/2+1..t]分別按關(guān)鍵字有序，則利用上述歸并算法很簡(jiǎn)潔將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。由此，應(yīng)當(dāng)先分別對(duì)這兩部分進(jìn)行2-路歸并排序。49例如：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]50void

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

{

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

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

else

{}}//Msort

……51m=(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]52voidMergeSort(SqList&L){//對(duì)依次表L作2-路歸并排序MSort(L.r,L.r,1,L.length);}//MergeSort簡(jiǎn)潔看出，對(duì)n個(gè)記錄進(jìn)行歸并排序的時(shí)間困難度為Ο(nlogn)。即：每一趟歸并的時(shí)間困難度為O(n)，總共需進(jìn)行l(wèi)og2n趟。53非遞歸的歸并排序VoidMergeSort(SqList&list){len=1;while(len<list.length){MergePass(list,tempList,len);len*=2;MergePass(tempList,list,len);len*=2;}}VoidMergePass(SqList&initList,SqList&mergedList,intlen){inti=1;while(i+2*len-1<=list.CurrentSize-1){merge(initlist,mergedList,i,i+len-1,i+2*len-1);i+=2*len;}if(i+len<=initList.length-1)merge(initlist,mergedList,i,i+len-1,initList.length-1);elsefor(intj=i;j<=initList.length-1;j++)mergedList.r[j]=initLIst.r[j];}}54

基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法?；鶖?shù)排序55多關(guān)鍵字的排序

n

個(gè)記錄的序列{R1,R2,…，Rn}對(duì)關(guān)鍵字(Ki0,Ki1,…,Kid-1)有序是指：其中:K0被稱(chēng)為“最主”位關(guān)鍵字Kd-1被稱(chēng)為“最次”位關(guān)鍵字對(duì)于序列中隨意兩個(gè)記錄Ri和Rj(1≤i<j≤n)都滿(mǎn)足下列(詞典)有序關(guān)系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)56先對(duì)K0進(jìn)行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對(duì)K1進(jìn)行排序，...…，依次類(lèi)推，直至最終對(duì)最次位關(guān)鍵字排序完成為止。最高位優(yōu)先MSD法57先對(duì)Kd-1進(jìn)行排序，然后對(duì)Kd-2進(jìn)行排序，依次類(lèi)推，直至對(duì)最主位關(guān)鍵字K0排序完成為止。最低位優(yōu)先LSD法58鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時(shí)，可以接受“安排-收集”的方法，其好處是不須要進(jìn)行關(guān)鍵字間的比較。對(duì)于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以接受這種“安排-收集”的方法進(jìn)行排序，稱(chēng)作基數(shù)排序法。59鏈?zhǔn)交鶖?shù)排序601、待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表；2、“安排”時(shí)，按當(dāng)前“關(guān)鍵字位”所取值，將記錄安排到不同的“鏈隊(duì)列”中，每個(gè)隊(duì)列中記錄的“關(guān)鍵字位”相同；3、“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表;4、對(duì)每個(gè)關(guān)鍵字位均重復(fù)2)和3)兩步。鏈?zhǔn)交鶖?shù)排序61基數(shù)排序的時(shí)間困難度為O(d(n+rd))其中：安排為O(n)收集為O(rd)(rd為“基”)d為“安排-收集”的趟數(shù)堆排序的時(shí)間困難度分析62各種排序方法時(shí)間性能1.平均的時(shí)間性能基數(shù)排序時(shí)間困難度為O(nlogn)：快速排序、堆排序和歸并排序時(shí)間困難度為O(n2)：干脆插入排序、起泡排序和簡(jiǎn)潔選擇排序時(shí)間困難度為O(n):632.當(dāng)待排記錄序列按關(guān)鍵字依次有序時(shí)3.簡(jiǎn)潔選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而變更。干脆插入排序和起泡排序能達(dá)到O(n)的時(shí)間困難度，快速排序的時(shí)間性能蛻化為O(n2)。各種排序方法時(shí)間性能64指的是排序過(guò)程中所需的協(xié)助空間大小1.全部的簡(jiǎn)潔排序方法(包括：干脆插入、起泡和簡(jiǎn)潔選擇)和堆排序的空間困難度為O(1)；2.快速排序?yàn)镺(logn)，為遞歸程序執(zhí)行過(guò)程中，棧所需的協(xié)助空間；各種排序方法空間性能3.歸并排序所需協(xié)助空間最多，其空間困難度為O(n);4.鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間困難度為O(rd)。65排序方法的穩(wěn)定性能1.穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過(guò)排序之后，沒(méi)有變更。2.當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必需接受穩(wěn)定的排序方法。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}

3.快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。66例如：

排序前

(56,34,47,23,66,18,82,

47)若排序后得到結(jié)果

(18,23,34,47,47,56,66,82)則稱(chēng)該排序方法是穩(wěn)定的;若排序后得到結(jié)果

(18,23,34,

47,47,56,66,82)則稱(chēng)該排序方法是不穩(wěn)定的。67排序方法的時(shí)間困難度的下限本章探討的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進(jìn)行排序的排序方法?？梢宰C明，這類(lèi)排序法可能達(dá)到的最快的時(shí)間困難度為O(nlogn)。(基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個(gè)限制。)68例如:對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹(shù)如下：K1<K3K1<K2K1<K3K2<K3K2<K3K2<K1<K3K1<K2<K3K3<K2<K1K2<K3<K1K3<K1<K2K1<K3<K2１．樹(shù)上的每一次“比較”都是必要的;２．樹(shù)上的葉子結(jié)點(diǎn)包含全部可能狀況。69一般狀況下，對(duì)n個(gè)關(guān)鍵字進(jìn)行排序，可能得到的結(jié)果有n!種，由于含n!個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的深度不小于log2(n