第十章內(nèi)部排序

1、第十章第十章 內(nèi)部排序內(nèi)部排序10.1 排序的基本概念排序的基本概念n排序(sorting)q將一個(gè)數(shù)據(jù)元素的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。q假設(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è)操作過程就是排序。n穩(wěn)定的排序方法穩(wěn)定的排序方法q若若kikj，且在排序前的序列中，且在排序前的序列中Ri領(lǐng)先于領(lǐng)先于Rj，排序，排序后后Ri仍領(lǐng)先于仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反，則稱

2、所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中之，若可能使排序后的序列中Rj仍領(lǐng)先于仍領(lǐng)先于Ri ，則稱所，則稱所用的排序方法是不穩(wěn)定的。用的排序方法是不穩(wěn)定的。n內(nèi)部排序和外部排序內(nèi)部排序和外部排序q待排序的記錄存放在計(jì)算機(jī)的內(nèi)存中所進(jìn)行的排序待排序的記錄存放在計(jì)算機(jī)的內(nèi)存中所進(jìn)行的排序操作稱為內(nèi)部排序。操作稱為內(nèi)部排序。q待排序的記錄數(shù)量很大，以致內(nèi)存一次不能容納全待排序的記錄數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中需要訪問外存的排序過程稱為部記錄，在排序過程中需要訪問外存的排序過程稱為外部排序。外部排序。n排序方法度量排序方法度量q排序過程主要是比較記錄的關(guān)鍵字和移動(dòng)記

3、錄。因排序過程主要是比較記錄的關(guān)鍵字和移動(dòng)記錄。因此排序的時(shí)間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)此排序的時(shí)間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動(dòng)次數(shù)來衡量。當(dāng)一種排序方法使排序過程及數(shù)據(jù)移動(dòng)次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進(jìn)行的比較和移動(dòng)次數(shù)越少，在最壞或平均情況下所進(jìn)行的比較和移動(dòng)次數(shù)越少，則認(rèn)為該方法的時(shí)間復(fù)雜性就越好。則認(rèn)為該方法的時(shí)間復(fù)雜性就越好。q針對(duì)一種排序方法，不僅要分析它的時(shí)間復(fù)雜性，針對(duì)一種排序方法，不僅要分析它的時(shí)間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。10.1 排序的基本概念排序的基

4、本概念(續(xù)續(xù))內(nèi)部排序內(nèi)部排序外部排序外部排序 插入排序（插入排序（直插排序、二分插入排序直插排序、二分插入排序、希爾排序希爾排序） 交換排序（冒泡排序、快速排序）交換排序（冒泡排序、快速排序） 選擇排序（直選排序、樹型排序、堆排序）選擇排序（直選排序、樹型排序、堆排序） 歸并排序（二路歸并排序、多路歸并排序）歸并排序（二路歸并排序、多路歸并排序） 分配排序（多關(guān)鍵字排序、基數(shù)排序）分配排序（多關(guān)鍵字排序、基數(shù)排序） 多路平衡歸并排序多路平衡歸并排序 置換選擇排序置換選擇排序 最佳歸并樹最佳歸并樹排序排序?qū)o序子序列中的將無序子序列中的一個(gè)或幾個(gè)記一個(gè)或幾個(gè)記錄錄“插入插入”到有序序列到有序序

5、列中，從而中，從而增加記錄的有序子序列的長度。增加記錄的有序子序列的長度。通過通過“交換交換”無序序列中的記錄無序序列中的記錄從而得到其中關(guān)鍵字從而得到其中關(guān)鍵字最小或最大最小或最大的記錄，并將它的記錄，并將它加入到有序子序加入到有序子序列列中，以此方法增加記錄的有序中，以此方法增加記錄的有序子序列的長度。子序列的長度。從記錄的無序子序列中從記錄的無序子序列中“選擇選擇”關(guān)鍵字關(guān)鍵字最小或最大最小或最大的記錄，并將的記錄，并將它它加入到有序子序列加入到有序子序列中，以此方中，以此方法增加記錄的有序子序列的長度。法增加記錄的有序子序列的長度。通過通過“歸并歸并”兩個(gè)或兩個(gè)以上的兩個(gè)或兩個(gè)以上的記

6、錄有序子序列記錄有序子序列，逐步增加記錄，逐步增加記錄有序序列的長度。有序序列的長度。10.2 插入排序插入排序1. 直接插入排序基本思想是：n個(gè)待排序的元素由一個(gè)有序表和一個(gè)無序表組成，開始時(shí)有序表中只包含一個(gè)元素。排序過程中，每次從無序表中取出第一個(gè)元素，將其插入到有序表中的適當(dāng)位置，使有序表的長度不斷加長，完成排序過程。有序序列有序序列R1.i-1Ri無序序列無序序列 Ri.n有序序列有序序列R1.i無序序列無序序列 Ri+1.n10.2 直接插入排序過程示例直接插入排序過程示例初始關(guān)鍵字序列3412492831525149*123456780監(jiān)視哨監(jiān)視哨i=21234492831525

7、149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=61228313449525149*52i=71228313449515249*51i=8122831344949*515249*10.2 直接插入排序算法直接插入排序算法v數(shù)據(jù)結(jié)構(gòu)定義#define MAXSIZE 20typedef int Keytype; / 定義關(guān)鍵字類型為整型typedef struct KeyType key; / 關(guān)鍵字項(xiàng) InfoType otherinfo; / 其他數(shù)據(jù)項(xiàng)RedType; / 記錄類型typed

8、ef struct RedType rMAXSIZE+1; / r0閑置或用作哨兵 int length; / 順序表長度SqList; / 順序表類型10.2 直接插入排序算法直接插入排序算法v以順序表作為存儲(chǔ)結(jié)構(gòu)的直接插入排序算法void InsertSort(SqList &L) for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if

9、/ InsertSortv分析直接插入排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)分析直接插入排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù) for(i = 2; i = L.length; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.ri-1; for(j = i - 2; L.r0.key L.rj

10、.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if最好情況下最好情況下( (正序正序) )元素的比較次數(shù)為元素的比較次數(shù)為: : n - 1 元素的移動(dòng)次數(shù)為元素的移動(dòng)次數(shù)為: :0最壞情況下最壞情況下(逆序逆序)元素的比較次數(shù)元素的比較次數(shù): : (n+2)(n-1)/2元素的元素的移動(dòng)次數(shù)為：移動(dòng)次數(shù)為： (n+4)(n-1)/2 10.2 直接插入排序算法直接插入排序算法v以順序表作為存儲(chǔ)結(jié)構(gòu)的直接插入排序算法以順序表作為存儲(chǔ)結(jié)構(gòu)的直接插入排序算法q時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(nO(n2 2) )n在最好情況下在最好情況下( (正序正序) )，元素的移

11、動(dòng)次數(shù)為，元素的移動(dòng)次數(shù)為0 0，比較次數(shù)，比較次數(shù)為為n 1n 1；n在最壞情況下在最壞情況下( (逆序逆序) )，元素的移動(dòng)次數(shù)為，元素的移動(dòng)次數(shù)為(n+4)(n-1)/2(n+4)(n-1)/2，比較次數(shù)為，比較次數(shù)為 (n+2)(n-1)/2(n+2)(n-1)/2q空間復(fù)雜度：空間復(fù)雜度：O(1)O(1)n只需要只需要 1 1 個(gè)輔助單元個(gè)輔助單元q穩(wěn)定的排序方法穩(wěn)定的排序方法q適用情況適用情況n元素?cái)?shù)目少，或者元素的初始序列基本有序元素?cái)?shù)目少，或者元素的初始序列基本有序10.2 其他插入排序其他插入排序2. 其他插入排序q在尋找插入位置時(shí)采用二分查找，則稱為折半插入排序;q2-路插

12、入排序在此基礎(chǔ)上增加了輔助空間、減少了記錄的移動(dòng);q表插入排序就是通過鏈接指針，按關(guān)鍵碼的大小，實(shí)現(xiàn)從小到大的鏈接過程，不移動(dòng)元素，用靜態(tài)鏈表實(shí)現(xiàn)。 void InsertSort(SqList &L) /對(duì)順序表對(duì)順序表L作折半插入排序作折半插入排序 for(i=2；i = L.length; i+) L.r0 = L.ri; /保存待插入元素保存待插入元素 low = 1；high = i-1； /設(shè)置初始區(qū)間設(shè)置初始區(qū)間 while(low L.rmid.key) low = mid+1； /插入位置在高半?yún)^(qū)中插入位置在高半?yún)^(qū)中 else high = mid-1； /插入位置在

13、低半?yún)^(qū)中插入位置在低半?yún)^(qū)中 for(j = i - 1; j = high +1; j-) L.rj+1 = L.rj; L.rhigh+1 = L.r0; /* 將元素插入將元素插入 */ 10.2 希爾排序希爾排序3. 希爾排序希爾排序(Shells Sort)(Shells Sort)也稱為縮小增量排序，也稱為縮小增量排序，其改進(jìn)原理主要基于以下兩點(diǎn):q元素基本有序時(shí)，直接插入排序的時(shí)間復(fù)雜度接近于O(n)q元素?cái)?shù)目n較少時(shí)，直接插入排序的效率較高v希爾排序的算法思想希爾排序的算法思想先將整個(gè)待排序元素序列分割成若干個(gè)子序列（由先將整個(gè)待排序元素序列分割成若干個(gè)子序列（由相隔某個(gè)相隔某個(gè)

14、“增量增量”的元素組成的），分別進(jìn)行直接插的元素組成的），分別進(jìn)行直接插入入排序，待整個(gè)序列中的元素基本有序（增量足夠?。┡判颍麄€(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。10.2 希爾排序過程示例希爾排序過程示例初始關(guān)鍵字序列：4938659776132749*123456785504910增量增量d5132749*5504493865123456789776910第一趟排序結(jié)果：第一趟排序結(jié)果：增量增量d3第二趟排序結(jié)果：第二趟排序結(jié)果：130449*3827495565123456789776910增量增量d1第三趟

15、排序結(jié)果：第三趟排序結(jié)果：0413273849*495565123456787697910132749*5504493865977610.2 希爾排序算法希爾排序算法void ShellInsert(SqList &L,int dk) /對(duì)順序表對(duì)順序表L作一趟希爾排序作一趟希爾排序 for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if /

16、ShellInsertSort for(i = dk+1; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if if (L.ri.key 0 &L.r0.key L.rj.key; j -= dk) L.rj+dk = L.rj; /尋找插入位置時(shí)記錄后移尋找插入位置時(shí)記錄后移 L.rj+dk = L.r0; /插入插入 /if10.2 希爾排序算法希爾排序算

17、法(續(xù)續(xù))及分析及分析void ShellInsert(SqList &L,int dk) /對(duì)順序表對(duì)順序表L作一趟希爾排序作一趟希爾排序L . /ShellInsertSortvoid ShellSort(SqList &L,int dlta,int t) /按增量序列按增量序列dlta0.t-1進(jìn)行希爾排序進(jìn)行希爾排序 for(k = 0; k t; k+) ShellInsert(L,dltak); /一趟增量為一趟增量為dltak的希爾排序的希爾排序 /ShellInsertSortv希爾排序的分析是一個(gè)復(fù)雜問題，增量序列的設(shè)置是希爾排序的分析是一個(gè)復(fù)雜問題，增量序列

18、的設(shè)置是關(guān)鍵，尚沒有正式的依據(jù)說明如何設(shè)置最佳的增量序列，關(guān)鍵，尚沒有正式的依據(jù)說明如何設(shè)置最佳的增量序列，大量的實(shí)驗(yàn)表明希爾排序所需的比較和移動(dòng)次數(shù)可達(dá)到大量的實(shí)驗(yàn)表明希爾排序所需的比較和移動(dòng)次數(shù)可達(dá)到n n1.31.3v希爾排序的空間復(fù)雜度為希爾排序的空間復(fù)雜度為O(1)O(1)，是，是不穩(wěn)定的排序方法不穩(wěn)定的排序方法10.3 交換排序交換排序1. 起泡排序起泡排序q基本思想是：將相鄰位置的關(guān)鍵字進(jìn)行比較，若為逆基本思想是：將相鄰位置的關(guān)鍵字進(jìn)行比較，若為逆序則交換之。序則交換之。無序序列無序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1無序序列無序序列R1.n-i有序序

19、列有序序列 Rn-i+1.n比較相鄰記錄，將關(guān)鍵字最大的記比較相鄰記錄，將關(guān)鍵字最大的記錄交換到錄交換到 n-i+1 的位置上的位置上第第 i 趟起泡排序趟起泡排序q若在一趟排序過程中沒有進(jìn)行過交換記錄的操若在一趟排序過程中沒有進(jìn)行過交換記錄的操作，則整個(gè)排序過程終止。作，則整個(gè)排序過程終止。10.3 起泡排序過程示例起泡排序過程示例初始關(guān)鍵字序列：4938659776132749*1234567838496576132749*97第一趟排序后：第一趟排序后：384965132749*7697第二趟排序后：第二趟排序后：3849132749*657697第三趟排序后：第三趟排序后：381327

20、4949*657697第四趟排序后：第四趟排序后：1327384949*657697第五趟排序后：第五趟排序后：1327384949*657697第六趟排序后：第六趟排序后：10.3 起泡排序算法起泡排序算法v以順序表作為存儲(chǔ)結(jié)構(gòu)的起泡排序算法void BubbleSort(SqList &L) for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0;

21、 /if / BubbleSortv分析起泡排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)分析起泡排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù) for(i = 1, change = TRUE; i L.length & change; +i) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /for /if change =FALSE; for(j = 1; j L.rj+1.key ) L.r0 = L

22、.rj; L.rj = L.rj+1; L.rj+1 = L.r0; change =TRUE; /if最好情況下，元素的比較次數(shù)為最好情況下，元素的比較次數(shù)為: n - 1 最壞情況下，比較次數(shù)為最壞情況下，比較次數(shù)為: n(n-1)/2最好情況下，元素的移動(dòng)次數(shù)為最好情況下，元素的移動(dòng)次數(shù)為:0:0最壞情況下，交換次數(shù)為：最壞情況下，交換次數(shù)為：n(n-1)/2n(n-1)/210.3 起泡排序算法起泡排序算法v以順序表作為存儲(chǔ)結(jié)構(gòu)的起泡排序算法q時(shí)間復(fù)雜度：O(n2)n在最好情況下(正序)，元素的交換次數(shù)為0，比較次數(shù)為n 1；n在最壞情況下(逆序)，元素的交換次數(shù)為n(n-1)/2，比

23、較次數(shù)為 (n+2)(n-1)/2q空間復(fù)雜度：O(1)n只需要 1 個(gè)輔助單元進(jìn)行交換q穩(wěn)定的排序方法q適用情況n元素?cái)?shù)目少，或者元素的初始序列基本有序10.3 交換排序交換排序(續(xù)續(xù))2. 快速排序q快速排序(Quick Sorting)是迄今為止所有內(nèi)排序算法中速度最快的一種。無無 序序 的的 記記 錄錄 序序 列列無序記錄子序列無序記錄子序列(1)無序子序列無序子序列(2)樞軸樞軸一次劃分一次劃分分別進(jìn)行快速排序分別進(jìn)行快速排序q其基本思想是：取待排序序列中的某個(gè)元素作為基基準(zhǔn)準(zhǔn)（一般取第一個(gè)元素一般取第一個(gè)元素），通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的關(guān)鍵字均小于

24、或等于基準(zhǔn)元素的關(guān)鍵字，右子序列的關(guān)鍵字則大于基準(zhǔn)元素的關(guān)鍵字，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。38 65 97 13 27 49* 551234567849049pivotij快速排序中的一趟劃分快速排序中的一趟劃分快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))38 65 97 13 27 49* 55123456784904949ijL.rj與與pivot比較，比較，L.rj小則與小則與L.ri交換；否則交換；否則j減減10449L.rj 與與L.ri交換，交換，i加加1快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))38 65 97 13 27 49* 551234

25、56780449949pivotijL.ri與與pivot比較，比較，L.ri大則與大則與L.rj交換；否則交換；否則i增增1快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))L.ri與與pivot比較，比較，L.ri大則與大則與L.rj交換；否則交換；否則i增增138 65 97 13 27 49* 55123456780449949pivotij4965L.ri與與L.rj交換，交換，j減減1快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))38 49 97 13 27 49* 55123456780465949ijL.rj與與pivot比較，比較，L.rj小則與小則與L.ri交換；否則交換；

26、否則j減減1快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))38 49 97 13 27 49* 55123456780465949pivotijL.rj與與pivot比較，比較，L.rj小則與小則與L.ri交換；否則交換；否則j減減1快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))L.rj與與pivot比較，比較，L.rj小則與小則與L.ri交換；否則交換；否則j減減138 49 97 13 27 49* 55123456780465949pivotij2749L.rj小則與小則與L.ri交換，交換，i加加1快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))pivot38 27 97 13 4

27、9 49* 55123456780465949pivotijL.ri與與pivot比較，比較，L.ri大則與大則與L.rj交換；否則交換；否則i增增1L.ri大則與大則與L.rj交換，交換，j減減14997快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))pivotL.rj與與pivot比較，比較，L.rj小則與小則與L.ri交換；否則交換；否則j減減138 27 49 13 97 49* 55123456780465949pivotijL.rj小則與小則與L.ri交換，交換，i加加113 49快速排序中的一趟劃分快速排序中的一趟劃分(續(xù)續(xù))38 27 13 49 97 49* 55123456

28、780465949pivoti j當(dāng)當(dāng)i與與j相等時(shí)，樞軸元素確定了位置相等時(shí)，樞軸元素確定了位置i，結(jié)束本次劃分，結(jié)束本次劃分 快速排序是對(duì)冒泡排序的一種改進(jìn)方法，算法中元快速排序是對(duì)冒泡排序的一種改進(jìn)方法，算法中元素的比較和交換是從兩端向中間進(jìn)行的，排序碼較大素的比較和交換是從兩端向中間進(jìn)行的，排序碼較大的元素一次就能夠交換到后面的單元，排序碼較小的的元素一次就能夠交換到后面的單元，排序碼較小的記錄一次就能夠交換到前面的單元，記錄每次移動(dòng)的記錄一次就能夠交換到前面的單元，記錄每次移動(dòng)的距離較遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。距離較遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。38 65 97 13 27

29、49* 551234567849049pivot快速排序中的一趟劃分算法快速排序中的一趟劃分算法38 27 13 49 97 49* 551234567804659一次劃分一次劃分int Partition(SqList &L,int low,int high) pivotkey = L.rlow.key; while (lowhigh) while (low= pivotkey) high- -; /從后往前尋找比樞軸元素小者從后往前尋找比樞軸元素小者 L.rlow L.rhigh; /比樞軸元素小者交換到前半?yún)^(qū)間比樞軸元素小者交換到前半?yún)^(qū)間 while (lowhigh &

30、 L.rlow.key = pivotkey) low+; /從前往后尋找比樞軸元素大者從前往后尋找比樞軸元素大者 L.rhigh L.rlow; /比樞軸元素大者交換到后半比樞軸元素大者交換到后半 區(qū)間區(qū)間 return low; /返回樞軸元素的位置返回樞軸元素的位置/Partition將交換改為元素的移動(dòng)將交換改為元素的移動(dòng)劃分算法改進(jìn)劃分算法改進(jìn)38 65 97 13 27 49* 55123456784904949ij044938 65 97 13 27 49* 55123456784904949ij0438 65 97 13 27 49 551234567849049pivotij

31、快速排序中的一趟劃分快速排序中的一趟劃分快速排序中的一趟劃分快速排序中的一趟劃分 38 65 97 13 27 49 551234567804949pivotijaj與與pivot比較，比較，aj小則小則ajai快速排序中的一趟劃分快速排序中的一趟劃分 38 65 97 13 27 49 551234567804949pivotij快速排序中的一趟劃分快速排序中的一趟劃分 38 65 97 13 27 49 551234567804949pivotijai與與pivot比較，比較，ai大則大則ai aj；否；否則則i增增1快速排序中的一趟劃分快速排序中的一趟劃分 38 65 97 13 27

32、49 551234567804949pivotijai與與pivot比較，比較，ai大則大則ai aj；否；否則則i增增1快速排序中的一趟劃分快速排序中的一趟劃分 3897 13 27 49 55123456780465949pivotij快速排序中的一趟劃分快速排序中的一趟劃分 3897 13 27 49 55123456780465949pivotijaj與與pivot比較，比較，aj小則小則aj ai; 否則，利用否則，利用j向前掃描向前掃描快速排序中的一趟劃分快速排序中的一趟劃分 3897 13 27 49 55123456780465949pivotijaj與與pivot比較，比較，

33、aj小則小則aj ai; 否則，利用否則，利用j向前掃描向前掃描快速排序中的一趟劃分快速排序中的一趟劃分 3897 13 27 49 55123456780465949pivotijaj與與pivot比較，比較，aj小則小則aj ai; 否則，利用否則，利用j向前掃描向前掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 27 97 1349 55123456780465949pivotijai與與pivot比較，比較，ai大則大則ai aj; 否則，利用否則，利用i向后掃描向后掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 27 97 1349 55123456780465949pivo

34、tij利用利用i向后掃描向后掃描ai與與pivot比較，比較，ai大則大則ai aj;快速排序中的一趟劃分快速排序中的一趟劃分 38 2713 97 49 55123456780465949pivotij利用利用j向前掃描向前掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 2713 97 49 55123456780465949pivotijaj與與pivot比較，比較，aj小則小則aj ai; 否則，利用否則，利用j向前掃描向前掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 27 1397 49 55123456780465949pivotijai與與pivot比較，比較，ai大則大

35、則ai aj; 否則，利用否則，利用i向后掃描向后掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 27 1397 49 55123456780465949pivotij快速排序中的一趟劃分快速排序中的一趟劃分 38 27 1397 49 55123456780465949pivoti ji與與j相等時(shí)，完成一次劃分相等時(shí)，完成一次劃分快速排序中的一趟劃分快速排序中的一趟劃分 38 27 13 49 97 49 551234567804659int Partition(SqList &L,int low,int high) L.r0 = L.rlow; pivotkey = L.r0

36、.key; while (lowhigh) while (low= pivotkey) high-; L.rlow = L.rhigh; while (lowhigh & L.rlow.key = pivotkey) low+; L.rhigh = L.rlow; L.rlow = L.r0; return low;/Partition快速排序快速排序int Partition(SqList &L,int low,int high) . return i; /返回樞軸元素的位置返回樞軸元素的位置/Partitionvoid QSort(SqList &L, int lo

37、w, int high) /對(duì)對(duì)L.rlowL.rhigh的元素進(jìn)行快速排序的元素進(jìn)行快速排序 if (low high) pivotloc = Partition(L,low,high); /一趟劃分一趟劃分 QSort(L,low,pivotloc - 1); QSort(L, pivotloc+1,high); /if /QSort快速排序過程分析快速排序過程分析38 65 97 13 27 49* 551234567849049劃分劃分38 27 13 49 97 49* 550465劃分劃分38 27 1304劃分劃分9765 49* 55劃分劃分13 27 38劃分劃分2713劃分

38、劃分55 49* 65劃分劃分5549*2749*10.3 快速排序分析快速排序分析v以順序表作為存儲(chǔ)結(jié)構(gòu)的快速排序算法q時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(nlognO(nlogn) )n快速排序在最好情形下(左、右子區(qū)間的長度大致相等)，則結(jié)點(diǎn)數(shù)n與二叉樹深度h應(yīng)滿足log2nhlog2n+1，所以總的比較次數(shù)不會(huì)超過(n+1)log2n。因此，快速排序的最好時(shí)間復(fù)雜度應(yīng)為O(nlog2n)。理論上已經(jīng)證明，快速排序的平均時(shí)間復(fù)雜度也為O(nlog2n)。n在最壞情況下(逆序或正序)，時(shí)間復(fù)雜度為 O(n2)q空間復(fù)雜度：空間復(fù)雜度：O(lognO(logn) )n在最壞情況下(逆序或正序)，空間

39、復(fù)雜度為O(n)q不穩(wěn)定的排序方法不穩(wěn)定的排序方法v快速排序不適合對(duì)小規(guī)模的序列進(jìn)行排序10.3 快速排序分析快速排序分析假設(shè)假設(shè)一次劃分所得樞軸位置一次劃分所得樞軸位置 i=k，則對(duì)，則對(duì)n 個(gè)記錄進(jìn)行個(gè)記錄進(jìn)行快排所需時(shí)間為：快排所需時(shí)間為： T(n) = Tpass(n) + T(k-1) + T(n-k)其中其中 Tpass(n)為對(duì)為對(duì) n 個(gè)記錄進(jìn)行一次劃分所需時(shí)間。個(gè)記錄進(jìn)行一次劃分所需時(shí)間。若待排序列中記錄的關(guān)鍵字隨機(jī)分布，則若待排序列中記錄的關(guān)鍵字隨機(jī)分布，則k 取取 1 至至 n 中任一值的可能性相同，中任一值的可能性相同，由此可得快速排序所需時(shí)由此可得快速排序所需時(shí)間的平

40、均值為：間的平均值為：nkavgavgavgknTkTnCnnT1)()1(1)(10)(2)(niavgavgiTnCnnTCCnnTnnnTavg2) 1() 1()(12) 1(1)(nCnnTnnTavg10.3 快速排序方法的改進(jìn)快速排序方法的改進(jìn)v樞軸元素的選取q三者取中q隨機(jī)選擇v劃分的過程中進(jìn)行“起泡”操作v當(dāng)劃分出的子序列長度小于某個(gè)值時(shí)，不再遞歸，而進(jìn)行直接插入排序v快速排序算法被認(rèn)為是內(nèi)部排序方法中最好的一種13 27 38 49 49* 55 650497123456789最壞情況下的快速排序最壞情況下的快速排序13 27 38 49 49* 55 65049713 2

41、7 38 49 49* 55 65 9727 38 49 49* 55 65 9738 49 49* 55 65 9749 49* 55 65 9749* 55 65 9755 65 9765 9797最好情況下的快速排序最好情況下的快速排序04 65 97 13 55 49* 381234567849279劃分劃分04 38 13 49 55 49* 972765劃分劃分13 043827劃分劃分6549* 55 97劃分劃分3804 13劃分劃分49*976565劃分劃分0410.4 選擇排序選擇排序1. 簡單選擇排序q簡單選擇排序的基本思想是：第一趟在n個(gè)記錄中選取最小記錄作為有序序列的

42、第一個(gè)記錄，第二趟在n-1個(gè)記錄中選取最小記錄作為有序序列的第二個(gè)記錄，第i趟在n-i+1個(gè)記錄中選取最小的記錄作為有序序列多中的第i個(gè)記錄。簡單選擇排序過程示例簡單選擇排序過程示例初始關(guān)鍵字序列3412492831525149*123456780i=11234492831525149*i=21228493431525149*i=31228313449525149*i=41228313449525149*i=51228313449525149*i=6122831344949*5152i=7122831344949*515210.4 簡單選擇排序算法簡單選擇排序算法v以順序表作為存儲(chǔ)結(jié)構(gòu)的簡單選

43、擇排序算法void SelectSort(SqList &L) /對(duì)順序表作簡單選擇排序?qū)樞虮碜骱唵芜x擇排序 for(i = 1; i L.ength; i+) for(k = i, j =i; k = L.length; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; /for / SelectSortv分析簡單選擇排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)分析簡單選擇排序算法中關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù) for(i = 1; i L.length; i+) for(k = i, j =i; k = L.lengt

44、h; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; /for /if for(k = i+1, j = i; k = L.length; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; 在逆序情況下在逆序情況下元素的比較次數(shù)元素的比較次數(shù): : n(n-1)/2元素的元素的移動(dòng)次數(shù)為：移動(dòng)次數(shù)為：3(n-1)在正序情況下在正序情況下元素的比較次數(shù)元素的比較次數(shù): : n(n-1)/2元素的元素的移動(dòng)次數(shù)為：移動(dòng)次數(shù)為：010.4 簡單選擇排序算法分析簡單選擇排序

45、算法分析v以順序表作為存儲(chǔ)結(jié)構(gòu)的簡單選擇排序算法q時(shí)間復(fù)雜度：O(n2)n在n個(gè)關(guān)鍵字中選出最小者，需要n-1次比較，繼續(xù)在剩余的n-1個(gè)元素中選出次小者需要n-2次比較，依此類推。q空間復(fù)雜度：O(1)n只需要 1 個(gè)輔助單元進(jìn)行交換q不穩(wěn)定的排序方法q適用情況n元素?cái)?shù)目少的情況n無需完全排序的情況，比如，選出第i小的元素v對(duì)簡單選擇排序過程進(jìn)行改進(jìn)：利用前面已經(jīng)進(jìn)行過的對(duì)簡單選擇排序過程進(jìn)行改進(jìn)：利用前面已經(jīng)進(jìn)行過的比較結(jié)果比較結(jié)果10.4 選擇排序選擇排序2. 樹形選擇排序(Tree Selection Sort)q又稱錦標(biāo)賽排序(Tournament Sort):首先對(duì)n個(gè)記錄的關(guān)鍵字

46、兩兩進(jìn)行比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。整個(gè)過程可用一個(gè)含有n個(gè)葉結(jié)點(diǎn)的二叉樹表示。q例如3412492831525149*12283149*123112341212 492831525149*10.4 選擇排序選擇排序q選出最小記錄后，將樹中的該最小記錄修改為，然后從該葉子結(jié)點(diǎn)所在子樹開始，修改到達(dá)樹根的路徑上的結(jié)點(diǎn)34 492831525149*34 283149*28312834 492831525149*10.4 選擇排序選擇排序q以后每選出一個(gè)小元素，都只需進(jìn)行(logn)次比較34 4931525149*34 493149*3431

47、3134 492831525149*10.4 選擇排序選擇排序2. 樹形選擇排序的缺陷q需要較多的輔助空間q存在與“”進(jìn)行比較的冗余比較34 4931525149*34 493149*34313110.4 選擇排序選擇排序3. 3. 堆排序堆排序(Heap Sort)(Heap Sort)q只需要一個(gè)元素的輔助空間q算法的時(shí)間復(fù)雜度為O(nlogn)v堆的定義堆的定義對(duì)于對(duì)于n個(gè)元素的序列個(gè)元素的序列k1,k2,.,kn，當(dāng)且僅當(dāng)滿足當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆。以下關(guān)系時(shí)，稱之為堆。 1i2ii2ikkkk 1i2ii2ikkkk2n,.,2,1i或或10.4 堆排序堆排序v堆(完全二叉

48、樹)96833811279(a) 大頂堆大頂堆(max heap)123685472430(b) 小頂堆小頂堆(min heap)5391 1i2ii2ikkkk 1i2ii2ikkkk10.4 堆排序堆排序3. 堆排序(Heap Sort)q對(duì)一組待排序記錄的關(guān)鍵字，首先把它們按堆的定義建成小(大)頂堆，然后輸出堆頂?shù)淖钚?大)關(guān)鍵字所代表的記錄，再對(duì)剩余的關(guān)鍵字建堆，以便得到次小(大)的關(guān)鍵字，如此反復(fù)進(jìn)行，直到全部關(guān)鍵字排成有序序列為止。v 實(shí)現(xiàn)堆排序需要解決兩個(gè)問題：實(shí)現(xiàn)堆排序需要解決兩個(gè)問題： (1) (1) 如何建堆？如何建堆？ (2) (2) 輸出堆頂元素后，如何將剩余元素重新調(diào)

49、整為輸出堆頂元素后，如何將剩余元素重新調(diào)整為一個(gè)新堆？一個(gè)新堆？10.4 堆排序過程示例堆排序過程示例v下面是一個(gè)小頂堆，輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆的方法是：從樹根開始，若以某結(jié)點(diǎn)為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向12368547243053919136854724305312交換堆頂元素與序列末交換堆頂元素與序列末端的元素端的元素比較比較比較比較-交換交換10.4 堆排序過程示例堆排序過程示例(續(xù)續(xù))v輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆的方法是：從樹根開始，若以某結(jié)點(diǎn)為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的

50、子樹推向葉子方向2436854730915312繼續(xù)向葉子方向調(diào)整繼續(xù)向葉子方向調(diào)整2436854791305312比較比較比較比較交換交換10.4 堆排序過程示例堆排序過程示例(續(xù)續(xù))v一旦已調(diào)整為堆，則輸出堆頂元素，重復(fù)將剩余元素重新調(diào)整為一個(gè)新堆。24368547309153125336854730912412交換堆頂元素與序列末交換堆頂元素與序列末端的元素端的元素10.4 堆排序過程示例堆排序過程示例(續(xù)續(xù))v輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆3036854753912412調(diào)整成堆調(diào)整成堆533685473091241210.4 堆排序過程分析堆排序過程分析v輸出堆頂元素后

51、，將剩余元素重新調(diào)整為一個(gè)新堆9136854753302412反復(fù)將堆頂元素與序列反復(fù)將堆頂元素與序列末端的元素的交換，并末端的元素的交換，并重新調(diào)整成堆。重新調(diào)整成堆。9185473653302412q調(diào)整堆元素調(diào)整堆元素( (篩選篩選) ) 對(duì)于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小對(duì)于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小( (大大) )頂頂堆，從而得到最小堆，從而得到最小( (大大) )關(guān)鍵字。關(guān)鍵字。 在輸出堆頂元素之后，用堆中最后一個(gè)元素替代在輸出堆頂元素之后，用堆中最后一個(gè)元素替代之。此時(shí)由于以之。此時(shí)由于以K K2 2和和K K3 3為根的子樹仍具有堆的特性，為根的子樹仍具有堆

52、的特性，因此只需自上而下進(jìn)行調(diào)整即可。因此只需自上而下進(jìn)行調(diào)整即可。 調(diào)整過程為：調(diào)整過程為：首先令首先令K K1 1的兩個(gè)子樹根進(jìn)行比較，令其中較的兩個(gè)子樹根進(jìn)行比較，令其中較小小( (大大) )者與者與K K1 1相比較，將最小相比較，將最小( (大大) )元素交換至元素交換至K K1 1，使得，使得K K1 1、K K2 2和和K K3 3成為堆。由于交換后破壞了子樹的堆性質(zhì)，則需再次進(jìn)行成為堆。由于交換后破壞了子樹的堆性質(zhì)，則需再次進(jìn)行與上述過程類似的調(diào)整，直至進(jìn)行到最下層的葉結(jié)點(diǎn)為止。與上述過程類似的調(diào)整，直至進(jìn)行到最下層的葉結(jié)點(diǎn)為止。調(diào)整后即得到一個(gè)有調(diào)整后即得到一個(gè)有n-1n-1

53、個(gè)元素的新堆，從而得到次小關(guān)鍵字。個(gè)元素的新堆，從而得到次小關(guān)鍵字。10.4 堆排序過程分析堆排序過程分析(續(xù)續(xù))v輸出堆頂元素后，將剩余元素重新調(diào)整為一個(gè)新堆q調(diào)整堆元素調(diào)整堆元素( (篩選篩選) ) 對(duì)于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小對(duì)于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小( (大大) )頂堆，從而得頂堆，從而得到最小到最小( (大大) )關(guān)鍵字。關(guān)鍵字。 在輸出堆頂元素之后，用堆中最后一個(gè)元素替代之。此時(shí)由于以在輸出堆頂元素之后，用堆中最后一個(gè)元素替代之。此時(shí)由于以K K2 2和和K K3 3為根的子樹仍具有堆的特性，因此只需自上而下進(jìn)行調(diào)整即可。為根的子樹仍具有堆的特性，因此

54、只需自上而下進(jìn)行調(diào)整即可。 首先令首先令K K1 1將的兩個(gè)子樹根進(jìn)行比較，令其中較小將的兩個(gè)子樹根進(jìn)行比較，令其中較小( (大大) )者與者與K K1 1相比較，相比較，將最小將最小( (大大) )元素交換至元素交換至K K1 1，使得，使得K K1 1、K K2 2和和K K3 3成為堆。由于交換后破壞了右成為堆。由于交換后破壞了右子樹的堆，則需再次進(jìn)行與上述類似的調(diào)整，直至進(jìn)行到最下層的葉結(jié)點(diǎn)。子樹的堆，則需再次進(jìn)行與上述類似的調(diào)整，直至進(jìn)行到最下層的葉結(jié)點(diǎn)。調(diào)整后即得到一個(gè)有調(diào)整后即得到一個(gè)有n-1n-1個(gè)元素的新堆，從而得到次小關(guān)鍵字。個(gè)元素的新堆，從而得到次小關(guān)鍵字。重復(fù)上述過程，

55、將堆頂元素與堆中最后一個(gè)元素交換且調(diào)整，重復(fù)上述過程，將堆頂元素與堆中最后一個(gè)元素交換且調(diào)整，又得到了有又得到了有n-2n-2個(gè)元素的新堆。為節(jié)省存貯開銷，可以把輸出個(gè)元素的新堆。為節(jié)省存貯開銷，可以把輸出的最小的最小( (大大) )關(guān)鍵字放在關(guān)鍵字放在K Kn n的位置上，把第二次輸出的次小的位置上，把第二次輸出的次小( (大大) )關(guān)鍵字存放在關(guān)鍵字存放在K Kn-1n-1的位置上的位置上，直至最大，直至最大( (小小) )關(guān)鍵字放在關(guān)鍵字放在K K1 1的位置上。的位置上。如此，我們已經(jīng)可以在初始情況為堆的情況下完成排序，那么，如此，我們已經(jīng)可以在初始情況為堆的情況下完成排序，那么，如何

56、建立起初始堆呢？如何建立起初始堆呢？建初始小頂堆47369112533024851236854724305391v元素序列為：47,36,53,91,12,30,24,85建立小頂堆建立小頂堆建初始堆4736911253302485(a)4736851253302491(b)v從最后一個(gè)具有葉子的結(jié)點(diǎn)(編號(hào)n/2)開始建子堆，依次考查結(jié)點(diǎn)n/2-1,n/2-2,.，1等是否為堆，若否則調(diào)整為堆建初始堆4736851224305391v從最后一個(gè)具有葉子的結(jié)點(diǎn)(編號(hào)n/2)開始建子堆，依次考查結(jié)點(diǎn)n/2-1,n/2-2,.，1等是否為堆，若否則調(diào)整為堆(C)4712853624305391(d)

57、建初始堆1247853624305391v從最后一個(gè)具有葉子的結(jié)點(diǎn)(編號(hào)n/2)開始建子堆，依次考查結(jié)點(diǎn)n/2-1,n/2-2,.，1等是否為堆，若否則調(diào)整為堆(e)1236854724305391(f)v當(dāng)以下標(biāo)當(dāng)以下標(biāo)1 1為根的完全二叉樹為堆時(shí)，初始堆已建立為根的完全二叉樹為堆時(shí)，初始堆已建立v也可以從空堆開始建初始堆也可以從空堆開始建初始堆10.4 堆排序堆排序v1964年弗洛伊德（Floyd）提出了篩選法建立初始堆，具體方法是：v將待排序的關(guān)鍵字分放到一棵完全二叉樹的各個(gè)結(jié)點(diǎn)中（此時(shí)完全二叉樹并不一定具備堆的特性），顯然，所有in/2的結(jié)點(diǎn)Ki都沒有子結(jié)點(diǎn)，以這樣的Ki為根的子樹已經(jīng)

58、是堆，因此初始建堆可從完全二叉樹的第i個(gè)結(jié)點(diǎn)Ki開始(i=n/2)。通過調(diào)整，逐步使以Kn/2，Kn/2-1，Kn/2-2，為根的子樹滿足堆的定義，直至進(jìn)行到以K1為根的樹排成堆為止。v在對(duì)Ki為根的子樹建堆時(shí)，其子樹已經(jīng)為堆，要使得以Ki為根的完全二叉樹為堆，則可能要調(diào)整父、子結(jié)點(diǎn)的位置，如此下一層已建成堆的子樹可能不再滿足堆的定義，則需繼續(xù)進(jìn)行調(diào)整，如此一次次遞推下去，最多可能一直延伸到樹葉。這種方法就像過篩子一樣，把最小(大)的關(guān)鍵字一層一層地篩選出來，最后輸出堆頂?shù)淖钚?大)關(guān)鍵字。10.4 堆排序算法堆排序算法(篩選算法篩選算法)vtypedef SqList HeapType; /

59、堆采用順序存儲(chǔ)結(jié)構(gòu)void HeapAdjust (HeapType &H, int s, int m) / HeapAdjust rc = H.rs; for ( j=2*s; j=m; j*=2) /沿沿key較小的孩子結(jié)點(diǎn)向下篩選較小的孩子結(jié)點(diǎn)向下篩選 if ( j H.rj+l.key) + j; /j為為key較小的記錄的下標(biāo)較小的記錄的下標(biāo) if (rc. Key 0; -i) / 把把H建成大頂堆建成大頂堆 HeapAdjust ( H, i, H. length); for ( i = H. length; i 1; -i) H.r1 H.ri; /堆頂記錄和當(dāng)前未排子

60、序列中最后一個(gè)記錄相交換堆頂記錄和當(dāng)前未排子序列中最后一個(gè)記錄相交換 HeapAdjust (H, 1, i - 1); /將將H. rl . i - 1 重新調(diào)整為大頂堆重新調(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.r1H.ri; /堆頂記錄和當(dāng)前未排子序列中最后一個(gè)記錄相交換堆頂記錄和當(dāng)前未排子序列中最后一個(gè)記錄相交換 HeapAdjust (H, 1, i - 1); /將將H. rl . i - 1 重新調(diào)整為大重新調(diào)整為大/小頂堆小頂堆 473691125330248510.4