1、 第三章第三章 排排 序序（Sorting）2第三章第三章 排序排序n3.1 3.1 排序的基本概念排序的基本概念n3.2 3.2 簡單排序方法簡單排序方法n3.3 3.3 先進法排序方法先進法排序方法n3.4 3.4 基數排序基數排序n3.5 3.5 各種排序方法的綜合比較各種排序方法的綜合比較3第三章第三章 排序排序n待排序數據元素記錄的存儲結構：待排序數據元素記錄的存儲結構：ntypedef int KeyType /typedef int KeyType /定義關鍵字類型為定義關鍵字類型為整型整型ntypedef structtypedef structn KeyType key; K

2、eyType key; / /關鍵字項關鍵字項n InfoType otherinfo; /InfoType otherinfo; /其他數據項其他數據項nRcdType;RcdType; / /記錄類型記錄類型n本章的排序圖例只標出了記錄的關鍵字。本章的排序圖例只標出了記錄的關鍵字。43.1 3.1 排序的基本概念排序的基本概念n3.1.1 3.1.1 排序的定義排序的定義n3.1.2 3.1.2 排序的特性排序的特性穩定性與穩定性與不穩定性不穩定性n3.1.3 3.1.3 排序的分類排序的分類n3.1.4 3.1.4 內排序的特點內排序的特點n3.1.5 3.1.5 選擇排序法選擇排序法5

3、3.1 3.1 排序的基本概念排序的基本概念n3.1.1 3.1.1 排序的定義排序的定義n簡單定義：排序是按照關鍵字的非遞減簡單定義：排序是按照關鍵字的非遞減或非遞增順序對一組記錄重新進行整隊或非遞增順序對一組記錄重新進行整隊或排列的操作。或排列的操作。n數學定義：假設含有數學定義：假設含有n n個記錄的序列為：個記錄的序列為：nr1, r2, ,rnr1, r2, ,rn(3-1)(3-1)n它們的關鍵字相應為它們的關鍵字相應為k1, k2, ,kn,k1, k2, ,kn,對式對式(3-1)(3-1)的記錄序列進行排序就是要確定的記錄序列進行排序就是要確定序號序號1,2, ,n1,2,

4、,n的一種排列的一種排列p1, p2,pnp1, p2,pn使使其相應的關鍵字滿足如下的非遞增其相應的關鍵字滿足如下的非遞增( (減減) )關關系：系：nkp1 kp2 kpn kp1 kp2 kpn (3-2)(3-2)n也就是使式也就是使式(3-2)(3-2)的記錄序列重新排列成的記錄序列重新排列成一個按關鍵字有序的序列一個按關鍵字有序的序列rp1 rp2 rp1 rp2 rpn rpn (3-3) (3-3)63.1 3.1 排序的基本概念排序的基本概念n3.1.2 3.1.2 排序的特性排序的特性穩定性與不穩定性穩定性與不穩定性n當待排記錄中的關鍵字當待排記錄中的關鍵字ki(1,2,n

5、)ki(1,2,n)都不相同都不相同時，則任何一個記錄的無序序列經排序后得到的時，則任何一個記錄的無序序列經排序后得到的結果是惟一的。結果是惟一的。n簡單地說，穩定性排序簡單地說，穩定性排序-數據排序過后能使值數據排序過后能使值相同的數據，保持原順序中之相對位置。反之，相同的數據，保持原順序中之相對位置。反之，則稱為則稱為“不穩定性排序不穩定性排序” ” 。n若排序的序列中存在兩個或兩個以上關鍵字相若排序的序列中存在兩個或兩個以上關鍵字相等的記錄時，則排序得到的記錄序列的結果不惟等的記錄時，則排序得到的記錄序列的結果不惟一。一。n假設假設ki= kj (1i n, 1jn, ij )ki= k

6、j (1i n, 1jn, ij )，且，且在排序前的序列中在排序前的序列中 ri ri 領先于領先于rj (rj (即即ij ) ij ) 。若。若在排序后的序列中在排序后的序列中ri ri 總是領先于總是領先于rj rj ，則稱所用，則稱所用的排序方法是穩定的；反之，若可能使排序后的的排序方法是穩定的；反之，若可能使排序后的序列中序列中 rjrj領先于領先于ri ri ，則稱所用的排序方法是不，則稱所用的排序方法是不穩定的。穩定的。73.1.2 3.1.2 排序的特性排序的特性穩定性與不穩定性穩定性與不穩定性272716169 91 1）31317 724249 92 2）17170 01

7、 12 23 34 45 56 67 7 排序前：排序前：7 79 91 1） 9 92 2）161617172424272731310 01 12 23 34 45 56 67 7 穩定排序：穩定排序：7 79 92 2） 9 91 1）161617172424272731310 01 12 23 34 45 56 67 7 不穩定排序：不穩定排序：83.1.3 3.1.3 排序的分類排序的分類n根據在排序的過程涉及的存儲器不同，排序方根據在排序的過程涉及的存儲器不同，排序方法可分為兩類：法可分為兩類：n1.內部排序內部排序Internal Sort）：在排序進行的）：在排序進行的過程中不使

8、用計算機外部存儲器的排序過程。過程中不使用計算機外部存儲器的排序過程。n選擇排序選擇排序n插入排序插入排序n起泡排序起泡排序n快速排序快速排序n歸并排序歸并排序n堆排序堆排序n基數排序基數排序n2. 外部排序外部排序External Sort）：在排序進行的）：在排序進行的過程中需要對外存進行訪問的排序過程。過程中需要對外存進行訪問的排序過程。93.1.4 3.1.4 內排序的特點內排序的特點n 待排序記錄序列的存儲結構：待排序記錄序列的存儲結構：nconst int MAXSIZE=20 /const int MAXSIZE=20 /定義最大順序表的長度定義最大順序表的長度ntypedef

9、structtypedef structn RcdType rMAXSIZE+1;/r0 RcdType rMAXSIZE+1;/r0閑置或作為閑置或作為“哨兵哨兵”n int length; /int length; /順序表的真正長度順序表的真正長度nSqList;SqList; / /順序表類型順序表類型n 內部排序的過程是一個逐步擴大記錄的有序序列的過程。內部排序的過程是一個逐步擴大記錄的有序序列的過程。通常在排序的過程中，參與排序的記錄序列可劃分兩個區通常在排序的過程中，參與排序的記錄序列可劃分兩個區域：有序序列區和無序序列區，其中有序序列區的的記錄域：有序序列區和無序序列區，其中有

10、序序列區的的記錄已按關鍵字非遞減有序排列。已按關鍵字非遞減有序排列。n 使有序序列中記錄的數目至少增加一個的操作稱為一趟使有序序列中記錄的數目至少增加一個的操作稱為一趟排序。排序。103.1.5 選擇排序法選擇排序法n思想：在排序過程序中，依次從待排序的記錄序列中思想：在排序過程序中，依次從待排序的記錄序列中選擇出關鍵字值最小的記錄、關鍵字值次小的記錄、選擇出關鍵字值最小的記錄、關鍵字值次小的記錄、，并分別有序序列中的第并分別有序序列中的第1個位置、第二個位置、個位置、第二個位置、，最后剩下一個關鍵字值最大的記錄位于序列的最后一個最后剩下一個關鍵字值最大的記錄位于序列的最后一個位置，從而使待排

11、序的記錄序列成為按關鍵字值由小到位置，從而使待排序的記錄序列成為按關鍵字值由小到大排列的的有序序列。大排列的的有序序列。有序序列有序序列 R1.i-1R1.i-1無序序列無序序列 Ri.nRi.n有序序列有序序列 R1.i-1R1.i-1RjRjRiRi有序序列有序序列 R1.iR1.i無序序列無序序列 Ri+1.nRi+1.n一趟排序后一趟排序后一趟排序開始一趟排序開始113.1.5 選擇排序法選擇排序法n一趟排序算法：一趟排序算法：nvoid SelectPass(SqList &L,int i)void SelectPass(SqList &L,int i)n RcdTy

12、pe W; int j,k; RcdType W; int j,k;n j=i; / j j=i; / j指示無序序列中第一個記錄的位置指示無序序列中第一個記錄的位置 n for(k=i+1;k=L.length;k+)for(k=i+1;k=L.length;k+)nif(L.rk.keyL.rj.key) j=k; /if(L.rk.keyL.rj.key) j=k; /只記只記錄位置錄位置n if(i!=j) / if(i!=j) / 交換交換RjRj和和Ri; Ri; n W=L.ri; L.ri=L.rj; L.rj= W; W=L.ri; L.ri=L.rj; L.rj= W; n

13、 / L.ri L.rj; / L.ri L.rj; n / SelectPass / SelectPass123.1.5 選擇排序法選擇排序法n整個算法：整個算法：nvoid SelectSort(SqList &L)void SelectSort(SqList &L)n RcdType W; RcdType W;n for(i=1;iL.length;i+) for(i=1;iL.length;i+)n j=i; / j j=i; / j指示無序序列中第一個記錄的位指示無序序列中第一個記錄的位置置 n for(k=i+1;k=L.length;k+) /for(k=i+1;

14、k=L.length;k+) /找到最小找到最小記錄下標記錄下標n if(L.rk.keyL.rj.key) j=k; if(L.rk.keyL.rj.key) j=k; n if(i!=j) / if(i!=j) / 交換交換RjRj和和Ri; Ri; n W=L.ri; L.ri=L.rj; L.rj= W=L.ri; L.ri=L.rj; L.rj= W; W; n / for / for n / SelectSort / SelectSort133.1.5 選擇排序法選擇排序法初始狀態初始狀態491491383865654924927676131327275252i=1i=113133

15、8386565492492767649149127275252i=2i=2131327276565492492767649149138385252i=3i=3131327273838492492767649149165655252i=4i=4131327273838492492767649149165655252i=5i=5131327273838492492491491656552527676i=6i=6131327273838492492491491656576765252i=7i=7131327273838492492491491656576765252143.1.5 選擇排序法選擇排序

16、法n時間復雜度：時間復雜度：O(n2)O(n2)n空間復雜度：空間復雜度：O(1)O(1)n優點：優點：n算法簡單；輔助空間少。算法簡單；輔助空間少。n缺陷：缺陷：n效率低；不穩定性排序。效率低；不穩定性排序。153.2 簡單排序方法簡單排序方法n3.2.1 3.2.1 插入排序插入排序n3.2.2 3.2.2 起泡排序起泡排序163.2.1 插入排序插入排序n基本思想：依次將記錄序列中的每一個記錄插入到有序段中，使有基本思想：依次將記錄序列中的每一個記錄插入到有序段中，使有序段的長度不斷地擴大。其具體的排序過程可以描述如下：首先將待序段的長度不斷地擴大。其具體的排序過程可以描述如下：首先將待

17、排序記錄序列中的第一個記錄作為一個有序段，將記錄序列中的第二排序記錄序列中的第一個記錄作為一個有序段，將記錄序列中的第二個記錄插入到上述有序段中，形成由兩個記錄組成的有序段，再將記個記錄插入到上述有序段中，形成由兩個記錄組成的有序段，再將記錄序列中的第三個記錄插入到這個有序段中，形成由三個記錄組成的錄序列中的第三個記錄插入到這個有序段中，形成由三個記錄組成的有序段，有序段，依此類推，每一趟都是將一個記錄插入到前面的有序段中。依此類推，每一趟都是將一個記錄插入到前面的有序段中。n假設當前欲處理第假設當前欲處理第i個記錄，則將個記錄，則將Ri這個記錄插入到有序這個記錄插入到有序R1.i-1 段段中

18、，從而使有序序列長度增中，從而使有序序列長度增1，直到所有記錄都插入到有序段中。一共，直到所有記錄都插入到有序段中。一共需要經過需要經過n-1趟就可以將初始序列的趟就可以將初始序列的n個記錄重新排列成按關鍵字值大個記錄重新排列成按關鍵字值大小排列的有序序列。小排列的有序序列。RiRi有序序列有序序列 R1.iR1.i無序序列無序序列 Ri+1.nRi+1.n一趟排序后一趟排序后一趟排序開始一趟排序開始有序序列有序序列 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

19、36 69 93 36 69 94 43 34 46 69 9插入插入9 9插入插入3 3插入插入4 4起始起始183.2.1 插入排序插入排序n一趟排序算法：一趟排序算法：nvoid InsertPass(SqList &L,int i)void InsertPass(SqList &L,int i)n / /將將L.riL.ri插入有序的插入有序的R1.i-1R1.i-1中中n L.r0=L.ri; /L.r0=L.ri; /復制為哨兵復制為哨兵n for(j=i-1;L.r0.keyL.rj.key;j-for(j=i-1;L.r0.keyL.rj.key;j-)-)nL

20、.rj+1=L.rj; /L.rj+1=L.rj; /記錄后移記錄后移n L.rj+1= L.r0; /L.rj+1= L.r0; /插入到正確位插入到正確位置置n/InsertPass/InsertPass193.2.1 插入排序插入排序n整個算法：整個算法：nvoid InsertSort(SqList &L)void InsertSort(SqList &L)n / /將將L.riL.ri插入有序的插入有序的R1.i-1R1.i-1中中n for(i=2;i=L.length;i+)for(i=2;i=L.length;i+)n if(L.ri.keyL.ri-1.key

21、) if(L.ri.keyL.ri-1.key) n L.r0=L.ri; / L.r0=L.ri; /復制為哨兵復制為哨兵n for(j=i-for(j=i-1;L.r0.keyL.rj.key;j-)1;L.r0.keyL.rj.key;j-)n L.rj+1=L.rj; / L.rj+1=L.rj; /記錄后移記錄后移n L.rj+1= L.r0; /L.rj+1= L.r0; /插入到正確插入到正確位置位置n n/InsertSort/InsertSort203.2.1 插入排序插入排序初始狀態初始狀態491491383865659797767613132727492492i=2i=2

22、i=3i=3i=4i=4i=5i=5i=6i=6i=7i=7i=8i=8383849149165659797767613132727492492383849149165659797767613132727492492383865654914916565979776761313272749249238389797491491656576769797131327274924923838767649149138386565767697972727492492131313134914912727383865657676979749249213132727491491272738389797656576

23、764924921313492492213.2.1 插入排序插入排序n時間復雜度時間復雜度n最佳狀況正序）：最佳狀況正序）： O On n）n最壞狀況逆序）：最壞狀況逆序）：O(n2)O(n2)n平均狀況：平均狀況： O(n2)O(n2)n空間復雜度：空間復雜度：O(1)O(1)n優點：優點：n算法簡單；穩定排序。算法簡單；穩定排序。n缺陷：缺陷：n花費較長的排序時間。花費較長的排序時間。223.2.2 3.2.2 起泡排序起泡排序n思想：通過對無序序列區中的記錄進行相鄰記錄關鍵思想：通過對無序序列區中的記錄進行相鄰記錄關鍵字間的字間的“比較和記錄位置的比較和記錄位置的“交換實現關鍵字較小交換

24、實現關鍵字較小的記錄向的記錄向“一頭漂移，而關鍵字較大的記錄向一頭漂移，而關鍵字較大的記錄向“另一另一頭下沉，從而達到記錄按關鍵字非遞減順序有序排列頭下沉，從而達到記錄按關鍵字非遞減順序有序排列的目標。的目標。i i無序序列無序序列 R1.i-1R1.i-1有序序列有序序列 Ri.nRi.n一趟排序后一趟排序后一趟排序開始一趟排序開始無序序列無序序列 R1.iR1.i有序序列有序序列 Ri+1.nRi+1.n233.2.2 3.2.2 起泡排序起泡排序373796968 854548 854549696373796968 89696373754548 8969654548 83737243.2

25、.2 3.2.2 起泡排序起泡排序n一趟排序算法：一趟排序算法：nvoid BubblePass(SqList &L,int i)void BubblePass(SqList &L,int i)n RcdType W; RcdType W; n / j / j指示無序序列中第一個記錄的位置指示無序序列中第一個記錄的位置 n for(j=1;ji;j+)for(j=1;ji;j+)nif(L.rj+1.keyL.rj.key) /if(L.rj+1.key1;i-) for(i=L.length;i1;i-)n for(j=1;ji;j+) for(j=1;ji;j+)n if(

26、L.rj+1.keyL.rj.key) / if(L.rj+1.key1) while(i1)n lastExchange=1; lastExchange=1;n for(j=1;ji;j+) for(j=1;ji;j+)n if(L.rj+1.keyL.rj.key) / if(L.rj+1.key=pivotkeyRhigh.key=pivotkey，則減小，則減小highhighn否則將否則將RhighRhigh移至指針移至指針lowlow所指位置所指位置n檢測指針所指記錄檢測指針所指記錄n若若Rlow.key=pivotkeyRlow.key=pivotkey，則增加，則增加lowlo

27、wn否則將否則將RlowRlow移至指針移至指針highhigh所指位置所指位置n重復進行，直至重復進行，直至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 2555536361414656528283636333.3.1 3.3.1 快速排序快速排序n一趟排序算法：一趟排序算法：n

28、int Partition(RcdType R,int low,int high)int Partition(RcdType R,int low,int high)n int pivotkey; int pivotkey;n R0=Rlow; / R0=Rlow; /將樞軸放在閑置單元將樞軸放在閑置單元n pivotkey=Rlow.key; /pivotkey=Rlow.key; /將樞軸的關鍵字放在將樞軸的關鍵字放在pivotkeypivotkeyn while(lowhigh) while(lowhigh) n while(low=pivotkey) while(low=pivotkey

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

30、ow;/把比樞軸大的把比樞軸大的記錄移到高端記錄移到高端n /while/whilen Rlow=R0; / Rlow=R0; /把樞軸放在正確的位置把樞軸放在正確的位置n return(low) ; /return(low) ; /返回樞軸位置返回樞軸位置n/Partition/Partition343.3.1 3.3.1 快速排序快速排序n整個算法：整個算法：nvoid QSort(RcdType R,int s,int t)void QSort(RcdType R,int s,int t)n / /對記錄序列對記錄序列Rs.tRs.t進行快速排序進行快速排序n if(s=t-1) /if

31、(s11n pivotLoc=Partition(R,s,t); / pivotLoc=Partition(R,s,t); /對對Rs.tRs.t進行一進行一次劃分次劃分n QSort(R,s,pivotLoc-1); /QSort(R,s,pivotLoc-1); /對低端子序列遞歸排序對低端子序列遞歸排序n QSort(R,s,pivotLoc-1); /QSort(R,s,pivotLoc-1); /對高端子序列遞歸排序對高端子序列遞歸排序n /if/ifn/QSort/QSortnvoid QuickSort(SqList &L)void QuickSort(SqList &a

32、mp;L)n / /對順序表對順序表L L進行快速排序進行快速排序n QSort(L.r,1,L.length);QSort(L.r,1,L.length);n/QuickSort/QuickSort一趟快速排序示例一趟快速排序示例491491383865659797767613132727492492i ij jj j2727383865659797767613132727492492i ij ji i2727383865659797767613136565492492i ij jj j2727383813139797767613136565492492i ij ji i2727383813

33、139797767697976565492492i ij jj j272738381313491491767697976565492492pivotkeypivotkey491491363.3.1 3.3.1 快速排序快速排序初始狀態初始狀態491491383865659797767613132727492492一次劃分一次劃分272713137676767697974924926565491491383813133838767676769797492492656549149127271313383876767676979749249265654914912727131338387676767

34、697974924926565491491272713133838767676769797492492656549149127271313383876767676979749249265654914912727373.3.1 3.3.1 快速排序快速排序n時間復雜度：時間復雜度：n最佳狀況最佳狀況( (當每次分割的兩個區塊都均勻大小時當每次分割的兩個區塊都均勻大小時) )：O(nO(n* *log2n)log2n)n最壞狀況最壞狀況( (每次分割的兩個區塊大小相差很多時每次分割的兩個區塊大小相差很多時) )：O(n2)O(n2)n平均狀況：平均狀況： O(nO(n* *log2n)log2n)

35、n空間復雜度：使用遞歸的深度空間復雜度：使用遞歸的深度n最佳狀況最佳狀況: O(log2n): O(log2n)n最壞狀況最壞狀況: O(n): O(n)n平均狀況：介于平均狀況：介于O(log2n) O(log2n) 和和O(n)O(n)之間之間n優點：優點：n平均時間復雜度低，適用于完全隨機的序列。平均時間復雜度低，適用于完全隨機的序列。n缺陷：缺陷：n不穩定性排序不穩定性排序; ;空間效率低；結點順序不好則效率空間效率低；結點順序不好則效率低。低。383.3.2 歸并排序歸并排序n歸并排序法是利用歸并排序法是利用“歸并操作的一種排序方歸并操作的一種排序方法。法。n基本思想：基本思想：n將

36、待排序的原始記錄序列將待排序的原始記錄序列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，算法如，算法如下：下：nvoid Merge(RcdType SR,RcdType TR,int i,int v

37、oid Merge(RcdType SR,RcdType TR,int i,int m,int n)m,int n)n / /對有序的對有序的Ri.mRi.m和和Ri+1.nRi+1.n歸并為一個有序的歸并為一個有序的RnRnn for(j=m+1,k=i;i=m&j=n;k+) for(j=m+1,k=i;i=m&j=n;k+) n if(SRi.key=SRj.key) TRk=SRi+; if(SRi.key=SRj.key) TRk=SRi+;n else TRk=SRj+; else TRk=SRj+; n /for /forn while(i=m) TRk+=SRi

38、+; / while(i=m) TRk+=SRi+; /將剩余的將剩余的Ri.mRi.m復復制到制到TRTRn while(j=n) TRk+=SRj+; / while(jn/2=4（1考慮考慮n4n4 n8 不變不變67491382n1n2n3n4n5n6n7n88453.3.3 堆排序堆排序（2考慮考慮n3n3 n7 交換交換67491382n1n2n3n4n5n6n7n8267491382n1n2n3n4n5n6n7n862463.3.3 堆排序堆排序（3考慮考慮n2n4n2n5n2 不變不變27491386n1n2n3n4n5n6n7n89473.3.3 堆排序堆排序（4考慮考慮n1

39、n1 n2 交換交換29471386n1n2n3n4n5n6n7n8769471382n1n2n3n4n5n6n7n887493.3.3 堆排序堆排序考慮考慮n4n4n8 不變不變29481376n1n2n3n4n5n6n7n879 98 86 67 71 14 42 23 3最大堆最大堆503.3.3 堆排序堆排序29481376n1n2n3n4n5 n6n7n8n取出樹根取出樹根與最后一個節點交換與最后一個節點交換39n1n823481976n1n2n3n4n5 n6n7n8928471936n1n2n3n4n5 n6n7n89n1n7成堆成堆5128471936n1n2n3n4n5 n6

40、n7n893.3.3 堆排序堆排序n1n7n1n6成堆成堆8222471936n1n2n3n4n5 n6n7n89827431926n1n2n3n4n5 n6n7n898523.3.3 堆排序堆排序n1n6n1n5成堆成堆27431926n1n2n3n4n5 n6n7n8987424431926n1n2n3n4n5 n6n7n898726431924n1n2n3n4n5 n6n7n8987533.3.3 堆排序堆排序n1n5n1n4成堆成堆26431924n1n2n3n4n5 n6n7n89876121431924n1n2n3n4n5 n6n7n8987624431921n1n2n3n4n5

41、n6n7n89876543.3.3 堆排序堆排序n1n4n1n3成堆成堆24431921n1n2n3n4n5 n6n7n898764223421941n1n2n3n4n5 n6n7n89876422431941n1n2n3n4n5 n6n7n898764553.3.3 堆排序堆排序n1n3n1n2成堆成堆23421941n1n2n3n4n5 n6n7n8987641321421943n1n2n3n4n5 n6n7n898764322411943n1n2n3n4n5 n6n7n8987643563.3.3 堆排序堆排序n1n222411943n1n2n3n4n5 n6n7n89876431221

42、411943n1n2n3n4n5 n6n7n898764321 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 he

43、ap1heapi+1; /heapi+1; /借助借助temptemp交換交換 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) wh

44、ile(j=index&finish=0) if(jindex) 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; 堆排序算法堆排序算法調用調用HeapSort(list,index);HeapSort(list,index);583.3.3 堆排序堆排序n時間復雜度：時間復雜度：O(nlog2n)O(nlog

45、2n)n空間復雜度：空間復雜度：O(1)O(1)n優點：優點：n最壞情況下時間復雜度也僅為最壞情況下時間復雜度也僅為O(nlog2n) O(nlog2n) 。n缺陷：缺陷：n運行時間主要耗費在建初始堆和調整堆運行時間主要耗費在建初始堆和調整堆上，排序數據較少時，不值得提倡。上，排序數據較少時，不值得提倡。593.4 3.4 基數排序基數排序n基本思想：基本思想：n基數排序：假設記錄的邏輯關鍵字由多個關基數排序：假設記錄的邏輯關鍵字由多個關鍵字構成，每個關鍵字可能取鍵字構成，每個關鍵字可能取r r個值，則只要個值，則只要從最低位關鍵字起，按關鍵字的不同值將記錄從最低位關鍵字起，按關鍵字的不同值將

46、記錄“分配到分配到r r個隊列之后再個隊列之后再“搜集在一起，搜集在一起，如此重復趟，最終完成整個記錄序列的排序。如此重復趟，最終完成整個記錄序列的排序。“基數指的是基數指的是r r的取值范圍。的取值范圍。n例：關鍵字為三位整數，其關鍵字構成是例：關鍵字為三位整數，其關鍵字構成是k2, k1 , k0 k2, k1 , k0 ），）， k2, k1 , k0 k2, k1 , k0 的基數為的基數為1010n例：關鍵字為例：關鍵字為5 5個字母，其關鍵字構成是個字母，其關鍵字構成是（ k4, k3 , k2, k1 , k0 k4, k3 , k2, k1 , k0 ），）， kj,(0=j=

47、4) kj,(0=j-搜集搜集-分配分配-搜搜集集基基數數排排序序例例如如7878090963633030747489899494252505056969181883830 01 12 23 34 45 56 67 78 89 910101111（a a初始狀態初始狀態3030636383837474949425250505787818180909898969690 01 12 23 34 45 56 67 78 89 910101111（c c第一趟收集后的結果第一趟收集后的結果0505090918182525303063636969747478788383898994940 01 12 2

48、3 34 45 56 67 78 89 910101111（e e第二趟收集后的結果第二趟收集后的結果30300909898969690 01 12 23 34 45 56 67 78 89 9（b b第一趟分配后的結果第一趟分配后的結果25250505787818187474949463638383181894940 01 12 23 34 45 56 67 78 89 9（d d第二趟分配后的結果第二趟分配后的結果7474787883838989636369690505090925253030需要一個臨時需要一個臨時的二維數組存的二維數組存放分配結果嗎？放分配結果嗎？610 01 12 2

49、3 34 45 56 67 78 89 9101011113.4 3.4 基數排序基數排序7878090963633030747489899494252505056969181883830 01 12 23 34 45 56 67 78 89 910101111記錄數組記錄數組A A計數數組個位）計數數組個位）（a a初始狀態和對初始狀態和對“個位數計數的結果個位數計數的結果0 03 30 01 12 23 34 45 56 67 78 89 90 02 20 01 10 02 22 22 2計數數組累加計數數組累加1 112120 01 12 23 34 45 56 67 78 89 97

50、79 97 71 11 13 35 57 7記錄數組記錄數組B B303063638383747494942525050578781818090989896969（b b計數器的累加結果和記錄計數器的累加結果和記錄“復制后的狀態復制后的狀態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 基數排序基數排序（b b計數器的累加結果和記錄計數器的累加結果和記錄“復制后的狀復制后的狀態態303063638383747494942525050578781818090989896

51、9690 01 12 23 34 45 56 67 78 89 910101111計數數組十位）計數數組十位）1 11 10 01 12 23 34 45 56 67 78 89 92 22 22 22 21 11 10 00 0計數數組累加計數數組累加3 312120 01 12 23 34 45 56 67 78 89 99 911117 72 24 45 55 55 5記錄數組記錄數組A A050509091818252530306363696974747878838389899494（c c對對“十位數計數、累加和記錄十位數計數、累加和記錄“復制后的狀態復制后的狀態記錄數組記錄數組B

52、B6 610101 12 28 80 03 311117 79 95 54 4633.4 3.4 基數排序基數排序n基數排序需說明的數據結構基數排序需說明的數據結構nconst int MAX_NUM_OF_KEY=6 /const int MAX_NUM_OF_KEY=6 /關鍵字項數的最大值關鍵字項數的最大值nconst int RADIX=10 /const int RADIX=10 /關鍵字的基數關鍵字的基數nconst int MAXSIZE=10000 const int MAXSIZE=10000 ntypedef structtypedef structn KeysType k

53、eysMAX_NUM_OF_KEY; / KeysType keysMAX_NUM_OF_KEY; /關鍵字數組關鍵字數組n InfoType otheritems; /InfoType otheritems; /其他數據項其他數據項n /int bitsnum; /int bitsnum; /關鍵字的位數關鍵字的位數nRcdType; /RcdType; /基數排序中的記錄類型基數排序中的記錄類型643.4 3.4 基數排序基數排序n 一趟基數排序算法：一趟基數排序算法：nvoid RadixPass(RcdType A,RcdType B, int void RadixPass(RcdTy

54、pe A,RcdType B, int n,int i)n,int i)n / /對數組對數組A A中記錄關鍵字的中記錄關鍵字的“第第i i位計數，并累計位計數，并累計countcount的值的值n /將數組將數組A A中復制到數組中復制到數組B B中中n for(j=0;jRADIX;j+) countj=0; /for(j=0;jRADIX;j+) countj=0; /計數數組計數數組countcount初始化初始化n for(k=0;kn;k+) /for(k=0;kn;k+) /對關鍵字的對關鍵字的“第第i i位計數位計數n countAk.keysi+; countAk.keysi

55、+; n for(j=1;jRADIX;j+) / for(j=1;j=0;k-) / for(k=n-1;k=0;k-) /從右端開始復制記從右端開始復制記錄錄n j=Ak.keysi;j=Ak.keysi;n Bcountj-1=Ak; Bcountj-1=Ak;n countj-; countj-;n /for /forn/RadixPass/RadixPass653.4 3.4 基數排序基數排序n 整個算法：整個算法：nvoid RadixSort(SqList &L)void RadixSort(SqList &L)n RcdType CL.length; / Rcd

56、Type CL.length; /申請輔助空間申請輔助空間n i=L.bitsnum-1;i=L.bitsnum-1;n while(i=0) while(i=0) n RadixPass(L.r,C,L.length,i); / RadixPass(L.r,C,L.length,i); /一趟基數排序，結一趟基數排序，結果存人果存人C Cn i-; i-;n if(i=0) if(i=0)n RadixPass(C,L.r, L.length,i); / RadixPass(C,L.r, L.length,i); /一趟基數排序，一趟基數排序，結果存人結果存人L.rL.rn i-; i-;

57、n /if /ifn else elsen for(j=0;jL.length;j+) / for(j=0;jL.length;j+) /排序后的結果若在排序后的結果若在C C中，中，復制到復制到L.rL.rn L.rj=Cj; L.rj=Cj;n /while /whilen/RadixSort/RadixSortTypedef struct RcdType *r;int bitnum;int length;SqList 663.4 3.4 基數排序基數排序n時間復雜度：時間復雜度：n最佳狀況、最壞狀況、平均狀況：最佳狀況、最壞狀況、平均狀況：O(dO(d* *n)n)n空間復雜度：空間復雜

58、度：n最佳狀況、最壞狀況、平均狀況：最佳狀況、最壞狀況、平均狀況：O(n) O(n) n優點：優點：n平均時間復雜度低；穩定性排序。平均時間復雜度低；穩定性排序。n缺陷：缺陷：n空間效率低。空間效率低。673.5 各種排序方法的綜合比較各種排序方法的綜合比較n3.5.1 3.5.1 時間性能時間性能n3.5.2 3.5.2 空間性能空間性能n3.5.3 3.5.3 排序方法穩定性能排序方法穩定性能n3.5.4 3.5.4 小結小結683.5.1 3.5.1 時間性能時間性能n按平均的時間性能來分，有三類排序方法：按平均的時間性能來分，有三類排序方法：n時間復雜度時間復雜度O(nlogn)O(n

59、logn)的方法有：快速排序、堆排序和歸并排序，的方法有：快速排序、堆排序和歸并排序，其中快速排序目前被認為是最快的一種排序方法，后兩者之比較，其中快速排序目前被認為是最快的一種排序方法，后兩者之比較，在在n n值較大的情況下，歸并排序較堆排序更快。值較大的情況下，歸并排序較堆排序更快。n時間復雜度時間復雜度O(n2 )O(n2 )的方法有：插入排序、起泡排序和選擇排序，的方法有：插入排序、起泡排序和選擇排序，其中以插入排序為最常用，特別是已按關鍵字基本有序排列的記其中以插入排序為最常用，特別是已按關鍵字基本有序排列的記錄序列尤為如此，選擇排序過程中記錄移動次數最少。錄序列尤為如此，選擇排序過

60、程中記錄移動次數最少。n當待排記錄序列按關鍵字順序有序時，插入排序和起泡排序能當待排記錄序列按關鍵字順序有序時，插入排序和起泡排序能達到達到O(n)O(n)的時間復雜度；而對于快速排序而言，這是最不好的情的時間復雜度；而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為況，此時的時間性能蛻化為O(n2)O(n2)n選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵字的分布而改變，人們應事先對要排序的記錄關鍵字的分布情況字的分布而改變，人們應事先對要排序的記錄關鍵字的分布情況有所了解，才可有所了解，才可1 1對癥下藥，選擇有針對性的排序方法。對癥下藥，選擇有針對性的排序方法。n當待排序記錄中其他各數據項比關鍵字占有更大的數據量時，當待排序記錄中其他各數據項比關鍵字占有更大的