計算機數(shù)據(jù)結(jié)構(gòu)第十章排序

1、第十章第十章 排序排序q什么是排序？什么是排序？排序是計算機內(nèi)經(jīng)常進行的一種操作，其排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組目的是將一組“無序無序”的記錄序列調(diào)整為的記錄序列調(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, 9710.1 排序排序 一般情況下，假設(shè)含n個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系 ：

2、Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作操作稱作排序排序。n穩(wěn)定的排序方法穩(wěn)定的排序方法若若kikj，且排序前的序列中，且排序前的序列中Ri領(lǐng)先于領(lǐng)先于Rj，排序，排序后后Ri仍領(lǐng)先于仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中的；反之，若可能使排序后的序列中Rj仍領(lǐng)先仍領(lǐng)先于于Ri ，則稱所用的排序方法是不穩(wěn)定的。，則稱所用的排序方法是不穩(wěn)定的。n內(nèi)部排序和外部排序內(nèi)部排序和外部排序待排序的記錄存放再計算機的內(nèi)存中所進行的待排序的記錄存放再計算機的內(nèi)存中所進行的排序操作稱為內(nèi)部排序。排序操

3、作稱為內(nèi)部排序。待排序的記錄數(shù)量很大，以致內(nèi)存一次不能容待排序的記錄數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中需要訪問外存的排納全部記錄，在排序過程中需要訪問外存的排序過程稱為外部排序。序過程稱為外部排序。n正序與逆序正序與逆序若有序表是按排序碼升序排列的，則稱為升序表或正若有序表是按排序碼升序排列的，則稱為升序表或正序表，否則稱為降序表或逆序表。不失普遍性，我們序表，否則稱為降序表或逆序表。不失普遍性，我們一般只討論正序表。一般只討論正序表。n排序方法度量排序方法度量排序過程主要是進行記錄的關(guān)鍵字比較和記錄的移動。排序過程主要是進行記錄的關(guān)鍵字比較和記錄的移動。因此排序的時間復(fù)雜性

4、可以算法執(zhí)行中的數(shù)據(jù)比較次因此排序的時間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當(dāng)一種排序方法使排序過數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數(shù)越少，程在最壞或平均情況下所進行的比較和移動次數(shù)越少，則認(rèn)為該方法的時間復(fù)雜性就越好。則認(rèn)為該方法的時間復(fù)雜性就越好。針對一種排序方法，不僅要分析它的時間復(fù)雜性，而針對一種排序方法，不僅要分析它的時間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。常見排序的方法常見排序的方法內(nèi)部排序內(nèi)部排序外部排序外部排序 插入排序（直插排序、二分排序、希爾排序

5、）插入排序（直插排序、二分排序、希爾排序） 交換排序（冒泡排序、快速排序）交換排序（冒泡排序、快速排序） 選擇排序選擇排序 （直選排序、樹型排序、堆排序）（直選排序、樹型排序、堆排序） 歸并排序（二路歸并排序、多路歸并排序）歸并排序（二路歸并排序、多路歸并排序） 分配排序分配排序 （多關(guān)鍵字排序、基數(shù)排序）（多關(guān)鍵字排序、基數(shù)排序） 多路平衡歸并排序多路平衡歸并排序 置換選擇排序置換選擇排序 最佳歸并樹最佳歸并樹排序排序10.2 插入排序插入排序q直接插入排序原理直接插入排序原理直接插入排序直接插入排序(Straight Insertion Sorting)(Straight Insertio

6、n Sorting)的基本思想是：把的基本思想是：把n n個待排序的元素看作由兩個待排序的元素看作由兩部分組成：一個有序表和一個無序表。開始時部分組成：一個有序表和一個無序表。開始時有序表中只包含一個元素，無序表中包含有有序表中只包含一個元素，無序表中包含有n-n-1 1個元素。排序過程中，每次從無序表中取出個元素。排序過程中，每次從無序表中取出第一個元素，令其關(guān)鍵字依次與有序表元素的第一個元素，令其關(guān)鍵字依次與有序表元素的關(guān)鍵字進行比較，將其插入到有序表中的適當(dāng)關(guān)鍵字進行比較，將其插入到有序表中的適當(dāng)位置，使有序表的長度不斷加長，完成排序過位置，使有序表的長度不斷加長，完成排序過程。程。q直

7、接插入排序過程示例直接插入排序過程示例初始關(guān)鍵字序列初始關(guān)鍵字序列3412492831525149*123456780監(jiān)視哨監(jiān)視哨i=21234492831525149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=61228313449525149*52i=71228313449515249*51i=8122831344949*515249*q直接插入排序算法直接插入排序算法v數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義#define MAXSIZE 20typedef int Keytype; / 定義關(guān)鍵字類型為整

8、型定義關(guān)鍵字類型為整型typedef struct KeyType key; / 關(guān)鍵字項關(guān)鍵字項 InfoType otherinfo; / 其他數(shù)據(jù)項其他數(shù)據(jù)項RedType; / 記錄類型記錄類型typedef struct RedType rMAXSIZE+1; / r0閑置或用作哨兵閑置或用作哨兵 int length; / 順序表長度順序表長度SqList; / 順序表類型順序表類型v以順序表作為存儲結(jié)構(gòu)的直接插入排序算法以順序表作為存儲結(jié)構(gòu)的直接插入排序算法void InsertSort(SqList &L) for(i = 2; i = L.ength; i+) if

9、(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 / InsertSortv分析直接插入排序算法中關(guān)鍵字的比較次數(shù)和記錄移動次數(shù)分析直接插入排序算法中關(guān)鍵字的比較次數(shù)和記錄移動次數(shù) 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;

10、 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.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if最好情況下最好情況下( (正序正序) )元素的比較次數(shù)為元素的比較次數(shù)為: : n - 1 元素的移動次數(shù)為元素的移動次數(shù)為: :0最壞情況下最壞情況下(逆序逆序)元素的比較次數(shù)元素的比較次數(shù): : (n+2)(n-1)/2元素的元素的移動次數(shù)為：移動次數(shù)為： (n+4)(n

11、-1)/2 q直接插入排序算法時間復(fù)雜度直接插入排序算法時間復(fù)雜度v以順序表作為存儲結(jié)構(gòu)的直接插入排序算法以順序表作為存儲結(jié)構(gòu)的直接插入排序算法時間復(fù)雜度：時間復(fù)雜度：O(n2)n在在最好情況下最好情況下( (正序正序) )，元素的移動次數(shù)為，元素的移動次數(shù)為0 0，比較次數(shù)為比較次數(shù)為n 1；n在最壞情況下在最壞情況下( (逆序逆序) )，元素的移動次數(shù)為，元素的移動次數(shù)為(n+4)(n-1)/2，比較，比較次數(shù)為次數(shù)為 (n+2)(n-1)/2空間復(fù)雜度：空間復(fù)雜度：O(1)n只需要只需要 1 個輔助單元個輔助單元穩(wěn)定的排序方法穩(wěn)定的排序方法適用情況適用情況n元素數(shù)目少，或者元素的初始序列

12、基本有序元素數(shù)目少，或者元素的初始序列基本有序10.2.2. 其他插入排序其他插入排序在尋找插入位置時采用二分查找，則稱為折半插入排在尋找插入位置時采用二分查找，則稱為折半插入排序，序，2-2-路插入排序在此基礎(chǔ)上增加了輔助空間、減少路插入排序在此基礎(chǔ)上增加了輔助空間、減少了記錄的移動。了記錄的移動。10.2.3 希爾排序希爾排序希爾排序希爾排序(Shells Sort)也稱為縮小增量排序，其改進原理也稱為縮小增量排序，其改進原理主要基于以下兩點主要基于以下兩點元素基本有序時，直接插入排序的時間復(fù)雜度接近于元素基本有序時，直接插入排序的時間復(fù)雜度接近于O(n)O(n)元素數(shù)目元素數(shù)目n n較少

13、時，直接插入排序的效率較高較少時，直接插入排序的效率較高v希爾排序的算法思想希爾排序的算法思想先將整個待排序元素序列分割成若干個子序列（由相先將整個待排序元素序列分割成若干個子序列（由相隔某個隔某個“增量增量”的元素組成的），分別進行直接插入的元素組成的），分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠?。┡判?，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。時，再對全體元素進行一次直接插入排序。10.2 希爾排序過程示例希爾排序過程示例初始關(guān)鍵字序列：初始關(guān)鍵字序列：4938659776132749*123456785504910增量增量d51327

14、49*5504493865123456789776910第一趟排序結(jié)果：第一趟排序結(jié)果：增量增量d3第二趟排序結(jié)果：第二趟排序結(jié)果：130449*3827495565123456789776910增量增量d1第三趟排序結(jié)果：第三趟排序結(jié)果：0413273849*495565123456787697910132749*55044938659776q希爾排序算法希爾排序算法void ShellInsert(SqList &L,int dk) /對順序表對順序表L作一趟希爾排序作一趟希爾排序 for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.ke

15、y) 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 /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.ke

16、y L.rj.key; j -= dk) L.rj+dk = L.rj; /尋找插入位置時記錄后移尋找插入位置時記錄后移 L.rj+dk = L.r0; /插入插入 /ifvoid 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); /一趟增量為一趟增量為

17、dltak的希爾排序的希爾排序 /ShellInsertSortv希爾排序的分析是一個復(fù)雜問題，增量序列的設(shè)置是關(guān)鍵，希爾排序的分析是一個復(fù)雜問題，增量序列的設(shè)置是關(guān)鍵，尚沒有正式的依據(jù)說明如何設(shè)置最佳的增量序列，大量的實尚沒有正式的依據(jù)說明如何設(shè)置最佳的增量序列，大量的實驗表明希爾排序所需的比較和移動次數(shù)可達(dá)到驗表明希爾排序所需的比較和移動次數(shù)可達(dá)到n1.3v希爾排序的空間復(fù)雜度為希爾排序的空間復(fù)雜度為O(1)，是，是不穩(wěn)定不穩(wěn)定的排序方法的排序方法10.3 交換排序交換排序10.3.1 起泡排序起泡排序起泡排序起泡排序(Bubble Sorting)(Bubble Sorting)的基本思

18、想是：將的基本思想是：將相鄰位置的關(guān)鍵字進行比較，若為逆序則交換相鄰位置的關(guān)鍵字進行比較，若為逆序則交換之。之。第第i i趟排序過程為從趟排序過程為從L.r1L.r1至至L.rn-i+1L.rn-i+1依次依次比較相鄰兩個記錄的關(guān)鍵字，并在比較相鄰兩個記錄的關(guān)鍵字，并在“逆序逆序”時時交換相鄰記錄，其結(jié)果是這交換相鄰記錄，其結(jié)果是這n-i+1n-i+1個記錄中關(guān)個記錄中關(guān)鍵字最大的記錄被交換到第鍵字最大的記錄被交換到第n-i+1n-i+1的位置上。的位置上。整個排序過程終止的條件是整個排序過程終止的條件是“在一趟排序過程在一趟排序過程中沒有進行過交換記錄的操作中沒有進行過交換記錄的操作”q起泡

19、排序過程示例起泡排序過程示例初始關(guān)鍵字序列：初始關(guān)鍵字序列：4938659776132749*1234567838496576132749*97第一趟排序后：第一趟排序后：384965132749*7697第二趟排序后：第二趟排序后：3849132749*657697第三趟排序后：第三趟排序后：3813274949*657697第四趟排序后：第四趟排序后：1327384949*657697第五趟排序后：第五趟排序后：1327384949*657697第六趟排序后：第六趟排序后：q起泡排序算法起泡排序算法v以順序表作為存儲結(jié)構(gòu)的起泡排序算法以順序表作為存儲結(jié)構(gòu)的起泡排序算法void Bubble

20、Sort(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 / BubbleSortv分析起泡排序算法中關(guān)鍵字的比較次數(shù)和記錄移動次數(shù)分析起泡排序算法中關(guān)鍵字的比較次數(shù)和記錄移動次數(shù) for(i = 1, change = TRUE; i L.length & change; +i) if (L.ri.ke

21、y 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.rj; L.rj = L.rj+1; L.rj+1 = L.r0; change =TRUE; /if最好情況下，元素的比較次數(shù)為最好情況下，元素的比較次數(shù)為: : n - 1 最壞情況下，交換次數(shù)為最壞情況下，交換次數(shù)為: : n(n-1)/2最好情況下，元素的

22、移動次數(shù)為最好情況下，元素的移動次數(shù)為: :0最壞情況下，交換次數(shù)為：最壞情況下，交換次數(shù)為：n(n-1)/2q起泡排序算法分析起泡排序算法分析v以順序表作為存儲結(jié)構(gòu)的起泡排序算法以順序表作為存儲結(jié)構(gòu)的起泡排序算法時間復(fù)雜度：時間復(fù)雜度：O(n2)n在在最好情況下最好情況下( (正序正序) )，元素的交換次數(shù)為，元素的交換次數(shù)為0 0，比較次數(shù)為比較次數(shù)為n 1；n在最壞情況下在最壞情況下( (逆序逆序) )，元素的交換次數(shù)為，元素的交換次數(shù)為n(n-1)/2，比較次數(shù)，比較次數(shù)為為 (n+2)(n-1)/2空間復(fù)雜度：空間復(fù)雜度：O(1)n只需要只需要 1 個輔助單元進行交換個輔助單元進行交

23、換穩(wěn)定的排序方法穩(wěn)定的排序方法適用情況適用情況n元素數(shù)目少，或者元素的初始序列基本有序元素數(shù)目少，或者元素的初始序列基本有序10.3.2. 快速排序快速排序快速排序快速排序(Quick Sorting)(Quick Sorting)是迄今為止所有內(nèi)是迄今為止所有內(nèi)排序算法中速度排序算法中速度最快最快的一種。的一種。它的基本思想是：它的基本思想是：任取待排序序列中的某個元任取待排序序列中的某個元素作為基準(zhǔn)（一般取第一個元素），通過一趟素作為基準(zhǔn)（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子排序，將待排元素分為左右兩個子序列，左子序列元素的關(guān)鍵字均小于或等于基準(zhǔn)元素的關(guān)序列

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

25、，i加加1快速排序中的一趟劃分快速排序中的一趟劃分38 65 97 13 27 49* 55123456780449949pivotijL.ri與與pivot比較，比較，L.ri大則與大則與L.rj交換；否則交換；否則i增增1快速排序中的一趟劃分快速排序中的一趟劃分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* 551234567804

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

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

28、8 27 13 49 97 49* 55123456780465949pivoti j當(dāng)當(dāng)i與與j相等時，基準(zhǔn)元素確定了位置相等時，基準(zhǔn)元素確定了位置i，結(jié)束本次劃分，結(jié)束本次劃分38 65 97 13 27 49* 551234567849049pivot快速排序中的一趟劃分算法快速排序中的一趟劃分算法38 27 13 49 97 49* 551234567804659第趟劃分結(jié)果第趟劃分結(jié)果 第一組第一組第二組第二組int Partition(SqList &L,int low,int high) pivotkey = L.rlow.key; i = low; j = high;

29、while (ij) while (i= pivotkey) j-; L.ri L.rj; while (ij & L.ri.key = pivotkey) i+; L.rj L.ri; return i;/Partition38 65 97 13 27 49* 551234567849049劃分劃分38 27 13 49 97 49* 550465劃分劃分38 27 1304劃分劃分9749* 55 65劃分劃分13 27 38劃分劃分2713劃分劃分49* 55 65劃分劃分65552765將交換改為元素的移動將交換改為元素的移動劃分算法改進劃分算法改進38 65 97 13 27

30、 49* 55123456784904949ij044938 65 97 13 27 49* 55123456784904949ij0438 65 97 13 27 49 551234567849049pivotij快速排序中的一趟劃分快速排序中的一趟劃分快速排序中的一趟劃分快速排序中的一趟劃分 38 65 97 13 27 49 551234567804949pivotijaj與與pivot比較，比較，aj小則小則ajai快速排序中的一趟劃分快速排序中的一趟劃分 38 65 97 13 27 49 551234567804949pivotij快速排序中的一趟劃分快速排序中的一趟劃分 38 6

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

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

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

34、則小則aj ai; 否則，利用否則，利用j向前掃描向前掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 27 1397 49 55123456780465949pivotijai與與pivot比較，比較，ai大則大則ai aj; 否則，利用否則，利用i向后掃描向后掃描快速排序中的一趟劃分快速排序中的一趟劃分 38 27 1397 49 55123456780465949pivotij快速排序中的一趟劃分快速排序中的一趟劃分 38 27 1397 49 55123456780465949pivoti ji與與j相等時，完成一次劃分相等時，完成一次劃分快速排序中的一趟劃分快速排序中的一趟劃分 3

35、8 27 13 49 97 49 551234567804659int Partition(SqList &L,int low,int high) L.r0 = L.rlow; pivotkey = L.r0.key; i = low; j = high; while (ij) while (i= pivotkey) j-; L.ri = L.rj; while (ij & L.ri.key = pivotkey) i+; L.rj = L.ri; L.ri = L.r0; return i;/Partition快速排序快速排序int Partition(SqList &

36、;L,int low,int high) . return i; /返回樞軸元素的位置返回樞軸元素的位置/Partitionvoid QSort(SqList &L, int low, int high) /對對L.rlowL.rhigh的元素進行快速排序的元素進行快速排序 if (low high) pivotloc = Partition(L,low,high); /一趟劃分一趟劃分 QSort(L,low,pivotloc - 1); QSort(L, pivotloc+1,high); /if /QSortq快速排序過程分析快速排序過程分析38 65 97 13 27 49*

37、551234567849049劃分劃分38 27 13 49 97 49* 550465劃分劃分38 27 1304劃分劃分9749* 55 65劃分劃分13 27 38劃分劃分2713劃分劃分49* 55 65劃分劃分65552765v以順序表作為存儲結(jié)構(gòu)的快速排序算法以順序表作為存儲結(jié)構(gòu)的快速排序算法時間復(fù)雜度：時間復(fù)雜度：O(nlogn)n快速排序在快速排序在最好情形最好情形下下( (左、右子區(qū)間的長度大致相左、右子區(qū)間的長度大致相等等) )，則結(jié)點數(shù)，則結(jié)點數(shù)n n與二叉樹深度與二叉樹深度h h應(yīng)滿足應(yīng)滿足loglog2 2nhlognhlog2 2n+1n+1，所以總的比較次數(shù)不會超

38、過，所以總的比較次數(shù)不會超過(n+1)log(n+1)log2 2n n。因此，快速排序的最好時間復(fù)雜度應(yīng)為。因此，快速排序的最好時間復(fù)雜度應(yīng)為O(nlog(nlog2 2n)n)。理論上已經(jīng)證明，快速排序的平均時間。理論上已經(jīng)證明，快速排序的平均時間復(fù)雜度也為復(fù)雜度也為O( (nlognlog2 2n)n)。n在在最壞情況最壞情況下下( (逆序或正序逆序或正序) )，時間復(fù)雜度為，時間復(fù)雜度為 O(n2)空間復(fù)雜度：空間復(fù)雜度：O(logn)n在最壞情況下在最壞情況下( (逆序或正序逆序或正序) )，空間復(fù)雜度為，空間復(fù)雜度為O(n)不穩(wěn)定不穩(wěn)定的排序方法的排序方法v快速排序不適合對小規(guī)模的

39、序列進行排序快速排序不適合對小規(guī)模的序列進行排序10.3 快速排序方法的改進快速排序方法的改進v三者取中的方法選取樞軸元素三者取中的方法選取樞軸元素v劃分的過程中進行劃分的過程中進行“起泡起泡”操作操作v快速排序算法被認(rèn)為是內(nèi)部排序方法中最好的一種快速排序算法被認(rèn)為是內(nèi)部排序方法中最好的一種13 27 38 49 49* 55 650497123456789最壞情況下的快速排序最壞情況下的快速排序13 27 38 49 49* 55 65049713 27 38 49 49* 55 65 9727 38 49 49* 55 65 9738 49 49* 55 65 9749 49* 55 65

40、 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 選擇排序選擇排序10.4.1 簡單選擇排序簡單選擇排序簡單選擇排序的簡單選擇排序的基本思想基本思想是：第一趟是：第一趟在在n n個記錄中選取最小記錄作為有序個記錄中選取最小記錄作為有序序列的第一個記錄，第二趟在序列的第一個記錄，第二趟在n-1n-1

41、個個記錄中選取最小記錄作為有序序列的記錄中選取最小記錄作為有序序列的第二個記錄，第第二個記錄，第i i趟在趟在n-i+1n-i+1個記錄中個記錄中選取最小的記錄作為有序序列多中的選取最小的記錄作為有序序列多中的第第i i個記錄。個記錄。q簡單選擇排序過程示例簡單選擇排序過程示例初始關(guān)鍵字序列初始關(guān)鍵字序列3412492831525149*123456780i=11234492831525149*i=21228493431525149*i=31228313449525149*i=41228313449525149*i=51228313449525149*i=6122831344949*5152i

42、=7122831344949*5152q簡單選擇排序算法簡單選擇排序算法v以順序表作為存儲結(jié)構(gòu)的簡單選擇排序算法以順序表作為存儲結(jié)構(gòu)的簡單選擇排序算法void SelectSort(SqList &L) /對順序表作簡單選擇排序?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ù)和記錄移動次數(shù)分析簡單選擇排序算法中關(guān)

43、鍵字的比較次數(shù)和記錄移動次數(shù) 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 /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元素的元素的移動次數(shù)為：移動次數(shù)為：3(n-1)/2 在正序情況下

44、在正序情況下元素的比較次數(shù)元素的比較次數(shù): : n(n-1)/2元素的元素的移動次數(shù)為：移動次數(shù)為：0q簡單選擇排序算法分析簡單選擇排序算法分析v以順序表作為存儲結(jié)構(gòu)的簡單選擇排序算法以順序表作為存儲結(jié)構(gòu)的簡單選擇排序算法時間復(fù)雜度：時間復(fù)雜度：O(n2)n在在n n個關(guān)鍵字中選出最小者，需要個關(guān)鍵字中選出最小者，需要n-1n-1次比較，繼續(xù)在剩余的次比較，繼續(xù)在剩余的n-1n-1個元素中選出次小者需要個元素中選出次小者需要n-2n-2次比較，依此類推次比較，依此類推?？臻g復(fù)雜度：空間復(fù)雜度：O(1)n只需要只需要 1 個輔助單元進行交換個輔助單元進行交換不穩(wěn)定的排序方法不穩(wěn)定的排序方法適用情

45、況適用情況n元素數(shù)目少的情況元素數(shù)目少的情況n無需完全排序的情況，比如，選出第無需完全排序的情況，比如，選出第i i小的元素小的元素v對簡單選擇排序過程進行改進：利用前面已經(jīng)進行過的對簡單選擇排序過程進行改進：利用前面已經(jīng)進行過的比較結(jié)果比較結(jié)果10.4.2 樹形選擇排序樹形選擇排序(Tree Selection Sort)又稱錦標(biāo)賽排序又稱錦標(biāo)賽排序(Tournament Sort):(Tournament Sort):首先對首先對n n個記錄個記錄的關(guān)鍵字兩兩進行比較，然后在的關(guān)鍵字兩兩進行比較，然后在n/2n/2個較小者之間再個較小者之間再進行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記進

46、行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。整個過程可用一個含有錄。整個過程可用一個含有n n個葉結(jié)點的二叉樹表示。個葉結(jié)點的二叉樹表示。例如例如3412492831525149*12283149*123112341212 492831525149*2. 樹形選擇排序樹形選擇排序(Tree Selection Sort)又稱錦標(biāo)賽排序又稱錦標(biāo)賽排序(Tournament Sort):(Tournament Sort):首先對首先對n n個記錄個記錄的關(guān)鍵字兩兩進行比較，然后在的關(guān)鍵字兩兩進行比較，然后在n/2n/2個較小者之間再個較小者之間再進行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記進

47、行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。錄。選出最小記錄后，將樹中的該最小記錄修改為選出最小記錄后，將樹中的該最小記錄修改為，然然后從該葉子結(jié)點所在子樹開始，修改到達(dá)樹根的路徑后從該葉子結(jié)點所在子樹開始，修改到達(dá)樹根的路徑上的結(jié)點上的結(jié)點34 492831525149*34 283149*28312834 492831525149*2. 樹形選擇排序樹形選擇排序(Tree Selection Sort)又稱錦標(biāo)賽排序又稱錦標(biāo)賽排序(Tournament Sort):(Tournament Sort):首先對首先對n n個記錄的關(guān)鍵字兩個記錄的關(guān)鍵字兩兩進行比較，然后在兩進行比較，然后在

48、n/2n/2個較小者之間再進行兩兩比較，如此重個較小者之間再進行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄。復(fù)，直至選出最小關(guān)鍵字的記錄。選出最小記錄后，將樹中的該最小記錄修改為選出最小記錄后，將樹中的該最小記錄修改為，然后從該葉子然后從該葉子結(jié)點所在子樹開始修改到達(dá)樹根的路徑上的結(jié)點結(jié)點所在子樹開始修改到達(dá)樹根的路徑上的結(jié)點以后每選出一個小元素，都只需進行以后每選出一個小元素，都只需進行(logn)(logn)次比較次比較34 4931525149*34 493149*34313134 492831525149*q樹形選擇排序的缺陷樹形選擇排序的缺陷需要較多的輔助空間需要較多的輔助空間存在

49、與存在與“”進行比較的冗余比較進行比較的冗余比較34 4931525149*34 493149*34313110.4.3 堆排序堆排序(Heap Sort)只需要一個元素的輔助空間只需要一個元素的輔助空間算法的時間復(fù)雜度為算法的時間復(fù)雜度為O(nlogn)v堆的定義堆的定義對于對于n n個元素的序列個元素的序列kk1 1,k,k2 2,.,k,.,kn n ，當(dāng)且僅當(dāng)滿足以，當(dāng)且僅當(dāng)滿足以下關(guān)系時，稱之為堆。下關(guān)系時，稱之為堆。 1i2ii2ikkkk 1i2ii2ikkkk2n,.,2,1i或或v堆堆(完全二叉樹完全二叉樹)96833811279(a) 大頂堆大頂堆(max heap)123

50、685472430(b) 小頂堆小頂堆(min heap)5391 1i2ii2ikkkk 1i2ii2ikkkkq堆排序堆排序(Heap Sort)原理原理對一組待排序記錄的關(guān)鍵字，首先把它們按堆的定義對一組待排序記錄的關(guān)鍵字，首先把它們按堆的定義建成小建成小( (大大) )頂堆，然后輸出堆頂?shù)淖钚№敹眩缓筝敵龆秧數(shù)淖钚? (大大) )關(guān)鍵字所關(guān)鍵字所代表的記錄，再對剩余的關(guān)鍵字建堆，以便得到次小代表的記錄，再對剩余的關(guān)鍵字建堆，以便得到次小( (大大) )的關(guān)鍵字，如此反復(fù)進行，直到全部關(guān)鍵字排成的關(guān)鍵字，如此反復(fù)進行，直到全部關(guān)鍵字排成有序序列為止。有序序列為止。v 實現(xiàn)堆排序需要解決

51、兩個問題：實現(xiàn)堆排序需要解決兩個問題： (1) (1) 如何建堆？如何建堆？ (2) (2) 輸出堆頂元素后，如何將剩余元素重新調(diào)整為一個輸出堆頂元素后，如何將剩余元素重新調(diào)整為一個新堆？新堆？q堆排序過程示例堆排序過程示例v下面是一個小頂堆，輸出堆頂元素后，將剩余元素重新調(diào)整為一個下面是一個小頂堆，輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆的方法是：從樹根開始，若以某結(jié)點為根的子樹不是堆，則將新堆的方法是：從樹根開始，若以某結(jié)點為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向1236854724305391913

52、6854724305312交換堆頂元素與序列末交換堆頂元素與序列末端的元素端的元素比較比較比較比較-交換交換v輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆的方法是：從樹輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆的方法是：從樹根開始，若以某結(jié)點為根的子樹不是堆，則將其孩子中的較小者與根開始，若以某結(jié)點為根的子樹不是堆，則將其孩子中的較小者與之交換，即將非堆的子樹推向葉子方向之交換，即將非堆的子樹推向葉子方向2436854730915312繼續(xù)向葉子方向調(diào)整繼續(xù)向葉子方向調(diào)整2436854791305312比較比較比較比較交換交換q堆排序過程示例堆排序過程示例v一旦已調(diào)整為堆，則輸出堆頂元素，重

53、復(fù)將剩余元素重一旦已調(diào)整為堆，則輸出堆頂元素，重復(fù)將剩余元素重新調(diào)整為一個新堆。新調(diào)整為一個新堆。24368547309153125336854730912412交換堆頂元素與序列末交換堆頂元素與序列末端的元素端的元素q堆排序過程示例堆排序過程示例v輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆3036854753912412調(diào)整成堆調(diào)整成堆5336854730912412q堆排序過程示例堆排序過程示例v輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆9136854753302412反復(fù)將堆頂元素與序列反復(fù)將堆頂

54、元素與序列末端的元素的交換，并末端的元素的交換，并重新調(diào)整成堆。重新調(diào)整成堆。9185473653302412q調(diào)整堆元素調(diào)整堆元素( (篩選篩選) ) 對于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小對于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小( (大大) )頂頂堆，從而得到最小堆，從而得到最小( (大大) )關(guān)鍵字。關(guān)鍵字。 在輸出堆頂元素之后，用堆中最后一個元素替代在輸出堆頂元素之后，用堆中最后一個元素替代之。此時由于以之。此時由于以K K2 2和和K K3 3為根的為根的子樹仍具有堆的特性子樹仍具有堆的特性，因此只需自上而下進行調(diào)整即可。因此只需自上而下進行調(diào)整即可。 調(diào)整過程為：調(diào)整過程為：

55、首先令首先令K K1 1的兩個子樹根進行比較，令其中較的兩個子樹根進行比較，令其中較小小( (大大) )者與者與K K1 1相比較，將最小相比較，將最小( (大大) )元素交換至元素交換至K K1 1，使得，使得K K1 1、K K2 2和和K K3 3成為堆。由于成為堆。由于交換后破壞了子樹的堆性質(zhì)交換后破壞了子樹的堆性質(zhì)，則需再次進行，則需再次進行與上述過程類似的調(diào)整，直至進行到最下層的葉結(jié)點為止。與上述過程類似的調(diào)整，直至進行到最下層的葉結(jié)點為止。調(diào)整后即得到一個有調(diào)整后即得到一個有n-1n-1個元素的新堆，從而得到次小關(guān)鍵字。個元素的新堆，從而得到次小關(guān)鍵字。q堆排序過程示例堆排序過程

56、示例v輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆輸出堆頂元素后，將剩余元素重新調(diào)整為一個新堆q調(diào)整堆元素調(diào)整堆元素( (篩選篩選) ) 對于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小對于給出的關(guān)鍵字序列，經(jīng)初始建堆后便得到小( (大大) )頂堆，從而得頂堆，從而得到最小到最小( (大大) )關(guān)鍵字。關(guān)鍵字。 在輸出堆頂元素之后，用堆中最后一個元素替代之。此時由于以在輸出堆頂元素之后，用堆中最后一個元素替代之。此時由于以K K2 2和和K K3 3為根的子樹仍具有堆的特性，因此只需自上而下進行調(diào)整即可。為根的子樹仍具有堆的特性，因此只需自上而下進行調(diào)整即可。 首先令首先令K K1 1將的兩個子樹根

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

58、堆中最后一個元素交換且調(diào)整，又得到了有又得到了有n-2n-2個元素的新堆。為節(jié)省存貯開銷，可以把輸出個元素的新堆。為節(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)可以在初始情況為堆的情況下完成排序，那么，如何建立起初始堆呢？如何建立起初始堆呢？q堆排序過程示例堆排序過程示例

59、建初始堆47369112533024851236854724305391建初始堆4736911253302485(a)4736851253302491(b)v從最后一個具有葉子的結(jié)點從最后一個具有葉子的結(jié)點( (編號編號n/2)n/2)開始建子堆，依開始建子堆，依次考查結(jié)點次考查結(jié)點n/2-1,n/2-2,.n/2-1,n/2-2,.，1 1等是否為堆，若否等是否為堆，若否則調(diào)整為堆則調(diào)整為堆建初始堆4736851224305391v從最后一個具有葉子的結(jié)點從最后一個具有葉子的結(jié)點( (編號編號n/2)n/2)開始建子堆，依開始建子堆，依次考查結(jié)點次考查結(jié)點n/2-1,n/2-2,.n/2-1

60、,n/2-2,.，1 1等是否為堆，若否等是否為堆，若否則調(diào)整為堆則調(diào)整為堆(C)4712853624305391(d)建初始堆1247853624305391v從最后一個具有葉子的結(jié)點從最后一個具有葉子的結(jié)點( (編號編號n/2)n/2)開始建子堆，依開始建子堆，依次考查結(jié)點次考查結(jié)點n/2-1,n/2-2,.n/2-1,n/2-2,.，1 1等是否為堆，若否等是否為堆，若否則調(diào)整為堆則調(diào)整為堆(e)1236854724305391(f)v當(dāng)以下標(biāo)當(dāng)以下標(biāo)1 1為根的完全二叉樹為堆時，初始堆已建立為根的完全二叉樹為堆時，初始堆已建立v也可以從空堆開始建初始堆也可以從空堆開始建初始堆10.4 堆排序堆排序v19641964年弗洛伊德（年弗洛伊德（FloydFloyd）提出了篩選法建立初始堆，具體）提