西電初試專業(yè)課講義-數(shù)據(jù)結(jié)構(gòu)ch10sorting

第十章

內(nèi)部排序10.1排序的基本概念排序(sorting)將一個(gè)數(shù)據(jù)元素的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。假設(shè)n個(gè)元素的序列{R1,R2,...,Rn}，相應(yīng)的關(guān)鍵字序列為{k1,k2,...,kn}，確定1,2,...,n的一種排列p1,p2,...,pn

，使相應(yīng)的關(guān)鍵字滿足非遞減(或非遞增)關(guān)系kp1,kp2,...,kpn，從而得到一個(gè)按關(guān)鍵字有序的序列。這樣的一個(gè)操作過程就是排序。穩(wěn)定的排序方法若ki＝kj，且在排序前的序列中Ri領(lǐng)先于Rj，排序后Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中Rj仍領(lǐng)先于Ri，則稱所用的排序方法是不穩(wěn)定的。內(nèi)部排序和外部排序待排序的記錄存放在計(jì)算機(jī)的內(nèi)存中所進(jìn)行的排序操作稱為內(nèi)部排序。待排序的記錄數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中需要訪問外存的排序過程稱為外部排序。10.1排序的基本概念(續(xù))正序與逆序若有序表是按排序碼升序排列的，則稱為升序表或正序表，否則稱為降序表或逆序表。不失普遍性，我們一般只討論正序表。排序方法度量排序過程主要是比較記錄的關(guān)鍵字和移動(dòng)記錄。因此排序的時(shí)間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動(dòng)次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進(jìn)行的比較和移動(dòng)次數(shù)越少，則認(rèn)為該方法的時(shí)間復(fù)雜性就越好。針對(duì)一種排序方法，不僅要分析它的時(shí)間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。10.1排序的基本概念(續(xù))內(nèi)部排序外部排序

插入排序（直插排序、二分插入排序、希爾排序）

交換排序（冒泡排序、快速排序）

選擇排序（直選排序、樹型排序、堆排序）

歸并排序（二路歸并排序、多路歸并排序）

分配排序（多關(guān)鍵字排序、基數(shù)排序）

多路平衡歸并排序

置換－選擇排序

最佳歸并樹排序?qū)o序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。通過“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長度。10.2插入排序1.直接插入排序直接插入排序(StraightInsertionSorting)的基本思想是：n個(gè)待排序的元素由一個(gè)有序表和一個(gè)無序表組成，開始時(shí)有序表中只包含一個(gè)元素。排序過程中，每次從無序表中取出第一個(gè)元素，將其插入到有序表中的適當(dāng)位置，使有序表的長度不斷加長，完成排序過程。有序序列R[1..i-1]R[i]無序序列R[i..n]有序序列R[1..i]無序序列R[i+1..n]10.2直接插入排序過程示例初始關(guān)鍵字序列3412492831525149*123456780監(jiān)視哨i=21234492831525149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=61228313449525149*52i=71228313449515249*51i=8122831344949*515249*10.2直接插入排序算法數(shù)據(jù)結(jié)構(gòu)定義#defineMAXSIZE20typedefintKeytype;//定義關(guān)鍵字類型為整型typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)

InfoTypeotherinfo;//其他數(shù)據(jù)項(xiàng)}RedType;//記錄類型typedefstruct{RedTyper[MAXSIZE+1];//r[0]閑置或用作哨兵

intlength;//順序表長度}SqList;//順序表類型10.2直接插入排序算法以順序表作為存儲(chǔ)結(jié)構(gòu)的直接插入排序算法voidInsertSort(SqList&L){

for(i=2;i<=L.ength;i++)if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.[i-1];for(j=i-2;L.r[0].key<L.r[j].key];j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//if}//InsertSort分析直接插入排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)for(i=2;i<=L.length;i++)

if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.[i-1];for(j=i-2;L.r[0].key<L.r[j].key];j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//ifif(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key<L.r[j].key;j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//if最好情況下(正序)元素的比較次數(shù)為:n-1元素的移動(dòng)次數(shù)為:0最壞情況下(逆序)元素的比較次數(shù):(n+2)(n-1)/2元素的移動(dòng)次數(shù)為：

(n+4)(n-1)/210.2直接插入排序算法以順序表作為存儲(chǔ)結(jié)構(gòu)的直接插入排序算法時(shí)間復(fù)雜度：O(n2)在最好情況下(正序)，元素的移動(dòng)次數(shù)為0，比較次數(shù)為n–1；在最壞情況下(逆序)，元素的移動(dòng)次數(shù)為(n+4)(n-1)/2，比較次數(shù)為(n+2)(n-1)/2空間復(fù)雜度：O(1)只需要

1個(gè)輔助單元穩(wěn)定的排序方法適用情況元素?cái)?shù)目少，或者元素的初始序列基本有序10.2其他插入排序2.其他插入排序在尋找插入位置時(shí)采用二分查找，則稱為折半插入排序;2-路插入排序在此基礎(chǔ)上增加了輔助空間、減少了記錄的移動(dòng);表插入排序就是通過鏈接指針，按關(guān)鍵碼的大小，實(shí)現(xiàn)從小到大的鏈接過程，不移動(dòng)元素，用靜態(tài)鏈表實(shí)現(xiàn)。voidInsertSort(SqList&L)/*對(duì)順序表L作折半插入排序*/{ for(i=2；i<=L.length;i++){L.r[0]=L.r[i];/*保存待插入元素*/

low=1；high=i-1；/*設(shè)置初始區(qū)間*/while(low<=high)/*確定插入位置*/{mid=(low+high)/2；

if(L.r[0].key>L.r[mid].key)low=mid+1；/*插入位置在高半?yún)^(qū)中*/elsehigh=mid-1；/*插入位置在低半?yún)^(qū)中*/}/*while*/for(j=i-1;j>=high+1;j--)/*high+1為插入位置*/L.r[j+1]=L.r[j];/*后移元素，留出插入空位*/L.r[high+1]=L.r[0];/*將元素插入*/}/*for*/}/*InsertSort*/10.2希爾排序3.希爾排序(Shell’sSort)也稱為縮小增量排序，其改進(jìn)原理主要基于以下兩點(diǎn)元素基本有序時(shí)，直接插入排序的時(shí)間復(fù)雜度接近于O(n)元素?cái)?shù)目n較少時(shí)，直接插入排序的效率較高希爾排序的算法思想先將整個(gè)待排序元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的），分別進(jìn)行直接插入排序，待整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。10.2希爾排序過程示例初始關(guān)鍵字序列：4938659776132749*123456785504910增量d＝5132749*5504493865123456789776910第一趟排序結(jié)果：增量d＝3第二趟排序結(jié)果：130449*3827495565123456789776910增量d＝1第三趟排序結(jié)果：0413273849*495565123456787697910132749*5504493865977610.2希爾排序算法voidShellInsert(SqList&L,intdk){//對(duì)順序表L作一趟希爾排序

for(i=2;i<=L.ength;i++)if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.[i-1];for(j=i-2;L.r[0].key<L.r[j].key];j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//if}//ShellInsertSortfor(i=dk+1i<=L.ength;i++)

if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.[i-1];for(j=i-2;L.r[0].key<L.r[j].key];j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//ifif(L.r[i].key<L.r[i-dk].key){//需將L.r[i]插入有序增量子表

L.r[0]=L.r[i];//L.r[i]暫存入L.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];//尋找插入位置時(shí)記錄后移

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

}//if10.2希爾排序算法(續(xù))及分析voidShellInsert(SqList&L,intdk){//對(duì)順序表L作一趟希爾排序L......}//ShellInsertSortvoidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]進(jìn)行希爾排序

for(k=0;k<t;k++)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的希爾排序}//ShellInsertSort希爾排序的分析是一個(gè)復(fù)雜問題，增量序列的設(shè)置是關(guān)鍵，尚沒有正式的依據(jù)說明如何設(shè)置最佳的增量序列，大量的實(shí)驗(yàn)表明希爾排序所需的比較和移動(dòng)次數(shù)可達(dá)到n1.3希爾排序的空間復(fù)雜度為O(1)，是不穩(wěn)定的排序方法10.3交換排序1.起泡排序起泡排序(BubbleSorting)的基本思想是：將相鄰位置的關(guān)鍵字進(jìn)行比較，若為逆序則交換之。無序序列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的位置上第i趟起泡排序若在一趟排序過程中沒有進(jìn)行過交換記錄的操作，則整個(gè)排序過程終止。10.3起泡排序過程示例初始關(guān)鍵字序列：4938659776132749*1234567838496576132749*97第一趟排序后：384965132749*7697第二趟排序后：3849132749*657697第三趟排序后：3813274949*657697第四趟排序后：1327384949*657697第五趟排序后：1327384949*657697第六趟排序后：10.3起泡排序算法以順序表作為存儲(chǔ)結(jié)構(gòu)的起泡排序算法voidBubbleSort(SqList&L){

for(i=2;i<=L.ength;i++)if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.[i-1];for(j=i-2;L.r[0].key<L.r[j].key];j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//if}//BubbleSort分析起泡排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)for(i=1,change=TRUE;i<L.length&&change;++i){

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

}//for}//ifchange=FALSE;for(j=1;j<L.length-i+1;++j)if(L.r[j].key>L.r[j+1].key){L.r[0]=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=L.r[0];change=TRUE;}//if最好情況下，元素的比較次數(shù)為:n-1最壞情況下，比較次數(shù)為:n(n-1)/2最好情況下，元素的移動(dòng)次數(shù)為:0最壞情況下，交換次數(shù)為：n(n-1)/210.3起泡排序算法以順序表作為存儲(chǔ)結(jié)構(gòu)的起泡排序算法時(shí)間復(fù)雜度：O(n2)在最好情況下(正序)，元素的交換次數(shù)為0，比較次數(shù)為n–1；在最壞情況下(逆序)，元素的交換次數(shù)為n(n-1)/2，比較次數(shù)為(n+2)(n-1)/2空間復(fù)雜度：O(1)只需要

1個(gè)輔助單元進(jìn)行交換穩(wěn)定的排序方法適用情況元素?cái)?shù)目少，或者元素的初始序列基本有序10.3交換排序(續(xù))2.快速排序快速排序(QuickSorting)是迄今為止所有內(nèi)排序算法中速度最快的一種。其基本思想是：取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的關(guān)鍵字均小于或等于基準(zhǔn)元素的關(guān)鍵字，右子序列的關(guān)鍵字則大于基準(zhǔn)元素的關(guān)鍵字，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進(jìn)行快速排序386597132749*551234567849049pivotij快速排序中的一趟劃分快速排序中的一趟劃分(續(xù))386597132749*55123456784904949ijL.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減10449L.r[j]與L.r[i]交換，i加1快速排序中的一趟劃分(續(xù))386597132749*55123456780449949pivotijL.r[i]與pivot比較，L.r[i]大則與L.r[j]交換；否則i增1快速排序中的一趟劃分(續(xù))L.r[i]與pivot比較，L.r[i]大則與L.r[j]交換；否則i增1386597132749*55123456780449949pivotij4965L.r[i]與L.r[j]交換，j減1快速排序中的一趟劃分(續(xù))384997132749*55123456780465949ijL.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1快速排序中的一趟劃分(續(xù))384997132749*55123456780465949pivotijL.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1快速排序中的一趟劃分(續(xù))L.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1384997132749*55123456780465949pivotij2749L.r[j]小則與L.r[i]交換，i加1快速排序中的一趟劃分(續(xù))pivot382797134949*55123456780465949pivotijL.r[i]與pivot比較，L.r[i]大則與L.r[j]交換；否則i增1L.r[i]大則與L.r[j]交換，j減14997快速排序中的一趟劃分(續(xù))pivotL.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1382749139749*55123456780465949pivotijL.r[j]小則與L.r[i]交換，i加11349快速排序中的一趟劃分(續(xù))382713499749*55123456780465949pivotij當(dāng)i與j相等時(shí)，樞軸元素確定了位置i，結(jié)束本次劃分

快速排序是對(duì)冒泡排序的一種改進(jìn)方法，算法中元素的比較和交換是從兩端向中間進(jìn)行的，排序碼較大的元素一次就能夠交換到后面的單元，排序碼較小的記錄一次就能夠交換到前面的單元，記錄每次移動(dòng)的距離較遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。386597132749*551234567849049pivot快速排序中的一趟劃分算法382713499749*551234567804659一次劃分intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;i=low;j=high;while(i<j){

while(i<j&&L.r[j].key>=pivotkey)j--;/*從后往前尋找比樞軸元素小者*/L.r[i]←→L.r[j];/*比樞軸元素小者交換到前半?yún)^(qū)間*/

while(i<j&&L.r[i].key<=pivotkey)i++;/*從前往后尋找比樞軸元素大者*/L.r[j]←→L.r[i];/*比樞軸元素大者交換到后半?yún)^(qū)間*/}returni;/*返回樞軸元素的位置*/}//Partition將交換改為元素的移動(dòng)劃分算法改進(jìn)386597132749*55123456784904949ij0449386597132749*55123456784904949ij04386597132749551234567849049pivotij快速排序中的一趟劃分快速排序中的一趟劃分386597132749551234567804949pivotija[j]與pivot比較，a[j]小則a[j]→a[i]快速排序中的一趟劃分386597132749551234567804949pivotij快速排序中的一趟劃分386597132749551234567804949pivotija[i]與pivot比較，a[i]大則a[i]→a[j]；否則i增1快速排序中的一趟劃分386597132749551234567804949pivotija[i]與pivot比較，a[i]大則a[i]→a[j]；否則i增1快速排序中的一趟劃分389713274955123456780465949pivotij快速排序中的一趟劃分389713274955123456780465949pivotija[j]與pivot比較，a[j]小則a[j]→a[i];

否則，利用j向前掃描快速排序中的一趟劃分389713274955123456780465949pivotija[j]與pivot比較，a[j]小則a[j]→a[i];

否則，利用j向前掃描快速排序中的一趟劃分389713274955123456780465949pivotija[j]與pivot比較，a[j]小則a[j]→a[i];

否則，利用j向前掃描快速排序中的一趟劃分382797134955123456780465949pivotija[i]與pivot比較，a[i]大則a[i]→a[j];

否則，利用i向后掃描快速排序中的一趟劃分382797134955123456780465949pivotij利用i向后掃描a[i]與pivot比較，a[i]大則a[i]→a[j];快速排序中的一趟劃分382713974955123456780465949pivotij利用j向前掃描快速排序中的一趟劃分382713974955123456780465949pivotija[j]與pivot比較，a[j]小則a[j]→a[i];

否則，利用j向前掃描快速排序中的一趟劃分382713974955123456780465949pivotija[i]與pivot比較，a[i]大則a[i]→a[j];

否則，利用i向后掃描快速排序中的一趟劃分382713974955123456780465949pivotij快速排序中的一趟劃分382713974955123456780465949pivotiji與j相等時(shí)，完成一次劃分快速排序中的一趟劃分382713499749551234567804659intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];pivotkey=L.r[0].key;i=low;j=high;while(i<j){

while(i<j&&L.r[j].key>=pivotkey)j--;L.r[i]=L.r[j];

while(i<j&&L.r[i].key<=pivotkey)i++;L.r[j]=L.r[i];}L.r[i]=L.r[0];returni;}//Partition快速排序intPartition(SqList&L,intlow,inthigh){......returni;//返回樞軸元素的位置}//PartitionvoidQSort(SqList&L,intlow,inthigh){//對(duì)L.r[low]～L.r[high]的元素進(jìn)行快速排序

if(low<high){pivotloc=Partition(L,low,high);//一趟劃分

QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}//if}//QSort快速排序過程分析386597132749*551234567849049劃分382713499749*550465劃分38271304劃分9749*5565劃分132738劃分2713劃分49*5565劃分6555276510.3快速排序分析以順序表作為存儲(chǔ)結(jié)構(gòu)的快速排序算法時(shí)間復(fù)雜度：O(nlogn)快速排序在最好情形下(左、右子區(qū)間的長度大致相等)，則結(jié)點(diǎn)數(shù)n與二叉樹深度h應(yīng)滿足log2n<h<log2n+1，所以總的比較次數(shù)不會(huì)超過(n+1)log2n。因此，快速排序的最好時(shí)間復(fù)雜度應(yīng)為O(nlog2n)。理論上已經(jīng)證明，快速排序的平均時(shí)間復(fù)雜度也為O(nlog2n)。在最壞情況下(逆序或正序)，時(shí)間復(fù)雜度為O(n2)空間復(fù)雜度：O(logn)在最壞情況下(逆序或正序)，空間復(fù)雜度為O(n)不穩(wěn)定的排序方法快速排序不適合對(duì)小規(guī)模的序列進(jìn)行排序10.3快速排序分析以順序表作為存儲(chǔ)結(jié)構(gòu)的快速排序算法時(shí)間復(fù)雜度：O(nlogn)快速排序在最好情形下的時(shí)間復(fù)雜度為O(nlog2n)。理論上已經(jīng)證明，快速排序的平均時(shí)間復(fù)雜度也為O(nlog2n)。在最壞情況下(逆序或正序)，時(shí)間復(fù)雜度為O(n2)空間復(fù)雜度：O(logn)在最壞情況下(逆序或正序)，空間復(fù)雜度為O(n)不穩(wěn)定的排序方法快速排序不適合對(duì)小規(guī)模的序列進(jìn)行排序假設(shè)一次劃分所得樞軸位置i=k，則對(duì)n個(gè)記錄進(jìn)行快排所需時(shí)間為：

T(n)=Tpass(n)+T(k-1)+T(n-k)其中Tpass(n)為對(duì)n個(gè)記錄進(jìn)行一次劃分所需時(shí)間。若待排序列中記錄的關(guān)鍵字隨機(jī)分布，則k

取1至n

中任一值的可能性相同，由此可得快速排序所需時(shí)間的平均值為：10.3快速排序方法的改進(jìn)樞軸元素的選取三者取中隨機(jī)選擇劃分的過程中進(jìn)行“起泡”操作當(dāng)劃分出的子序列長度小于某個(gè)值時(shí)，不再遞歸，而進(jìn)行直接插入排序快速排序算法被認(rèn)為是內(nèi)部排序方法中最好的一種選擇排序1327384949*55650497123456789最壞情況下的快速排序1327384949*556504971327384949*55659727384949*556597384949*5565974949*55659749*556597556597659797return最好情況下的快速排序046597135549*381234567849279劃分043813495549*972765劃分13043827劃分6549*5597劃分380413劃分49*976565return劃分0410.4選擇排序1.簡單選擇排序簡單選擇排序的基本思想是：第一趟在n個(gè)記錄中選取最小記錄作為有序序列的第一個(gè)記錄，第二趟在n-1個(gè)記錄中選取最小記錄作為有序序列的第二個(gè)記錄，第i趟在n-i+1個(gè)記錄中選取最小的記錄作為有序序列多中的第i個(gè)記錄。10.4簡單選擇排序過程示例初始關(guān)鍵字序列3412492831525149*123456780i=11234492831525149*i=21228493431525149*i=31228313449525149*i=41228313449525149*i=51228313449525149*i=6122831344949*5152i=7122831344949*5152return10.4簡單選擇排序算法以順序表作為存儲(chǔ)結(jié)構(gòu)的簡單選擇排序算法voidSelectSort(SqList&L){//對(duì)順序表作簡單選擇排序

for(i=1;i<L.ength;i++){for(k=i,j=i;k<=L.length;k++)if(L.r[k].key<L.r[j].key)j=k;if(j!=i){L.r[i]←

→L.r[j];}}//for}//SelectSort分析簡單選擇排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)for(i=1;i<L.length;i++){

for(k=i,j=i;k<=L.length;k++)if(L.r[k].key<L.r[j].key)j=k;if(j!=i){L.r[i]←

→L.r[j];}}//for}//iffor(k=i+1,j=i;k<=L.length;k++)if(L.r[k].key<L.r[j].key)j=k;if(j!=i){L.r[i]←

→L.r[j];}在逆序情況下元素的比較次數(shù):n(n-1)/2元素的移動(dòng)次數(shù)為：3(n-1)/2在正序情況下元素的比較次數(shù):n(n-1)/2元素的移動(dòng)次數(shù)為：010.4簡單選擇排序算法分析以順序表作為存儲(chǔ)結(jié)構(gòu)的簡單選擇排序算法時(shí)間復(fù)雜度：O(n2)在n個(gè)關(guān)鍵字中選出最小者，需要n-1次比較，繼續(xù)在剩余的n-1個(gè)元素中選出次小者需要n-2次比較，依此類推?？臻g復(fù)雜度：O(1)只需要

1個(gè)輔助單元進(jìn)行交換不穩(wěn)定的排序方法適用情況元素?cái)?shù)目少的情況無需完全排序的情況，比如，選出第i小的元素對(duì)簡單選擇排序過程進(jìn)行改進(jìn)：利用前面已經(jīng)進(jìn)行過的比較結(jié)果10.4選擇排序2.樹形選擇排序(TreeSelectionSort)又稱錦標(biāo)賽排序(TournamentSort):首先對(duì)n個(gè)記錄的關(guān)鍵字兩兩進(jìn)行比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。整個(gè)過程可用一個(gè)含有n個(gè)葉結(jié)點(diǎn)的二叉樹表示。例如3412492831525149*12283149*1231123412

492831525149*10.4選擇排序2.樹形選擇排序(TreeSelectionSort)又稱錦標(biāo)賽排序(TournamentSort):首先對(duì)n個(gè)記錄的關(guān)鍵字兩兩進(jìn)行比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。選出最小記錄后，將樹中的該最小記錄修改為∞，然后從該葉子結(jié)點(diǎn)所在子樹開始，修改到達(dá)樹根的路徑上的結(jié)點(diǎn)34∞

492831525149*34283149*28312834∞

492831525149*10.4選擇排序2.樹形選擇排序(TreeSelectionSort)又稱錦標(biāo)賽排序(TournamentSort):首先對(duì)n個(gè)記錄的關(guān)鍵字兩兩進(jìn)行比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。選出最小記錄后，將樹中的該最小記錄修改為∞，然后從該葉子結(jié)點(diǎn)所在子樹開始修改到達(dá)樹根的路徑上的結(jié)點(diǎn)以后每選出一個(gè)小元素，都只需進(jìn)行(logn)次比較34∞

49∞31525149*34493149*34313134∞

492831525149*10.4選擇排序2.樹形選擇排序的缺陷需要較多的輔助空間存在與“∞”進(jìn)行比較的冗余比較34∞

49∞31525149*34493149*34313110.4選擇排序3.堆排序(HeapSort)只需要一個(gè)元素的輔助空間算法的時(shí)間復(fù)雜度為O(nlogn)堆的定義對(duì)于n個(gè)元素的序列{k1,k2,...,kn}，當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆。

或10.4堆排序堆(完全二叉樹)96833811279(a)大頂堆(maxheap)123685472430(b)小頂堆(minheap)539110.4堆排序3.堆排序(HeapSort)對(duì)一組待排序記錄的關(guān)鍵字，首先把它們按堆的定義建成小(大)頂堆，然后輸出堆頂?shù)淖钚?大)關(guān)鍵字所代表的記錄，再對(duì)剩余的關(guān)鍵字建堆，以便得到次小(大)的關(guān)鍵字，如此反復(fù)進(jìn)行，直到全部關(guān)鍵字排成有序序列為止。

實(shí)現(xiàn)堆排序需要解決兩個(gè)問題：

(1)如何建堆？

(2)輸出堆頂元素后，如何將剩余元素重新調(diào)整為一個(gè)新堆？10.4堆排序過程示例下面是一個(gè)小頂堆，輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆的方法是：從樹根開始，若以某結(jié)點(diǎn)為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向12368547243053919136854724305312交換堆頂元素與序列末端的元素比較比較-交換return10.4堆排序過程示例(續(xù))輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆的方法是：從樹根開始，若以某結(jié)點(diǎn)為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向2436854730915312繼續(xù)向葉子方向調(diào)整2436854791305312比較比較交換10.4堆排序過程示例(續(xù))一旦已調(diào)整為堆，則輸出堆頂元素，重復(fù)將剩余元素重新調(diào)整為一個(gè)新堆。24368547309153125336854730912412交換堆頂元素與序列末端的元素10.4堆排序過程示例(續(xù))輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆3036854753912412調(diào)整成堆533685473091241210.4堆排序過程分析輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆9136854753302412反復(fù)將堆頂元素與序列末端的元素的交換，并重新調(diào)整成堆。9185473653302412調(diào)整堆元素(篩選)

對(duì)于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小(大)頂堆，從而得到最小(大)關(guān)鍵字。

在輸出堆頂元素之后，用堆中最后一個(gè)元素替代之。此時(shí)由于以K2和K3為根的子樹仍具有堆的特性，因此只需自上而下進(jìn)行調(diào)整即可。調(diào)整過程為：首先令K1的兩個(gè)子樹根進(jìn)行比較，令其中較小(大)者與K1相比較，將最小(大)元素交換至K1，使得K1、K2和K3成為堆。由于交換后破壞了子樹的堆性質(zhì)，則需再次進(jìn)行與上述過程類似的調(diào)整，直至進(jìn)行到最下層的葉結(jié)點(diǎn)為止。調(diào)整后即得到一個(gè)有n-1個(gè)元素的新堆，從而得到次小關(guān)鍵字。10.4堆排序過程分析(續(xù))輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆調(diào)整堆元素(篩選)

對(duì)于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小(大)頂堆，從而得到最小(大)關(guān)鍵字。在輸出堆頂元素之后，用堆中最后一個(gè)元素替代之。此時(shí)由于以K2和K3為根的子樹仍具有堆的特性，因此只需自上而下進(jìn)行調(diào)整即可。首先令K1將的兩個(gè)子樹根進(jìn)行比較，令其中較小(大)者與K1相比較，將最小(大)元素交換至K1，使得K1、K2和K3成為堆。由于交換后破壞了右子樹的堆，則需再次進(jìn)行與上述類似的調(diào)整，直至進(jìn)行到最下層的葉結(jié)點(diǎn)。調(diào)整后即得到一個(gè)有n-1個(gè)元素的新堆，從而得到次小關(guān)鍵字。重復(fù)上述過程，將堆頂元素與堆中最后一個(gè)元素交換且調(diào)整，又得到了有n-2個(gè)元素的新堆。為節(jié)省存貯開銷，可以把輸出的最小(大)關(guān)鍵字放在Kn的位置上，把第二次輸出的次小(大)關(guān)鍵字存放在Kn-1的位置上……，直至最大(小)關(guān)鍵字放在K1的位置上。如此，我們已經(jīng)可以在初始情況為堆的情況下完成排序，那么，如何建立起初始堆呢？建初始小頂堆47369112533024851236854724305391元素序列為：47,36,53,91,12,30,24,85建立小頂堆建初始堆4736911253302485(a)4736851253302491(b)從最后一個(gè)具有葉子的結(jié)點(diǎn)(編號(hào)[n/2])開始建子堆，依次考查結(jié)點(diǎn)[n/2]-1,[n/2]-2,...，1等是否為堆，若否則調(diào)整為堆return建初始堆4736851224305391從最后一個(gè)具有葉子的結(jié)點(diǎn)(編號(hào)[n/2])開始建子堆，依次考查結(jié)點(diǎn)[n/2]-1,[n/2]-2,...，1等是否為堆，若否則調(diào)整為堆(C)4712853624305391(d)建初始堆1247853624305391從最后一個(gè)具有葉子的結(jié)點(diǎn)(編號(hào)[n/2])開始建子堆，依次考查結(jié)點(diǎn)[n/2]-1,[n/2]-2,...，1等是否為堆，若否則調(diào)整為堆(e)1236854724305391(f)當(dāng)以下標(biāo)1為根的完全二叉樹為堆時(shí)，初始堆已建立也可以從空堆開始建初始堆10.4堆排序1964年弗洛伊德（Floyd）提出了篩選法建立初始堆，具體方法是：將待排序的關(guān)鍵字分放到一棵完全二叉樹的各個(gè)結(jié)點(diǎn)中（此時(shí)完全二叉樹并不一定具備堆的特性），顯然，所有i≥[n/2]的結(jié)點(diǎn)Ki都沒有子結(jié)點(diǎn)，以這樣的Ki為根的子樹已經(jīng)是堆，因此初始建堆可從完全二叉樹的第i個(gè)結(jié)點(diǎn)Ki開始(i=[n/2])。通過調(diào)整，逐步使以K[n/2]，K[n/2]-1，K[n/2]-2，…為根的子樹滿足堆的定義，直至進(jìn)行到以K1為根的樹排成堆為止。在對(duì)Ki為根的子樹建堆時(shí)，其子樹已經(jīng)為堆，要使得以Ki為根的完全二叉樹為堆，則可能要調(diào)整父、子結(jié)點(diǎn)的位置，如此下一層已建成堆的子樹可能不再滿足堆的定義，則需繼續(xù)進(jìn)行調(diào)整，如此一次次遞推下去，最多可能一直延伸到樹葉。這種方法就像過篩子一樣，把最小(大)的關(guān)鍵字一層一層地篩選出來，最后輸出堆頂?shù)淖钚?大)關(guān)鍵字。10.4堆排序算法(篩選算法)typedefSqListHeapType;//堆采用順序存儲(chǔ)結(jié)構(gòu)voidHeapAdjust(HeapType&H,ints,intm){}//HeapAdjustrc=H.r[s];

for(j=2*s;j<=m;j*=2){//沿key較小的孩子結(jié)點(diǎn)向下篩選

if(j<m&&H.r[j].key>H.r[j+l].key)++j;

//j為key較小的記錄的下標(biāo)

if(rc.Key<H.r[j].key)break;

H.r[s]=H.r[j];//較小的孩子結(jié)點(diǎn)值換到父結(jié)點(diǎn)位置

s=j;}H.r[s]=rc;//rc應(yīng)插入的位置在s處//H.r[s..m]中除H.r[s].key外均滿足堆的定義

//調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一個(gè)小頂堆示例10.4堆排序算法(續(xù))typedefSqListHeapType;//堆采用順序存儲(chǔ)結(jié)構(gòu)voidHeapSort(HeapType&H){//對(duì)順序表H進(jìn)行堆排序

for(i=H.length/2;i>0;--i)//把H建成大頂堆

HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){H.r[1]←→H.r[i];//堆頂記錄和當(dāng)前未排子序列中最后一個(gè)記錄相交換

HeapAdjust(H,1,i-1);//將H.r[l..i-1]重新調(diào)整為大頂堆

}}//HeapSort

for(i=H.length/2;i>0;--i)//把H建成大/小頂堆

HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){H.r[1]←→H.r[i];//堆頂記錄和當(dāng)前未排子序列中最后一個(gè)記錄相交換

HeapAdjust(H,1,i-1);//將H.r[l..i-1]重新調(diào)整為大/小頂堆

}示例473691125330248510.4堆排序算法分析由于是完全二叉樹，所以采用順序存儲(chǔ)結(jié)構(gòu)時(shí)間復(fù)雜度：O(nlog2n)堆排序的整個(gè)算法時(shí)間是由建立初始堆和不斷調(diào)整堆這兩部分時(shí)間代價(jià)構(gòu)成的，建立初始堆時(shí)關(guān)鍵字的比較次數(shù)不超過4n，不斷調(diào)整堆的時(shí)間不超過O(nlog2n)?？臻g復(fù)雜度：O(1)只需要

1個(gè)輔助單元進(jìn)行交換不穩(wěn)定的排序方法對(duì)于記錄數(shù)較少的序列來說，堆排序的優(yōu)越性并不明顯，但對(duì)數(shù)量大的序列來說堆排序是很有效的。歸并排序篩選過程示例下面是一個(gè)大頂堆，輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆的方法是：從樹根開始，若以某結(jié)點(diǎn)為根的子樹不是堆，則將其孩子中的較大者與之交換，即將非堆的子樹推向葉子方向9153364785302412交換堆頂元素與序列末端的元素比較比較-交換return(a)大頂堆1253364785302491(b)8553364712302491(c)8553364730122491(d)大頂堆比較比較交換篩選過程示例下面是一個(gè)大頂堆，輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆的方法是：從樹根開始，若以某結(jié)點(diǎn)為根的子樹不是堆，則將其孩子中的較大者與之交換，即將非堆的子樹推向葉子方向9153364785302412交換堆頂元素與序列末端的元素比較比較-交換return(a)小頂堆1253364785302491(b)8553364712302412(c)小頂堆交換堆頂元素與序列末端的元素5336854791302412(d)10.5歸并排序歸并所謂“歸并”，是將兩個(gè)或兩個(gè)以上的有序序列合并成為一個(gè)新的有序序列。從第二章線性表的討論中得知，將兩個(gè)有序表歸并為一個(gè)有序表，無論是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都是容易實(shí)現(xiàn)的。利用歸并的思想可以進(jìn)行排序。歸并排序可將由n個(gè)記錄的一個(gè)無序序列看成是由n個(gè)長度為1的有序子序列組成的序列，然后進(jìn)行兩兩歸并，得到[n/2]個(gè)長度為2或1的有序子序列，再兩兩歸并，……，如此重復(fù)，直到最后形成包含n個(gè)記錄的一個(gè)有序序列為止。這種總是反復(fù)將兩個(gè)有序序列歸并成一個(gè)有序序列的排序方法稱為兩路歸并排序。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]2-路歸并10.5兩路歸并過程示例設(shè)初始關(guān)鍵字序列為:4834608075122648*[48][34][6O][80][75][12][26][48*]第一趟歸并：[34,48,60,80]第三趟歸并：

[12,26,34,48,48*,60,75,80][60,80][12,75][26,48*][12,26,48*,75][34,48]第二趟歸并：合并兩個(gè)序列時(shí)，將合并得到的序列與原序列分開存放也可以用分治思路處理10.5先分解再歸并設(shè)初始關(guān)鍵字序列為:[4834608075122648*][48346O8075122648*][75122648*][48346080][4834][6080][7512][2648*][48][34][60][80][75][12][26][48*][3448][6080][1275][2648*][122648*75][34486080][1226344848*607580]分解歸并10.5兩路歸并排序算法遞歸算法voidMergeSort(待排序列){//歸并排序

if(待排序列長度>1){MergeSort(待排序列的前半?yún)^(qū)間)；

MergeSort(待排序列的后半?yún)^(qū)間)；已排好序的前半?yún)^(qū)間、后半?yún)^(qū)間合并成一個(gè)有序序列；

}//if}//MergeSort采用順序存儲(chǔ)結(jié)構(gòu)，對(duì)于由下標(biāo)s~t界定的一個(gè)序列，前半?yún)^(qū)間為s~(s+t)/2，后半?yún)^(qū)間為(s+t)/2+1~tvoidMergeSort(SqList&L,ints,intt){//歸并排序

if(s<t){m=(s+t)/2;MergeSort(L,s,m)；

MergeSort(L,m+1,t)；

Merge(L,s,m,t);//合并L.r[s]~L.r[m]與L.r[m+1]~L.r[t]}//if}//MergeSort10.5兩路歸并算法以順序表作為存儲(chǔ)結(jié)構(gòu)voidMerge(SqList&L,inti,intm,intn){//兩路歸并

//引入輔助數(shù)組空間temp，有序序列為r[i..m]和r[m+1..n]}//Mergeb=i;for(j=m+1,k=1;i<=m&&j<=n;++k){

}//for//ifi]if(L.r[i].key<L.r[j].key)temp.r[k]=L.r[i++];elsetemp.r[k]=L.r[j++];for(;i<=m;)temp.r[k++]=L.r[i++];for(;j<=n;)temp.r[k++]=L.r[j++];

for(i=b,k=1;i<=n;)L.r[i++]=temp.r[k++];10.5歸并排序算法分析以順序表作為存儲(chǔ)結(jié)構(gòu)的歸并排序算法時(shí)間復(fù)雜度：O(nlogn)對(duì)于具有n個(gè)元素的一個(gè)序列，元素的移動(dòng)次數(shù)可以使用下面的遞歸公式計(jì)算：M(1)=0M(n)=2M(n/2)+2n空間復(fù)雜度：O(n)這是歸并排序的嚴(yán)重缺點(diǎn)穩(wěn)定的排序方法用迭代取代遞歸進(jìn)行歸并排序效率更高10.6基數(shù)排序基數(shù)排序(RadixSorting)基數(shù)排序是一種借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法，不需要進(jìn)行記錄關(guān)鍵字間的比較。例如：整理撲克牌、圖書館卡片的排序多關(guān)鍵字排序：n個(gè)元素的序列{R1,R2,...,Rn}，每個(gè)元素Ri有d個(gè)關(guān)鍵字(K0i,K1i,...,Kd-1i)，則序列對(duì)關(guān)鍵字(K0i,K1i,...,Kd-1i)有序是指：對(duì)于序列中任意兩個(gè)記錄Ri和Rj記都滿足下列有序關(guān)系：

(K0i,K1i,...,Kd-1i)<(K0j,K1j,...,Kd-1j)

其中K0稱為最主位關(guān)鍵字，Kd-1稱為最次位關(guān)鍵字。10.6基數(shù)排序多關(guān)鍵字排序最高位優(yōu)先(MSD):先對(duì)最主位關(guān)鍵字K0進(jìn)行排序,將序列分成若干個(gè)子序列，每個(gè)子序列中的元素具有相同的K0值，然后分別就每個(gè)子序列對(duì)關(guān)鍵字K1進(jìn)行排序，按K1值的不同再分成更小的子序列，依次重復(fù)，直至對(duì)Kd-2進(jìn)行排序之后得到的每個(gè)子序列中的元素都具有相同的(K0,K1,...,Kd-2)，而后分別對(duì)每個(gè)子序列對(duì)Kd-1

進(jìn)行排序，最后將所有子序列依次聯(lián)接在一起成為一個(gè)有序序列。最低位優(yōu)先(LSD):先對(duì)最次位關(guān)鍵字Kd-1進(jìn)行排序,然后對(duì)Kd-2進(jìn)行排序，依次重復(fù)，直至對(duì)K0進(jìn)行排序后便形成一個(gè)有序序列。10.6鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序借助“分配”和“收集”兩種操作對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法。有的單邏輯關(guān)鍵字可以看成是由若干個(gè)關(guān)鍵字復(fù)合而成。例如，若關(guān)鍵字是數(shù)值，且其值都在0≤K≤999范圍內(nèi)，則可把每一個(gè)十進(jìn)制數(shù)字看成一個(gè)關(guān)鍵字，即可認(rèn)為K由3個(gè)關(guān)鍵字(K0,K1,K2)組成，其中，K0是百位數(shù)，K1是十位數(shù)，K2是個(gè)位數(shù)，且0≤Ki≤9(RADIX＝10)，由于每個(gè)關(guān)鍵字的范圍相同，則按LSD進(jìn)行排序，只要從最低數(shù)位關(guān)鍵字起，按關(guān)鍵字的不同值將序列中記錄“分配”到RADIX個(gè)隊(duì)列中后再“收集”之，如此重復(fù)d次，即可實(shí)現(xiàn)基數(shù)排序。具體來講，第一次對(duì)最低位關(guān)鍵字(個(gè)位數(shù))進(jìn)行分配，將初始序列中的元素分配到RADIX個(gè)隊(duì)列中去，每個(gè)隊(duì)列中的元素的關(guān)鍵字的個(gè)位數(shù)相同。用f[i]和e[i]分別表示第i個(gè)隊(duì)列的頭指針和尾指針。10.6鏈?zhǔn)交鶖?shù)排序278用鏈表表示元素序列109063930589184505269008083e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]278109063930589184505269008083分配1收集193006308318450527800810958926910.6鏈?zhǔn)交鶖?shù)排序(續(xù))用鏈表表示元素序列e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]083930505184269分配2收集250500810993006326927808318458993006308318450527800810958926906327800810958910.6鏈?zhǔn)交鶖?shù)排序(續(xù))用鏈表表示元素序列e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]083930505184278分配3收集300806308310918426927850558993006326900810958950500810993006326927808318458910.6鏈?zhǔn)交鶖?shù)排序方法分析采用鏈?zhǔn)酱鎯?chǔ)，避免元素移動(dòng)時(shí)間復(fù)雜度：O(d(n+rd))，rd為每個(gè)關(guān)鍵字的基數(shù)每一趟分配：O(n)每一趟收集：O(rd)共d趟：d(n+rd)

空間復(fù)雜度：O(rd)2rd個(gè)隊(duì)列指針穩(wěn)定的排序方法適用于元素?cái)?shù)目n很大且關(guān)鍵字很小的情況10.7內(nèi)部排序方法分析與比較時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性適用情況鏈?zhǔn)交鶖?shù)排序2－路歸并排序堆排序簡單選擇排序快速排序冒泡排序希爾排序直接插入排序O(n2)O(1)穩(wěn)定n較小，初始序列基本有序O(n1.3)O(1)不穩(wěn)定O(n2)O(1)穩(wěn)定n較小，初始序列基本有序O(nlog2n)O(log2n)不穩(wěn)定初始序列無序O(n2)O(1)不穩(wěn)定n較小O(nlog2n)O(1)不穩(wěn)定n較大，或只排前幾位O(nlog2n)O(n)穩(wěn)定n很大O(d(n+rd))O(rd)穩(wěn)定n大，關(guān)鍵字值小10.7內(nèi)部排序方法分析與比較內(nèi)部排序可能達(dá)到的最快速度是多少？在已經(jīng)討論過的方法中，最壞情況下的時(shí)間復(fù)雜度為O(n2)或O(nlog2n)，因此排序速度的上界是O(n2)，那么O(nlog2n)是否為其下界呢？下面先看一個(gè)例子。K3<k2<k1K1<k2K1<k3K2<k3K2<k3<k1否否否是K2<k1<k3K2<k3K1<k3否K1<k2<k3是是K3<k1<k2K1<k3<k2否是10.7內(nèi)部排序方法分析與比較若二叉樹的高度為h，則其葉子結(jié)點(diǎn)數(shù)目不超過2h-1;反之，若二叉樹中有u個(gè)葉子結(jié)點(diǎn)，則二叉樹的高度至少為log2u＋1（向上取整），因此任何一個(gè)借