數(shù)據(jù)結(jié)構(gòu)-03排序.

1、 第三章第三章 排排 序序（Sorting）2第三章第三章 排序排序n3.1 3.1 排序的基本概念排序的基本概念n3.2 3.2 簡單排序方法簡單排序方法n3.3 3.3 先進法排序方法先進法排序方法n3.4 3.4 基數(shù)排序基數(shù)排序n3.5 3.5 各種排序方法的綜合比較各種排序方法的綜合比較3第三章第三章 排序排序n待排序數(shù)據(jù)元素（記錄）的存儲結(jié)構(gòu)：待排序數(shù)據(jù)元素（記錄）的存儲結(jié)構(gòu)：typedeftypedef intint KeyType KeyType /定義關(guān)鍵字類型為整型定義關(guān)鍵字類型為整型typedeftypedef structstruct KeyType KeyType k

2、ey;key; /關(guān)鍵字項關(guān)鍵字項 InfoType otherinfoInfoType otherinfo; ; /其他數(shù)據(jù)項其他數(shù)據(jù)項 RcdTypeRcdType; ; /記錄類型記錄類型n本章的排序圖例只標出了記錄的關(guān)鍵字。本章的排序圖例只標出了記錄的關(guān)鍵字。43.1 3.1 排序的基本概念排序的基本概念n3.1.1 3.1.1 排序的定義排序的定義n3.1.2 3.1.2 排序的特性排序的特性穩(wěn)定性與穩(wěn)定性與不穩(wěn)定性不穩(wěn)定性n3.1.3 3.1.3 排序的分類排序的分類n3.1.4 3.1.4 內(nèi)排序的特點內(nèi)排序的特點n3.1.5 3.1.5 選擇排序法選擇排序法53.1 3.1 排

3、序的基本概念排序的基本概念n3.1.1 3.1.1 排序的定義排序的定義n簡單定義：排序是按照關(guān)鍵字的簡單定義：排序是按照關(guān)鍵字的非遞減非遞減或或非遞增非遞增順順序?qū)σ唤M記錄重新進行序?qū)σ唤M記錄重新進行整隊整隊（或（或排列排列）的操作。）的操作。n數(shù)學定義：假設(shè)含有數(shù)學定義：假設(shè)含有n個記錄的序列為：個記錄的序列為：r1, r2, ,rn(3-1)它們的關(guān)鍵字相應(yīng)為它們的關(guān)鍵字相應(yīng)為k1, k2, ,kn,對式對式(3-1)的記錄的記錄序列進行排序就是要確定序號序列進行排序就是要確定序號1,2, ,n的一種排列的一種排列p1, p2,pn使其相應(yīng)的關(guān)鍵字滿足如下的非遞增使其相應(yīng)的關(guān)鍵字滿足如下

4、的非遞增(減減)關(guān)系：關(guān)系：kp1 kp2 kpn (3-2)也就是使式也就是使式(3-2)的記錄序列重新排列成一個按關(guān)鍵的記錄序列重新排列成一個按關(guān)鍵字有序的序列字有序的序列rp1 rp2 rpn (3-3)63.1 3.1 排序的基本概念排序的基本概念n3.1.2 3.1.2 排序的特性排序的特性穩(wěn)定性與不穩(wěn)定性穩(wěn)定性與不穩(wěn)定性n當待排記錄中的關(guān)鍵字當待排記錄中的關(guān)鍵字ki(1,2,n)都不相同時，則都不相同時，則任何一個記錄的無序序列經(jīng)排序后得到的結(jié)果是惟一任何一個記錄的無序序列經(jīng)排序后得到的結(jié)果是惟一的。的。n簡單地說，簡單地說，穩(wěn)定性排序穩(wěn)定性排序-數(shù)據(jù)排序過后能使值相同數(shù)據(jù)排序過后

5、能使值相同的數(shù)據(jù)，保持原順序中之相對位置。反之，則稱為的數(shù)據(jù)，保持原順序中之相對位置。反之，則稱為“不穩(wěn)定性排序不穩(wěn)定性排序” 。n若排序的序列中存在兩個或兩個以上關(guān)鍵字相等的若排序的序列中存在兩個或兩個以上關(guān)鍵字相等的記錄時，則排序得到的記錄序列的結(jié)果不惟一。記錄時，則排序得到的記錄序列的結(jié)果不惟一。n假設(shè)假設(shè)ki= kj (1i n, 1jn, ijj )，且在排序前的序列，且在排序前的序列中中 ri 領(lǐng)先于領(lǐng)先于rj (即即ijj ) 。若在排序后的序列中。若在排序后的序列中ri 總是領(lǐng)總是領(lǐng)先于先于rj ，則稱所用的排序方法是，則稱所用的排序方法是穩(wěn)定穩(wěn)定的；反之，若可能的；反之，若可

6、能使排序后的序列中使排序后的序列中 rj領(lǐng)先于領(lǐng)先于ri ，則稱所用的排序方法是，則稱所用的排序方法是不穩(wěn)定不穩(wěn)定的。的。73.3.1.2 1.2 排序的特性穩(wěn)定性與不穩(wěn)定性272716169 9（1 1）31317 724249 9（2 2）17170 01 12 23 34 45 56 67 7 排序前：排序前：7 79 9（1 1） 9 9（2 2）161617172424272731310 01 12 23 34 45 56 67 7 穩(wěn)定排序：穩(wěn)定排序：7 79 9（2 2） 9 9（1 1）161617172424272731310 01 12 23 34 45 56 67 7 不

7、穩(wěn)定排序：不穩(wěn)定排序：83.1.3 3.1.3 排序的分類排序的分類n根據(jù)在排序的過程涉及的存儲器不同，排序方根據(jù)在排序的過程涉及的存儲器不同，排序方法可分為兩類：法可分為兩類：n1.1.內(nèi)部排序（內(nèi)部排序（Internal Sort）：在排序進行的過程）：在排序進行的過程中不使用計算機外部存儲器的排序過程。中不使用計算機外部存儲器的排序過程。n選擇排序選擇排序n插入排序插入排序n起泡排序起泡排序n快速排序快速排序n歸并排序歸并排序n堆排序堆排序n基數(shù)排序基數(shù)排序n2. 外部排序（外部排序（External Sort）：在排序進行的過程）：在排序進行的過程中需要對外存進行訪問的排序過程。中需要

8、對外存進行訪問的排序過程。93.1.4 3.1.4 內(nèi)排序的特點內(nèi)排序的特點n 待排序記錄序列的存儲結(jié)構(gòu)：待排序記錄序列的存儲結(jié)構(gòu)：const int const int MAXSIZE=20 MAXSIZE=20 /定義最大順序表的長度定義最大順序表的長度typedeftypedef structstruct RcdTypeRcdType rMAXSIZE+1; rMAXSIZE+1;/r0/r0閑置或作為閑置或作為“哨兵哨兵” intint length; length; /順序表的真正長度順序表的真正長度 SqListSqList; ; /順序表類型順序表類型n 內(nèi)部排序的過程是一個逐步

9、擴大記錄的有序序列的過程。通常內(nèi)部排序的過程是一個逐步擴大記錄的有序序列的過程。通常在排序的過程中，參與排序的記錄序列可劃分兩個區(qū)域：有序序在排序的過程中，參與排序的記錄序列可劃分兩個區(qū)域：有序序列區(qū)和無序序列區(qū)，其中有序序列區(qū)的的記錄已按關(guān)鍵字非遞減列區(qū)和無序序列區(qū)，其中有序序列區(qū)的的記錄已按關(guān)鍵字非遞減有序排列。有序排列。n 使有序序列中記錄的數(shù)目至少增加一個的操作稱為使有序序列中記錄的數(shù)目至少增加一個的操作稱為一趟排序一趟排序。103.1.5 選擇排序法選擇排序法n思想：在排序過程序中，依次從待排序的記錄序列中思想：在排序過程序中，依次從待排序的記錄序列中選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字

10、值次小的記錄、選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字值次小的記錄、，并分別有序序列中的第并分別有序序列中的第1個位置、第二個位置、個位置、第二個位置、，最后剩下一個關(guān)鍵字值最大的記錄位于序列的最后一個最后剩下一個關(guān)鍵字值最大的記錄位于序列的最后一個位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大排列的的有序序列。大排列的的有序序列。有序序列有序序列 R1.i-1R1.i-1無序序列無序序列 Ri.nRi.n有序序列有序序列 R1.i-1R1.i-1RjRjRiRi有序序列有序序列 R1.iR1.i無序序列無序序列 Ri+1.nRi+1.n一趟排序后一

11、趟排序后一趟排序開始一趟排序開始113.1.5 選擇排序法選擇排序法n一趟排序算法：一趟排序算法：voidvoid SelectPass(SqList SelectPass(SqList &L, &L,intint i) i) RcdType RcdType W; W; intint j,k; j,k; j=i; j=i; / j j指示無序序列中第一個記錄的位置指示無序序列中第一個記錄的位置 forfor(k=i+1;k=L.length;k+)(k=i+1;k=L.length;k+)if(L.rk.keyL.rj.key) j=k; if(L.rk.keyL.rj.key

12、) j=k; /只記錄位置只記錄位置 ifif(i!=j) (i!=j) / 交換交換RjRj和和Ri; Ri; W=L.ri; L.ri=L.rj; L.rj= W; W=L.ri; L.ri=L.rj; L.rj= W; / L.ri L.rj; L.ri L.rj; / SelectPass/ SelectPass123.1.5 選擇排序法選擇排序法n整個算法：整個算法：voidvoid SelectSort(SqList SelectSort(SqList &L) &L) RcdType RcdType W;W; forfor(i=1;iL.length;i+)(i=1

13、;iL.length;i+) j=i; j=i; / j j指示無序序列中第一個記錄的位置指示無序序列中第一個記錄的位置 forfor(k=i+1;k=L.length;k+) (k=i+1;k=L.length;k+) /找到最小記錄下標找到最小記錄下標 if(L.rk.keyL.rj.key) j=k; if(L.rk.keyL.rj.key) j=k; ifif(i!=j) (i!=j) / 交換交換RjRj和和Ri; Ri; W=L.ri; L.ri=L.rj; L.rj= W; W=L.ri; L.ri=L.rj; L.rj= W; / for for / SelectSort/ S

14、electSort133.1.5 選擇排序法選擇排序法初始狀態(tài)初始狀態(tài)49491 13838656549492 27676131327275252i=1i=113133838656549492 2767649491 127275252i=2i=213132727656549492 2767649491 138385252i=3i=313132727383849492 2767649491 165655252i=4i=413132727383849492 2767649491 165655252i=5i=513132727383849492 249491 1656552527676i=6i=61

15、3132727383849492 249491 1656576765252i=7i=713132727383849492 249491 1656576765252143.1.5 選擇排序法選擇排序法n時間復(fù)雜度：時間復(fù)雜度：O(n2)n空間復(fù)雜度：空間復(fù)雜度：O(1)n優(yōu)點：優(yōu)點：n算法簡單；輔助空間少。算法簡單；輔助空間少。n缺點：缺點：n效率低；不穩(wěn)定性排序。效率低；不穩(wěn)定性排序。153.2 簡單排序方法簡單排序方法n3.2.1 3.2.1 插入排序插入排序n3.2.2 3.2.2 起泡排序起泡排序163.2.1 插入排序插入排序n基本思想：依次將記錄序列中的每一個記錄插入到有序段中，使有

16、基本思想：依次將記錄序列中的每一個記錄插入到有序段中，使有序段的長度不斷地擴大。其具體的排序過程可以描述如下：首先將待序段的長度不斷地擴大。其具體的排序過程可以描述如下：首先將待排序記錄序列中的第一個記錄作為一個有序段，將記錄序列中的第二排序記錄序列中的第一個記錄作為一個有序段，將記錄序列中的第二個記錄插入到上述有序段中，形成由兩個記錄組成的有序段，再將記個記錄插入到上述有序段中，形成由兩個記錄組成的有序段，再將記錄序列中的第三個記錄插入到這個有序段中，形成由三個記錄組成的錄序列中的第三個記錄插入到這個有序段中，形成由三個記錄組成的有序段，有序段，依此類推，每一趟都是將一個記錄插入到前面的有序

17、段中。依此類推，每一趟都是將一個記錄插入到前面的有序段中。n假設(shè)當前欲處理第假設(shè)當前欲處理第i個記錄，則將個記錄，則將Ri這個記錄插入到有序這個記錄插入到有序R1.i-1 段段中，從而使有序序列長度增中，從而使有序序列長度增1，直到所有記錄都插入到有序段中。一共，直到所有記錄都插入到有序段中。一共需要經(jīng)過需要經(jīng)過n-1趟就可以將初始序列的趟就可以將初始序列的n個記錄重新排列成按關(guān)鍵字值大個記錄重新排列成按關(guān)鍵字值大小排列的有序序列。小排列的有序序列。RiRi有序序列有序序列 R1.iR1.i無序序列無序序列 Ri+1.nRi+1.n一趟排序后一趟排序后一趟排序開始一趟排序開始有序序列有序序列

18、R1.i-1R1.i-1無序序列無序序列 Ri.nRi.n173.2.1 插入排序插入排序6 69 93 34 46 69 93 34 46 69 96 69 93 34 43 36 69 93 36 69 94 43 34 46 69 9插入插入9 9插入插入3 3插入插入4 4起始起始183.2.1 插入排序插入排序n一趟排序算法：一趟排序算法：voidvoid InsertPass(SqList InsertPass(SqList &L, &L,intint i) i) /將將L.riL.ri插入有序的插入有序的R1.i-1R1.i-1中中 L.r0=L.ri; L.r0

19、=L.ri; /復(fù)制為哨兵復(fù)制為哨兵 forfor(j=i-1;L.r0.keyL.rj.key;j-)(j=i-1;L.r0.keyL.rj.key;j-)L.rj+1=L.rj; L.rj+1=L.rj; /記錄后移記錄后移 L.rj+1= L.r0; L.rj+1= L.r0; /插入到正確位置插入到正確位置 /InsertPass/InsertPass193.2.1 插入排序插入排序n整個算法：整個算法：voidvoid InsertSort(SqList InsertSort(SqList &L) &L) /將將L.riL.ri插入有序的插入有序的R1.i-1R1.i

20、-1中中 forfor(i=2;i=L.length;i+)(i=2;i=L.length;i+) ifif(L.ri.keyL.ri-1.key) (L.ri.keyL.ri-1.key) L.r0=L.ri; L.r0=L.ri; /復(fù)制為哨兵復(fù)制為哨兵 forfor(j=i-1;L.r0.keyL.rj.key;j-)(j=i-1;L.r0.keyL.rj.key;j-) L.rj+1=L.rj; L.rj+1=L.rj; /記錄后移記錄后移 L.rj+1= L.r0; L.rj+1= L.r0; /插入到正確位置插入到正確位置 /InsertSort/InsertSort203.2.1

21、 插入排序插入排序初始狀態(tài)初始狀態(tài)49491 138386565979776761313272749492 2i=2i=2i=3i=3i=4i=4i=5i=5i=6i=6i=7i=7i=8i=8383849491 16565979776761313272749492 2383849491 16565979776761313272749492 23838656549491 16565979776761313272749492 23838979749491 16565767697971313272749492 23838767649491 13838656576769797272749492 21

22、313131349491 12727383865657676979749492 21313272749491 12727383897976565767649492 2131349492 2213.2.1 插入排序插入排序n時間復(fù)雜度時間復(fù)雜度n最佳狀況（最佳狀況（正序）正序）： O（n）n最壞狀況最壞狀況（逆序）：（逆序）：O(n2)n平均狀況：平均狀況： O(n2)n空間復(fù)雜度：空間復(fù)雜度：O(1)n優(yōu)點：優(yōu)點：n算法簡單；穩(wěn)定排序算法簡單；穩(wěn)定排序。n缺點：缺點：n花費較長的排序時間。花費較長的排序時間。223.2.2 3.2.2 起泡排序起泡排序n思想：通過對無序序列區(qū)中的記錄進行相鄰記

23、錄關(guān)鍵思想：通過對無序序列區(qū)中的記錄進行相鄰記錄關(guān)鍵字間的字間的“比較比較”和記錄位置的和記錄位置的“交換交換”實現(xiàn)關(guān)鍵字較小實現(xiàn)關(guān)鍵字較小的記錄向的記錄向“一頭一頭”漂移，而關(guān)鍵字較大的記錄向漂移，而關(guān)鍵字較大的記錄向“另一另一頭頭”下沉，從而達到記錄按關(guān)鍵字非遞減順序有序排列下沉，從而達到記錄按關(guān)鍵字非遞減順序有序排列的目標。的目標。i i無無序序列序序列 R1.i-1R1.i-1有有序序列序序列 Ri.nRi.n一趟排序后一趟排序后一趟排序開始一趟排序開始無無序序列序序列 R1.iR1.i有有序序列序序列 Ri+1.nRi+1.n233.2.2 3.2.2 起泡排序起泡排序3737969

24、68 854548 854549696373796968 89696373754548 8969654548 83737243.2.2 3.2.2 起泡排序起泡排序n一趟排序算法：一趟排序算法：voidvoid BubblePass(SqList BubblePass(SqList &L, &L,intint i) i) RcdType RcdType W; W; / / j j指示無序序列中第一個記錄的位置指示無序序列中第一個記錄的位置 forfor(j=1;ji;j+)(j=1;ji;j+)ifif(L.rj+1.keyL.rj.key) (L.rj+1.key1;i-)(

25、i=L.length;i1;i-) forfor(j=1;ji;j+)(j=1;ji;j+) ifif(L.rj+1.keyL.rj.key) (L.rj+1.key1)(i1) lastExchange lastExchange=1;=1; forfor(j=1;ji;j+)(j=1;ji;j+) ifif(L.rj+1.keyL.rj.key) (L.rj+1.key=pivotkeyRhigh.key=pivotkey，則減小，則減小highhighn否則將否則將RhighRhigh移至指針移至指針lowlow所指位置所指位置n檢測指針所指記錄檢測指針所指記錄n若若Rlow.key=pi

26、votkeyRlow.key=pivotkey，則增加，則增加lowlown否則將否則將RlowRlow移至指針移至指針highhigh所指位置所指位置n重復(fù)進行，直至重復(fù)進行，直至lowlow和和highhigh指向同一位置。指向同一位置。323.3.1 3.3.1 快速排序快速排序28284 436362 26565141455551717i ij jtemptemp2828i ii i28284 436362 26565141455551717i ij j1717j jj j1414i ii i6565j j282817174 42 255553636141465652828363633

27、3.3.1 3.3.1 快速排序快速排序n一趟排序算法：一趟排序算法：intint Partition(RcdType Partition(RcdType R, R,intint low, low,intint high) high) intint pivotkey pivotkey; ; R0=Rlow; R0=Rlow; /將樞軸放在閑置單元將樞軸放在閑置單元 pivotkeypivotkey=Rlow.key; =Rlow.key; /將樞軸的關(guān)鍵字放在將樞軸的關(guān)鍵字放在pivotkeypivotkey while(lowhigh) while(lowhigh) whilewhile(l

28、ow=pivotkey(low=pivotkey) ) high-; high-; /high/high往左找，比小時停止往左找，比小時停止 ifif(lowhigh) Rlow+=Rhigh;(lowhigh) Rlow+=Rhigh;/把比樞軸小的記錄移到低端把比樞軸小的記錄移到低端 whilewhile(lowhigh&Rlow.key=pivotkey(lowhigh&Rlow.key=pivotkey) ) low+; low+;/low/low往右找，比往右找，比pivotkeypivotkey大時停止大時停止 ifif(lowhigh) Rhigh-=Rlow;(

29、lowhigh) Rhigh-=Rlow;/把比樞軸大的記錄移到高端把比樞軸大的記錄移到高端 /whilewhile Rlow=R0; Rlow=R0; /把樞軸放在正確的位置把樞軸放在正確的位置 return(low) ; return(low) ; /返回樞軸位置返回樞軸位置 /PartitionPartition343.3.1 3.3.1 快速排序快速排序n整個算法：整個算法：voidvoid QSort(RcdType QSort(RcdType R, R,intint s, s,intint t) t) /對記錄序列對記錄序列Rs.tRs.t進行快速排序進行快速排序 ifif(s(s

30、11 pivotLoc pivotLoc=Partition(R,s,t); =Partition(R,s,t); /對對Rs.tRs.t進行一次劃分進行一次劃分 QSort(R,s,pivotLocQSort(R,s,pivotLoc-1); -1); /對低端子序列遞歸排序?qū)Φ投俗有蛄羞f歸排序 QSort(R,s,pivotLocQSort(R,s,pivotLoc-1); -1); /對高端子序列遞歸排序?qū)Ω叨俗有蛄羞f歸排序 /ifif /QSort/QSortvoidvoid QuickSort(SqList QuickSort(SqList &L) &L) /對順序表

31、對順序表L L進行快速排序進行快速排序 QSortQSort(L.r,1,L.length);(L.r,1,L.length); /QuickSort/QuickSort一趟快速排序示例一趟快速排序示例49491 138386565979776761313272749492 2i ij jj j272738386565979776761313272749492 2i ij ji i272738386565979776761313656549492 2i ij jj j272738381313979776761313656549492 2i ij ji i27273838131397977676

32、9797656549492 2i ij jj j27273838131349491 176769797656549492 2pivotkeypivotkey49491 1363.3.1 3.3.1 快速排序快速排序初始狀態(tài)初始狀態(tài)49491 138386565979776761313272749492 2一次劃分一次劃分2727131376767676979749492 2656549491 138381313383876767676979749492 2656549491 127271313383876767676979749492 2656549491 127271313383876767

33、676979749492 2656549491 127271313383876767676979749492 2656549491 127271313383876767676979749492 2656549491 12727373.3.1 3.3.1 快速排序快速排序n時間復(fù)雜度：時間復(fù)雜度：n最佳狀況最佳狀況( (當每次分割的兩個區(qū)塊都均勻大小時當每次分割的兩個區(qū)塊都均勻大小時)：O(nO(n* *loglog2 2n)n)n最壞狀況最壞狀況( (每次分割的兩個區(qū)塊大小相差很多每次分割的兩個區(qū)塊大小相差很多時時)：O(n2)n平均狀況：平均狀況： O(nO(n* *loglog2 2n)n

34、)n空間復(fù)雜度：空間復(fù)雜度：使用遞歸的深度使用遞歸的深度n最佳狀況最佳狀況: O(log: O(log2 2n)n)n最壞狀況最壞狀況: O(n): O(n)n平均狀況：平均狀況：介于介于O(logO(log2 2n)n) 和和O(n)之間之間n優(yōu)點：優(yōu)點：n平均時間復(fù)雜度低，適用于完全隨機的序列。平均時間復(fù)雜度低，適用于完全隨機的序列。n缺點：缺點：n不穩(wěn)定性排序不穩(wěn)定性排序; ;空間效率低；結(jié)點順序不好則效率低?？臻g效率低；結(jié)點順序不好則效率低。383.3.2 歸并排序歸并排序n歸并排序法是利用歸并排序法是利用“歸并歸并”操作的一種排序方操作的一種排序方法。法。n基本思想：基本思想：n將待

35、排序的原始記錄序列將待排序的原始記錄序列Rs.t中取一個中中取一個中間位置間位置(s+t)/2，先分別對子序列，先分別對子序列Rs.(s+t)/2和和R(s+t)/2+1. t進行遞歸的歸并排序，然后進行遞歸的歸并排序，然后進行一次歸并處理。進行一次歸并處理。393.3.2 歸并排序歸并排序n 歸并排序基本操作歸并排序基本操作將兩個位置相鄰的有序記錄子序列將兩個位置相鄰的有序記錄子序列Ri.mRi.m和和Rm+1.nRm+1.n歸并為一個有序記錄序列歸并為一個有序記錄序列RnRn，算法如，算法如下：下：voidvoid Merge(RcdType SR,RcdType Merge(RcdTyp

36、e SR,RcdType TR, TR,intint i, i,intint m, m,intint n) n) /對有序的對有序的Ri.mRi.m和和Ri+1.nRi+1.n歸并為一個有序的歸并為一個有序的RnRn forfor(j=m+1,k=i;i=m&j=n;k+) (j=m+1,k=i;i=m&j=n;k+) ifif(SRi.key=SRj.key) TRk=SRi+;(SRi.key=SRj.key) TRk=SRi+; elseelse TRk=SRj+; TRk=SRj+; /for/for whilewhile(i=m) TRk+=SRi+; (i=m) T

37、Rk+=SRi+; /將剩余的將剩余的Ri.mRi.m復(fù)制到復(fù)制到TRTR whilewhile(j=n) TRk+=SRj+; (jn/2=4（1）考慮）考慮n4n4 n8 不變不變67491382n1n2n3n4n5n6n7n88453.3.3 堆排序堆排序（2）考慮）考慮n3n3 n7 交換交換67491382n1n2n3n4n5n6n7n8267491382n1n2n3n4n5n6n7n862463.3.3 堆排序堆排序（3）考慮）考慮n2n4n2n5n2 不變不變27491386n1n2n3n4n5n6n7n89473.3.3 堆排序堆排序（4）考慮）考慮n1n1 n2 交換交換29

38、471386n1n2n3n4n5n6n7n8769471382n1n2n3n4n5n6n7n887493.3.3 堆排序堆排序考慮考慮n4n4n8 不變不變29481376n1n2n3n4n5n6n7n879 98 86 67 71 14 42 23 3最大堆最大堆503.3.3 堆排序堆排序29481376n1n2n3n4n5n6n7n8n取出樹根取出樹根與最后一個節(jié)點交換與最后一個節(jié)點交換39n1n823481976n1n2n3n4n5n6n7n8928471936n1n2n3n4n5n6n7n89n1n7成堆成堆5128471936n1n2n3n4n5n6n7n893.3.3 堆排序堆排

39、序n1n7n1n6成堆成堆8222471936n1n2n3n4n5n6n7n89827431926n1n2n3n4n5n6n7n898523.3.3 堆排序堆排序n1n6n1n5成堆成堆27431926n1n2n3n4n5n6n7n8987424431926n1n2n3n4n5n6n7n898726431924n1n2n3n4n5n6n7n8987533.3.3 堆排序堆排序n1n5n1n4成堆成堆26431924n1n2n3n4n5n6n7n89876126431924n1n2n3n4n5n6n7n8987624431921n1n2n3n4n5n6n7n89876543.3.3 堆排序堆排序

40、n1n4n1n3成堆成堆24431921n1n2n3n4n5n6n7n898764223421941n1n2n3n4n5n6n7n89876422431941n1n2n3n4n5n6n7n898764553.3.3 堆排序堆排序n1n3n1n2成堆成堆23421941n1n2n3n4n5n6n7n8987641321421943n1n2n3n4n5n6n7n898764322411943n1n2n3n4n5n6n7n8987643563.3.3 堆排序堆排序n1n222411943n1n2n3n4n5n6n7n89876431221411943n1n2n3n4n5n6n7n898764321

41、12 23 34 46 67 78 89 9void HeapSort(int void HeapSort(int * *heap,int index)heap,int index) int i,j,temp; int i,j,temp; for(i=index/2;i=1;i-) createHeap(heap,i,index); for(i=index/2;i=1;i-) createHeap(heap,i,index); for(i=index-1;i=1;i-) for(i=index-1;i=1;i-) heap1 heap1heapi+1; /heapi+1; /借助借助tempt

42、emp交換交換 createHeap(heap,1,i);createHeap(heap,1,i); void createHeap(int void createHeap(int * *heap,int root,int index)heap,int root,int index) int i,j,temp,finish=0; int i,j,temp,finish=0; j=2 j=2* *root;temp=heaproot;root;temp=heaproot; while(j=index&finish=0) while(j=index&finish=0) if(jin

43、dex) if(jindex) if(heapjheapj+1) j+; if(heapj=heapj) finish=1; if(temp=heapj) finish=1; else heapj/2=heapj; j else heapj/2=heapj; j* *=2; =2; heapj/2=temp; heapj/2=temp; 堆排序算法堆排序算法調(diào)用調(diào)用HeapSortHeapSort(list,index);(list,index);583.3.3 堆排序堆排序n時間復(fù)雜時間復(fù)雜度：度：O(nlog2n)n空間復(fù)雜度空間復(fù)雜度：O(1)O(1)n優(yōu)點：優(yōu)點：n最壞情況下時間復(fù)雜度

44、也僅為最壞情況下時間復(fù)雜度也僅為O(nlog2n) 。n缺點：缺點：n運行時間主要耗費在建初始堆和調(diào)整堆上，運行時間主要耗費在建初始堆和調(diào)整堆上，排序數(shù)據(jù)較少時，不值得提倡。排序數(shù)據(jù)較少時，不值得提倡。593.4 3.4 基數(shù)排序基數(shù)排序n基本思想：基本思想：n基數(shù)排序：假設(shè)記錄的邏輯關(guān)鍵字由多個關(guān)鍵字構(gòu)基數(shù)排序：假設(shè)記錄的邏輯關(guān)鍵字由多個關(guān)鍵字構(gòu)成，每個關(guān)鍵字可能取成，每個關(guān)鍵字可能取r r個值，則只要從最低位關(guān)鍵字個值，則只要從最低位關(guān)鍵字起，按關(guān)鍵字的不同值將記錄起，按關(guān)鍵字的不同值將記錄“分配分配”到到r r個隊列之后個隊列之后再再“收集收集”在一起，如此重復(fù)趟，最終完成整個記錄在一起

45、，如此重復(fù)趟，最終完成整個記錄序列的排序。序列的排序?！盎鶖?shù)基數(shù)”指的是指的是r r的取值范圍。的取值范圍。n例：關(guān)鍵字為三位整數(shù)，其關(guān)鍵字構(gòu)成是（例：關(guān)鍵字為三位整數(shù)，其關(guān)鍵字構(gòu)成是（k2, k1 , k0 ），）， k2, k1 , k0 的基數(shù)為的基數(shù)為10n例：關(guān)鍵字為例：關(guān)鍵字為5個字母，其關(guān)鍵字構(gòu)成是（個字母，其關(guān)鍵字構(gòu)成是（ k4, k3 , k2, k1 , k0 ），）， kj,(0=j收集收集-分配分配-收集收集基基數(shù)數(shù)排排序序示示例例7878090963633030747489899494252505056969181883830 01 12 23 34 45 56 67

46、 78 89 910101111（a a）初始狀態(tài)）初始狀態(tài)3030636383837474949425250505787818180909898969690 01 12 23 34 45 56 67 78 89 910101111（c c）第一趟收集后的結(jié)果）第一趟收集后的結(jié)果0505090918182525303063636969747478788383898994940 01 12 23 34 45 56 67 78 89 910101111（e e）第二趟收集后的結(jié)果）第二趟收集后的結(jié)果30300909898969690 01 12 23 34 45 56 67 78 89 9（b b

47、）第一趟分配后的結(jié)果）第一趟分配后的結(jié)果25250505787818187474949463638383181894940 01 12 23 34 45 56 67 78 89 9（d d）第二趟分配后的結(jié)果）第二趟分配后的結(jié)果7474787883838989636369690505090925253030需要一個臨時需要一個臨時的二維數(shù)組存的二維數(shù)組存放分配結(jié)果嗎？放分配結(jié)果嗎？610 01 12 23 34 45 56 67 78 89 9101011113.4 3.4 基數(shù)排序基數(shù)排序7878090963633030747489899494252505056969181883830 01

48、 12 23 34 45 56 67 78 89 910101111記錄數(shù)組記錄數(shù)組A A計數(shù)數(shù)組（個位）計數(shù)數(shù)組（個位）（a a）初始狀態(tài)和對）初始狀態(tài)和對“個位數(shù)個位數(shù)”計數(shù)的結(jié)果計數(shù)的結(jié)果0 03 30 01 12 23 34 45 56 67 78 89 90 02 20 01 10 02 22 22 2計數(shù)數(shù)組累加計數(shù)數(shù)組累加1 112120 01 12 23 34 45 56 67 78 89 97 79 97 71 11 13 35 57 7記錄數(shù)組記錄數(shù)組B B303063638383747494942525050578781818090989896969（b b）計數(shù)器的累加

49、結(jié)果和記錄）計數(shù)器的累加結(jié)果和記錄“復(fù)制復(fù)制”后的狀態(tài)后的狀態(tài)2 211116 6 5 54 410103 30 01 19 98 8 7 7620 01 12 23 34 45 56 67 78 89 9101011113.4 3.4 基數(shù)排序基數(shù)排序（b b）計數(shù)器的累加結(jié)果和記錄）計數(shù)器的累加結(jié)果和記錄“復(fù)制復(fù)制”后的狀后的狀態(tài)態(tài)3030636383837474949425250505787818180909898969690 01 12 23 34 45 56 67 78 89 910101111計數(shù)數(shù)組（十位）計數(shù)數(shù)組（十位）1 11 10 01 12 23 34 45 56 67

50、78 89 92 22 22 22 21 11 10 00 0計數(shù)數(shù)組累加計數(shù)數(shù)組累加3 312120 01 12 23 34 45 56 67 78 89 99 911117 72 24 45 55 55 5記錄數(shù)組記錄數(shù)組A A050509091818252530306363696974747878838389899494（c c）對）對“十位數(shù)十位數(shù)”計數(shù)、累加和記錄計數(shù)、累加和記錄“復(fù)制復(fù)制”后的狀態(tài)后的狀態(tài)記錄數(shù)組記錄數(shù)組B B6 610101 12 28 80 03 311117 79 95 54 4633.4 3.4 基數(shù)排序基數(shù)排序n基數(shù)排序需說明的數(shù)據(jù)結(jié)構(gòu)基數(shù)排序需說明的數(shù)據(jù)

51、結(jié)構(gòu)const intconst int MAX_NUM_OF_KEY=6 MAX_NUM_OF_KEY=6 /關(guān)鍵字項數(shù)的最大值關(guān)鍵字項數(shù)的最大值const intconst int RADIX=10 RADIX=10 /關(guān)鍵字的基數(shù)關(guān)鍵字的基數(shù)const intconst int MAXSIZE=10000MAXSIZE=10000 typedeftypedef structstruct KeysType KeysType keysMAX_NUM_OF_KEY; keysMAX_NUM_OF_KEY; /關(guān)鍵字數(shù)組關(guān)鍵字數(shù)組 InfoType otheritemsInfoType othe

52、ritems; ; /其他數(shù)據(jù)項其他數(shù)據(jù)項 /int bitsnumint bitsnum; ; /關(guān)鍵字的位數(shù)關(guān)鍵字的位數(shù)RcdTypeRcdType; ; /基數(shù)排序中的記錄類型基數(shù)排序中的記錄類型643.4 3.4 基數(shù)排序基數(shù)排序n 一趟基數(shù)排序算法：一趟基數(shù)排序算法：voidvoid RadixPass(RcdType A,RcdType RadixPass(RcdType A,RcdType B, B, intint n, n,intint i) i) /對數(shù)組對數(shù)組A A中記錄關(guān)鍵字的中記錄關(guān)鍵字的“第第i i位位”計數(shù)，并累計計數(shù)，并累計countcount的值的值 /將數(shù)組將

53、數(shù)組A A中復(fù)制到數(shù)組中復(fù)制到數(shù)組B B中中 forfor(j=0;jRADIX;j+) countj=0; (j=0;jRADIX;j+) countj=0; /計數(shù)數(shù)組計數(shù)數(shù)組countcount初始化初始化 forfor(k=0;kn;k+) (k=0;kn;k+) /對關(guān)鍵字的對關(guān)鍵字的“第第i i位位”計數(shù)計數(shù) countAk.keysi+; countAk.keysi+; forfor(j=1;jRADIX;j+) (j=1;j=0;k-) (k=n-1;k=0;k-) /從右端開始復(fù)制記錄從右端開始復(fù)制記錄 j=Ak.keysi;j=Ak.keysi; Bcountj-1=Ak;

54、 Bcountj-1=Ak; countj-; countj-; /for/for /RadixPass/RadixPass653.4 3.4 基數(shù)排序基數(shù)排序n 整個算法：整個算法：voidvoid RadixSort(SqList RadixSort(SqList &L) &L) RcdType RcdType CL.length; CL.length; /申請輔助空間申請輔助空間 i=L.bitsnumi=L.bitsnum-1;-1; whilewhile(i=0) (i=0) RadixPass RadixPass(L.r,C,L.length,i); (L.r,C,

55、L.length,i); /一趟基數(shù)排序，結(jié)果存人一趟基數(shù)排序，結(jié)果存人C C i-; i-; if if(i=0)(i=0) RadixPass RadixPass(C,L.r, L.length,i); (C,L.r, L.length,i); /一趟基數(shù)排序，結(jié)果存人一趟基數(shù)排序，結(jié)果存人L.rL.r i-; i-; /if/if elseelse for for(j=0;jL.length;j+)(j=0;jL.length;j+) / /排序后的結(jié)果若在排序后的結(jié)果若在C C中，復(fù)制到中，復(fù)制到L.rL.r L.rj=Cj;L.rj=Cj; /while/while /RadixSo

56、rt/RadixSortTypedef struct RcdType *r;int bitnum;int length;SqList 663.4 3.4 基數(shù)排序基數(shù)排序n時間復(fù)雜度：時間復(fù)雜度：n最佳狀況、最壞狀況、平均狀況：最佳狀況、最壞狀況、平均狀況：O(dO(d* *n)n)n空間復(fù)雜度：空間復(fù)雜度：n最佳狀況、最壞狀況、平均狀況：最佳狀況、最壞狀況、平均狀況：O(n)O(n) n優(yōu)點：優(yōu)點：n平均時間復(fù)雜度低；穩(wěn)定性排序。平均時間復(fù)雜度低；穩(wěn)定性排序。n缺點：缺點：n空間效率低?？臻g效率低。673.5 各種排序方法的綜合比較各種排序方法的綜合比較n3.5.1 3.5.1 時間性能時間

57、性能n3.5.2 3.5.2 空間性能空間性能n3.5.3 3.5.3 排序方法穩(wěn)定性能排序方法穩(wěn)定性能n3.5.4 3.5.4 小結(jié)小結(jié)683.5.1 3.5.1 時間性能時間性能n按平均的時間性能來分，有三類排序方法：按平均的時間性能來分，有三類排序方法：n時間復(fù)雜度時間復(fù)雜度O(nlognO(nlogn) )的方法有：快速排序、堆排序和歸并排的方法有：快速排序、堆排序和歸并排序，其中快速排序目前被認為是最快的一種排序方法，后兩者序，其中快速排序目前被認為是最快的一種排序方法，后兩者之比較，在之比較，在n n值較大的情況下，歸并排序較堆排序更快。值較大的情況下，歸并排序較堆排序更快。n時間

58、復(fù)雜度時間復(fù)雜度O(nO(n2 2 ) )的方法有：插入排序、起泡排序和選擇排的方法有：插入排序、起泡排序和選擇排序，其中以插入排序為最常用，特別是已按關(guān)鍵字基本有序排序，其中以插入排序為最常用，特別是已按關(guān)鍵字基本有序排列的記錄序列尤為如此，選擇排序過程中記錄移動次數(shù)最少。列的記錄序列尤為如此，選擇排序過程中記錄移動次數(shù)最少。n當待排記錄序列按關(guān)鍵字順序有序時，插入排序和起泡排序能當待排記錄序列按關(guān)鍵字順序有序時，插入排序和起泡排序能達到達到O(n)O(n)的時間復(fù)雜度；而對于快速排序而言，這是最不好的情的時間復(fù)雜度；而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為況，此時的時間性

59、能蛻化為O(O(n n2 2) )n選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變，人們應(yīng)事先對要排序的記錄關(guān)鍵字的分布情況字的分布而改變，人們應(yīng)事先對要排序的記錄關(guān)鍵字的分布情況有所了解，才可有所了解，才可1 1對癥下藥，選擇有針對性的排序方法。對癥下藥，選擇有針對性的排序方法。n當待排序記錄中其他各數(shù)據(jù)項比關(guān)鍵字占有更大的數(shù)據(jù)量時，當待排序記錄中其他各數(shù)據(jù)項比關(guān)鍵字占有更大的數(shù)據(jù)量時，還應(yīng)考慮到排序過程中移動記錄的操作時間，起泡排序效率最低。還應(yīng)考慮到排序過程中移動記錄的操作時間，起泡排序效率最低。693.5.2

60、3.5.2 空間性能空間性能n空間性能指的是排序過程中所需的輔助空間性能指的是排序過程中所需的輔助空間大小。空間大小。n所有的簡單排序方法（包括：插入、起泡和選擇所有的簡單排序方法（包括：插入、起泡和選擇排序）和堆排序的空間復(fù)雜度均為排序）和堆排序的空間復(fù)雜度均為O O（1 1）. .n快速排序為快速排序為O(lognO(logn),),為遞歸程序執(zhí)行過程中棧所為遞歸程序執(zhí)行過程中棧所需的輔助空間。需的輔助空間。n歸并排序和基數(shù)排序所需輔助空間最多，其空間歸并排序和基數(shù)排序所需輔助空間最多，其空間復(fù)雜度為復(fù)雜度為O(n)O(n)。703.5.3 3.5.3 排序方法穩(wěn)定性能排序方法穩(wěn)定性能n穩(wěn)定的排序方法指的是對于兩個關(guān)鍵字相等的穩(wěn)定的排序方法指的是對于兩個關(guān)鍵字相等的記錄在經(jīng)過排之后，不改變它們在排序之前在記錄在經(jīng)過排之后，不改變它