常用排序算法

常用排序算法第1頁，共56頁，2023年，2月20日，星期一內(nèi)部排序:

指的是待排序記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程。外部排序:

指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。內(nèi)部排序與外部排序第2頁，共56頁，2023年，2月20日，星期一假設(shè)Ki=Kj

，且排序前序列中Ri

領(lǐng)先于Rj

；若在排序后的序列中Ri

仍領(lǐng)先于Rj

，則稱排序方法是穩(wěn)定的。若在排序后的序列中Rj

仍領(lǐng)先于Ri

，則稱排序方法是不穩(wěn)定的。例，序列3158

869若排序后得368

8915穩(wěn)定的若排序后得368

8915不穩(wěn)定的排序衡量指標(biāo)——穩(wěn)定性第3頁，共56頁，2023年，2月20日，星期一排序衡量指標(biāo)——時間復(fù)雜度排序過程主要是對記錄的排序碼進(jìn)行比較和記錄的移動過程。排序的時間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進(jìn)行的比較和移動次數(shù)越少，則認(rèn)為該方法的時間復(fù)雜性就越好，分析一種排序方法，不僅要分析它的時間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性等。第4頁，共56頁，2023年，2月20日，星期一按照排序過程中所依據(jù)的原則的不同可以分類為:插入排序交換排序(快速排序)選擇排序歸并排序基數(shù)排序二叉排序樹排序內(nèi)部排序第5頁，共56頁，2023年，2月20日，星期一思想:利用有序表的插入操作進(jìn)行排序有序表的插入:

將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。例，序列132738657697插入4913273849

657697插入排序——直接插入排序第6頁，共56頁，2023年，2月20日，星期一直接插入排序——算法描述例，序列49386597761327初始，S={49}；{3849}初始，令第1

個元素作為初始有序表；依次插入第

2,3,…,k

個元素構(gòu)造新的有序表；直至最后一個元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要應(yīng)用比較和移動兩種操作。第7頁，共56頁，2023年，2月20日，星期一voidInsert(ArrNode*pnum){for(i=1;i<Len;i++){ tmp=pnum[i]; for(j=i;j>0&&tmp.key<pnum[j-1].key;j--){ pnum[j]=pnum[j-1]; } pnum[j]=tmp; }}直接插入排序——算法描述第8頁，共56頁，2023年，2月20日，星期一時間復(fù)雜度分析：外層循環(huán)要進(jìn)行n-1次插入，每次插入最少比較一次（正序），移動兩次；最多比較i次，移動i＋2次（逆序）（i=1,2,…,n-1）。Cmin=n-1Mmin=2（n-1）Cmax=1+2+…+n-1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mmax=（n2+7n-8）/4因此，直接插入排序的時間復(fù)雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。直接插入排序的效率分析第9頁，共56頁，2023年，2月20日，星期一由于直接插入排序算法利用了有序表的插入操作，故順序查找操作可以替換為折半查找操作。例，序列49386597761327設(shè)已形成有序表{3849659776}插入元素13折半插入排序第10頁，共56頁，2023年，2月20日，星期一voidBinaryInsertSort(ArrNode*pnum，intL){for(inti=1;i<L;i++)//共進(jìn)行n-1次插入

{intleft=0,right=i-1;temp=pnum[i]; while(left<=right) {intmiddle=(left+right)/2;//取中點

if(temp<pnum[middle])right=middle-1;//取左區(qū)間

else left=middle+1;//取右區(qū)間

} for(intj=i-1;j>=left;j--) pnum[j+1]=pnum[j];//元素后移空出插入位

pnum[left]=temp;}}折半插入排序——算法描述第11頁，共56頁，2023年，2月20日，星期一折半插入效率分析二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時間上，前者的比較次數(shù)比直接插入查找的最壞情況好，最好的情況壞，兩種方法的元素的移動次數(shù)相同，因此二分插入排序的時間復(fù)雜度仍為O(n2)。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩(wěn)定的。第12頁，共56頁，2023年，2月20日，星期一直接插入排序1.若待排序記錄序列按關(guān)鍵字基本有序，則排序效率可大大提高；2.待排序記錄總數(shù)越少，排序效率越高；希爾(shell)排序第13頁，共56頁，2023年，2月20日，星期一將待排序記錄序列分割成為若干子序列分別進(jìn)行直接插入排序；待整個序列中的記錄基本有序后，再全體進(jìn)行一次直接插入排序。例，序列493865977613274855419第一趟排序491319382765489755764131949273848655597476希爾(shell)排序——算法思想第14頁，共56頁，2023年，2月20日，星期一第二趟排序13194927384865559747613553876274

654948199713385576427

4965194897第三趟排序4131927

38

4849

556576

97第15頁，共56頁，2023年，2月20日，星期一voidHill(ArrNode*pnum,intincrement)//初始值為Lens{printf("\nTheHillSortlistis\n");for(h=increment;h>0;h=h/2){ for(j=h;j<Len;j++){ t=*(pnum+j); for(k=j-h;(k>=0&&t.key<pnum[k].key);k=k-h) *(pnum+k+h)=*(pnum+k); *(pnum+k+h)=t; } }}希爾(shell)排序——算法思想第16頁，共56頁，2023年，2月20日，星期一希爾排序效率分析希爾排序的時間復(fù)雜性在O（nlog2n）和O（n2

）之間，大致為O（n1.3）。第17頁，共56頁，2023年，2月20日，星期一思想:

通過不斷比較相鄰元素大小，進(jìn)行交換來實現(xiàn)排序。首先將第一個元素與第二個元素比較大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；...直至比較第n-1個元素與第n個元素的大小，若為逆序，則交換；第一趟排序:結(jié)果:關(guān)鍵字最大的記錄被交換至最后一個元素位置上。交換排序——冒泡排序第18頁，共56頁，2023年，2月20日，星期一例，序列4938761327493876132738

49

13

27384913762776初始第一趟排序后最大值13

492749次大值第二趟排序后3813

27132713382738第三趟排序后第四趟排序后第19頁，共56頁，2023年，2月20日，星期一voidBubble(ArrNode*pnum){for(i=0;i<Len-1;i++){ for(j=Len-1;j>i;j--){ if(pnum[j-1].key>pnum[j].key){ tmp=pnum[j]; pnum[j]=pnum[j-1]; pnum[j-1]=tmp; } }}}冒泡排序的算法實現(xiàn)第20頁，共56頁，2023年，2月20日，星期一從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進(jìn)行一趟排序，比較次數(shù)為（n-1）次，移動元素次數(shù)為0；若待排序的元素為逆序，則需進(jìn)行n-1趟排序，比較次數(shù)為(n2-n)/2，移動次數(shù)為3(n2-n)/2，因此冒泡排序算法的時間復(fù)雜度為O（n2）。由于其中的元素移動較多，所以屬于內(nèi)排序中速度較慢的一種。因為冒泡排序算法只進(jìn)行元素間的順序移動，所以是一個穩(wěn)定的算法。冒泡排序的效率分析第21頁，共56頁，2023年，2月20日，星期一冒泡排序的一種改進(jìn)算法。思想:以首記錄作為軸記錄，從前、后雙向掃描序列，通過交換，實現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適當(dāng)?shù)奈恢谩?小值記錄在前、大值記錄在后)軸記錄將原序列分割成兩部分，依次對前后兩部分重新設(shè)定軸記錄，繼而分別再進(jìn)行快速排序。直至整個序列有序。交換排序——快速排序第22頁，共56頁，2023年，2月20日，星期一快速排序—算法思想第23頁，共56頁，2023年，2月20日，星期一3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49快速排序—算法思想第24頁，共56頁，2023年，2月20日，星期一

voidQuick(ArrNode*pnum,intlow,inthigh){inti=low,j=high;ArrNodekey;key=pnum[i];if(i>=j)return;while(i<j){ while(i<j&&pnum[j].key>key.key) j--; if(i<j){ pnum[i]=pnum[j]; i++;}快速排序—算法思想第25頁，共56頁，2023年，2月20日，星期一

while(i<j&&pnum[i].key<key.key) i++; if(i<j){ pnum[j]=pnum[i]; j--; }}pnum[i]=key;printf("\n");Quick(pnum,low,j-1);Quick(pnum,j+1,high);}快排序---分割過程偽碼第26頁，共56頁，2023年，2月20日，星期一快速排序的效率分析若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長度大致相等），則結(jié)點數(shù)n與二叉樹深度h應(yīng)滿足log2n<h<log2n+1，所以總的比較次數(shù)不會超過(n+1)log2n。因此，快速排序的最好時間復(fù)雜度應(yīng)為O（nlog2n）。而且在理論上已經(jīng)證明，快速排序的平均時間復(fù)雜度也為O（nlog2n）。若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，得到的非空子區(qū)間包含有n-i個(i代表二叉樹的層數(shù)（1≤i≤n）元素，每層劃分需要比較n-i+2次，所以總的比較次數(shù)為（n2+3n-4）/2。因此，快速排序的最壞時間復(fù)雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復(fù)雜度為O（log2n），最壞的空間復(fù)雜度為O(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。第27頁，共56頁，2023年，2月20日，星期一思想:

每一趟都選出一個最大或最小的元素，并放在合適當(dāng)?shù)奈恢?。簡單選擇排序樹形選擇排序堆排序選擇排序第28頁，共56頁，2023年，2月20日，星期一思想:

第1趟選擇:從1—n

個記錄中選擇關(guān)鍵字最小的記錄，并和第1個記錄交換。第2趟選擇:從2—n

個記錄中選擇關(guān)鍵字最小的記錄，并和第2

個記錄交換。第n-1趟選擇:從n-1—n

個記錄中選擇關(guān)鍵字最小的記錄，并和第n-1

個記錄交換。...簡單選擇排序第29頁，共56頁，2023年，2月20日，星期一例，序列4938976576第1趟選擇:min3849976576第2趟選擇:min38

49976576第3趟選擇:min38

49

659776第4趟選擇:min38

49

65

7697第30頁，共56頁，2023年，2月20日，星期一voidChoise(ArrNode*pnum){for(i=0;i<Len-1;i++){ minLoc=i; for(j=i+1;j<Len;j++){ if(pnum[minLoc].key>pnum[j].key) minLoc=j; } if(i!=minLoc){ tmp=pnum[minLoc]; pnum[minLoc]=pnum[i]; pnum[i]=tmp; }}}直接選擇排序的偽碼描述第31頁，共56頁，2023年，2月20日，星期一選擇排序的主要操作是進(jìn)行關(guān)鍵字間的比較。在n個關(guān)鍵字中選出最小值，至少需要n-1次比較。在剩余的n-1個關(guān)鍵字中選出最小值，至少需要n-2次比較？如果能利用前n-1次比較所得信息，可以減少后面選擇的比較次數(shù)。第32頁，共56頁，2023年，2月20日，星期一例，序列4938659776132750第一趟選擇133813493865977613275038651327最小值樹形選擇排序第33頁，共56頁，2023年，2月20日，星期一第二趟選擇2738274938659776∞275038657627次小值第三趟選擇3838504938659776∞∞5038657650次次小值49386597761327504938659776∞2750缺點:

需要大量輔助存儲空間，最大值多余比較第34頁，共56頁，2023年，2月20日，星期一堆:

一棵完全二叉樹，任一個非終端結(jié)點的值均小于等于(或大于等于)其左、右子樹結(jié)點的值。1285473053362491963811

98324小頂堆大頂堆堆排序第35頁，共56頁，2023年，2月20日，星期一2.把這棵普通的完全二叉樹改造成堆，便可獲取最小值；堆排序算法思想:3.輸出最小值；4.刪除根結(jié)點，繼續(xù)改造剩余樹成堆，便可獲取次小值；5.輸出次小值；6.重復(fù)改造，輸出次次小值、次次次小值，直至所有結(jié)點均輸出，便得到一個排序。1.將序列構(gòu)造成一棵完全二叉樹；盡可能減少存儲空間開銷，讓待排序的記錄僅占最小的空間（1個）第36頁，共56頁，2023年，2月20日，星期一例，序列49386597761327501.按順序依次構(gòu)造成完全二叉樹的結(jié)點；49386597761327502.把完全二叉樹改造成堆；從下向上，父子交換；50971365134949273.取得最小值134.刪除13

，重新改造成新堆；1397279797495.取得次小值27；6.刪除27

，重新改造成新堆；9727973897507.取得次次小值38；第37頁，共56頁，2023年，2月20日，星期一堆排序算法思想:voidHeap(ArrNode*pnum,intL){inti,k;ArrNodet;for(i=L/2-1;i>=0;i--) createheap(pnum,i,L); //Thebasicheapfor(k=L-1;k>0;k--){ t=*pnum; *pnum=*(pnum+k); *(pnum+k)=t; createheap(pnum,0,k);}}第38頁，共56頁，2023年，2月20日，星期一堆排序算法思想:voidcreateheap(ArrNode*pnum,inti,intnLens){intnChild,nTemp;for(nTemp=pnum[i].key;2*i+1<nLens;i=nChild){ nChild=2*i+1; if((nChild!=nLens-1) &&(pnum[nChild+1].key>pnum[nChild].key)) ++nChild; if(nTemp<pnum[nChild].key) pnum[i]=pnum[nChild]; else break;}pnum[i].key=nTemp;}第39頁，共56頁，2023年，2月20日，星期一歸并排序（MergeSort)歸并---合并兩個有序的序列假設(shè)有兩個已排序好的序列A（長度為n1），B（長度為n2），將它們合并為一個有序的序列C（長度為n=n1+n2)方法：把A，B兩個序列的最小元素進(jìn)行比較，把其中較小的元素作為C的第一個元素；在A，B剩余的元素中繼續(xù)挑最小的元素進(jìn)行比較，確定C的第二個元素，依次類推，就可以完成對A和B的歸并，其復(fù)雜度為O(n)第40頁，共56頁，2023年，2月20日，星期一歸并---合并兩個有序的序列A:138911B:2571013歸并排序（MergeSort)C:1

2

3

5

7

89

10

11

13第41頁，共56頁，2023年，2月20日，星期一voidmerge(TA[],intAlen,TB[],intBlen,TC[]){inti=0,j=0,k=0;while(i<Alen&&j<Blen){if(A[i]<B[j]) C[k++]=A[i++]; else C[k++]=B[j++]; } while(i<Alen) C[k++]=A[i++]; while(j<Blen) C[k++]=B[j++];}歸并排序（MergeSort)第42頁，共56頁，2023年，2月20日，星期一歸并---合并一個序列中的兩個有序的數(shù)據(jù)段voidmerge(TA[],intl,intm,inth){inti=l,j=m+1,k=0;T*C=newT[h-l+1];while(i<=m&&j<=h){if(A[i]<A[j])C[k++]=A[i++]; elseC[k++]=A[j++];} while(i<=m)C[k++]=A[i++]; while(j<=h)C[k++]=B[j++];for(k=0;k<h-l+1;k++)A[i+k]=C[k];//將排好序的元素寫回A數(shù)組

delete[]C;}第43頁，共56頁，2023年，2月20日，星期一歸并排序（MergeSort)歸并排序歸并排序是一個分治遞歸算法遞歸基礎(chǔ)：若序列只有一個元素，則它是有序的，不執(zhí)行任何操作遞歸步驟：先把序列劃分成長度基本相等的兩個序列對每個子序列遞歸排序把排好序的子序列歸并成最后的結(jié)果第44頁，共56頁，2023年，2月20日，星期一歸并排序（MergeSort)初始序列：[8，4，5，6，2，1，7，3]分解：[8][4][5][6][2][1][7][3]歸并：[4，8][5，6][1，2][3，7]歸并：[4，5，6，8][1，2，3，7]歸并：[1，2，3，4，5，6，7，8]分解：[8，4，5，6][2，1，7，3]分解：[8，4][5，6][2，1][7，3]第45頁，共56頁，2023年，2月20日，星期一歸并排序（MergeSort)算法分析最壞情況：歸并排序是一個遞歸算法，所以很容易得到算法計算量的遞推公式

所以算法最壞情況的復(fù)雜度為算法需要的輔助空間

第46頁，共56頁，2023年，2月20日，星期一以比較為基礎(chǔ)的排序算法的下界根據(jù)數(shù)據(jù)結(jié)構(gòu)中關(guān)于二叉樹的性質(zhì)，有：最壞情況：任何排序算法至少要做 次比較平均情況：任何排序算法的平均比較次數(shù)的下界是結(jié)論：具有O(nlgn)復(fù)雜度的比較排序算法在漸進(jìn)意義下是最優(yōu)的算法歸并排序（MergeSort)第47頁，共56頁，2023年，2月20日，星期一一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法1.多關(guān)鍵字排序撲克牌問題:已知撲克牌中52張牌面的次序關(guān)系定義為:?

＜

?

＜

?

＜

?花色:面值:2＜3＜＜A...例，?8

?

3＜花色優(yōu)先級更高，為主關(guān)鍵字，面值為次關(guān)鍵字基數(shù)排序第48頁，共56頁，2023年，2月20日，星期一2.52張牌排序方法:最高位優(yōu)先法(MSDF):先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；然后分別對每一堆按“面值”大小整理有序。最低位優(yōu)先法(LSDF):先按不同“面值”分成13堆；然后將這13堆牌自小至大疊在一起(2,3,...,A)；然后將這付牌整個顛倒過來再重新按不同的“花色”分成4堆；最后將這4堆牌按自小至大的次序合在一起。收集分配第49頁，共56頁，2023年，2月20日，星期一3.基數(shù)排序基數(shù)排序就是借助于“分配”和“收集”兩種操作實現(xiàn)對單邏輯關(guān)鍵字的排序。首先，單邏輯關(guān)鍵字通常都可以看作是由若干關(guān)鍵字復(fù)合而成。其次，利用LSDF法實現(xiàn)對若干關(guān)鍵字的排序。例，若關(guān)鍵字是數(shù)值，且值域為0≤K≤999，故可以將K

看作是由3個關(guān)鍵字K0K1K2

組成，例，603是由603

組成。第50頁，共56頁，2023年，2月20日，星期一例，序列278109063