第十章內部排序

1、第十章第十章 內部排序內部排序10.1 排序的基本概念排序的基本概念n排序(sorting)q將一個數據元素的任意序列重新排列成一個按關鍵字有序的序列。q假設n個元素的序列R1,R2,.,Rn，相應的關鍵字序列為k1, k2,., kn，確定1,2,.,n的一種排列p1,p2,.,pn ，使相應的關鍵字滿足非遞減(或非遞增)關系kp1,kp2,.,kpn，從而得到一個按關鍵字有序的序列。這樣的一個操作過程就是排序。n穩(wěn)定的排序方法穩(wěn)定的排序方法q若若kikj，且在排序前的序列中，且在排序前的序列中Ri領先于領先于Rj，排序，排序后后Ri仍領先于仍領先于Rj，則稱所用的排序方法是穩(wěn)定的；反，則稱

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

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

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

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

6、錄有序子序列記錄有序子序列，逐步增加記錄，逐步增加記錄有序序列的長度。有序序列的長度。10.2 插入排序插入排序1. 直接插入排序基本思想是：n個待排序的元素由一個有序表和一個無序表組成，開始時有序表中只包含一個元素。排序過程中，每次從無序表中取出第一個元素，將其插入到有序表中的適當位置，使有序表的長度不斷加長，完成排序過程。有序序列有序序列R1.i-1Ri無序序列無序序列 Ri.n有序序列有序序列R1.i無序序列無序序列 Ri+1.n10.2 直接插入排序過程示例直接插入排序過程示例初始關鍵字序列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數據結構定義#define MAXSIZE 20typedef int Keytype; / 定義關鍵字類型為整型typedef struct KeyType key; / 關鍵字項 InfoType otherinfo; / 其他數據項RedType; / 記錄類型typed

8、ef struct RedType rMAXSIZE+1; / r0閑置或用作哨兵 int length; / 順序表長度SqList; / 順序表類型10.2 直接插入排序算法直接插入排序算法v以順序表作為存儲結構的直接插入排序算法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分析直接插入排序算法中關鍵字的比較次數和記錄移動次數分析直接插入排序算法中關鍵字的比較次數和記錄移動次數 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最好情況下最好情況下( (正序正序) )元素的比較次數為元素的比較次數為: : n - 1 元素的移動次數為元素的移動次數為: :0最壞情況下最壞情況下(逆序逆序)元素的比較次數元素的比較次數: : (n+2)(n-1)/2元素的元素的移動次數為：移動次數為： (n+4)(n-1)/2 10.2 直接插入排序算法直接插入排序算法v以順序表作為存儲結構的直接插入排序算法以順序表作為存儲結構的直接插入排序算法q時間復雜度：時間復雜度：O(nO(n2 2) )n在最好情況下在最好情況下( (正序正序) )，元素的移

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

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

13、低半區(qū)中插入位置在低半區(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)也稱為縮小增量排序，也稱為縮小增量排序，其改進原理主要基于以下兩點:q元素基本有序時，直接插入排序的時間復雜度接近于O(n)q元素數目n較少時，直接插入排序的效率較高v希爾排序的算法思想希爾排序的算法思想先將整個待排序元素序列分割成若干個子序列（由先將整個待排序元素序列分割成若干個子序列（由相隔某個相隔某個

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

15、排序結果：第三趟排序結果：0413273849*495565123456787697910132749*5504493865977610.2 希爾排序算法希爾排序算法void ShellInsert(SqList &L,int dk) /對順序表對順序表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; /尋找插入位置時記錄后移尋找插入位置時記錄后移 L.rj+dk = L.r0; /插入插入 /if10.2 希爾排序算法希爾排序算

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

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

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

20、4949*657697第四趟排序后：第四趟排序后：1327384949*657697第五趟排序后：第五趟排序后：1327384949*657697第六趟排序后：第六趟排序后：10.3 起泡排序算法起泡排序算法v以順序表作為存儲結構的起泡排序算法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分析起泡排序算法中關鍵字的比較次數和記錄移動次數分析起泡排序算法中關鍵字的比較次數和記錄移動次數 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最好情況下，元素的比較次數為最好情況下，元素的比較次數為: n - 1 最壞情況下，比較次數為最壞情況下，比較次數為: n(n-1)/2最好情況下，元素的移動次數為最好情況下，元素的移動次數為:0:0最壞情況下，交換次數為：最壞情況下，交換次數為：n(n-1)/2n(n-1)/210.3 起泡排序算法起泡排序算法v以順序表作為存儲結構的起泡排序算法q時間復雜度：O(n2)n在最好情況下(正序)，元素的交換次數為0，比較次數為n 1；n在最壞情況下(逆序)，元素的交換次數為n(n-1)/2，比

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

24、或等于基準元素的關鍵字，右子序列的關鍵字則大于基準元素的關鍵字，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序。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當當i與與j相等時，樞軸元素確定了位置相等時，樞軸元素確定了位置i，結束本次劃分，結束本次劃分 快速排序是對冒泡排序的一種改進方法，算法中元快速排序是對冒泡排序的一種改進方法，算法中元素的比較和交換是從兩端向中間進行的，排序碼較大素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面的單元，排序碼較小的的元素一次就能夠交換到后面的單元，排序碼較小的記錄一次就能夠交換到前面的單元，記錄每次移動的記錄一次就能夠交換到前面的單元，記錄每次移動的距離較遠，因而總的比較和移動次數較少。距離較遠，因而總的比較和移動次數較少。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; /比樞軸元素小者交換到前半區(qū)間比樞軸元素小者交換到前半區(qū)間 while (lowhigh &

30、 L.rlow.key = pivotkey) low+; /從前往后尋找比樞軸元素大者從前往后尋找比樞軸元素大者 L.rhigh L.rlow; /比樞軸元素大者交換到后半比樞軸元素大者交換到后半 區(qū)間區(qū)間 return low; /返回樞軸元素的位置返回樞軸元素的位置/Partition將交換改為元素的移動將交換改為元素的移動劃分算法改進劃分算法改進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相等時，完成一次劃分相等時，完成一次劃分快速排序中的一趟劃分快速排序中的一趟劃分 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) /對對L.rlowL.rhigh的元素進行快速排序的元素進行快速排序 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以順序表作為存儲結構的快速排序算法q時間復雜度：時間復雜度：O(nlognO(nlogn) )n快速排序在最好情形下(左、右子區(qū)間的長度大致相等)，則結點數n與二叉樹深度h應滿足log2nhlog2n+1，所以總的比較次數不會超過(n+1)log2n。因此，快速排序的最好時間復雜度應為O(nlog2n)。理論上已經證明，快速排序的平均時間復雜度也為O(nlog2n)。n在最壞情況下(逆序或正序)，時間復雜度為 O(n2)q空間復雜度：空間復雜度：O(lognO(logn) )n在最壞情況下(逆序或正序)，空間

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

40、均值為：間的平均值為：nkavgavgavgknTkTnCnnT1)()1(1)(10)(2)(niavgavgiTnCnnTCCnnTnnnTavg2) 1() 1()(12) 1(1)(nCnnTnnTavg10.3 快速排序方法的改進快速排序方法的改進v樞軸元素的選取q三者取中q隨機選擇v劃分的過程中進行“起泡”操作v當劃分出的子序列長度小于某個值時，不再遞歸，而進行直接插入排序v快速排序算法被認為是內部排序方法中最好的一種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個記錄中選取最小記錄作為有序序列的

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

43、擇排序算法void SelectSort(SqList &L) /對順序表作簡單選擇排序對順序表作簡單選擇排序 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分析簡單選擇排序算法中關鍵字的比較次數和記錄移動次數分析簡單選擇排序算法中關鍵字的比較次數和記錄移動次數 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; 在逆序情況下在逆序情況下元素的比較次數元素的比較次數: : n(n-1)/2元素的元素的移動次數為：移動次數為：3(n-1)在正序情況下在正序情況下元素的比較次數元素的比較次數: : n(n-1)/2元素的元素的移動次數為：移動次數為：010.4 簡單選擇排序算法分析簡單選擇排序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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