1、1第10章 內部排序210.1 概述10.2 插入排序10.3 快速排序10.4 選擇排序10.7 各種排序方法的綜合比較310.1 概 述一、排序的定義二、內部排序和外部排序三、內部排序方法的分類4一、什么是排序？排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。例如：將下列關鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 975 一般情況下，假設含n個記錄的序列為 R1, R2, ， Rn 其相應的關鍵字序列為 K1, K2, ，Kn

2、這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系 ： Kp1Kp2Kpn按此固有關系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。6二、內部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序； 反之，若參加排序的記錄數量很大， 整個序列的排序過程不可能在內存中 完成，則稱此類排序問題為外部排序。7三、內部排序的方法內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。經過一趟排序有序序列區無 序 序 列 區有序序列區無 序 序 列 區8基于不同的“擴大” 有序序列長度的方法，內部排序方法大致可分下列幾種類型：插入類交換類選擇類

3、 歸并類其它方法91. 插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。102. 交換類通過“交換”無序序列中的記錄從而得到其中關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。113. 選擇類從記錄的無序子序列中“選擇”關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。124. 歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5. 其它方法13待排記錄的數據類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長度typedef

4、int KeyType; / 關鍵字類型為整數類型typedef struct KeyType key; / 關鍵字項 InfoType otherinfo; / 其它數據項 RcdType; / 記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置 int length; / 順序表長度 SqList; / 順序表類型14 10. 2 插 入 排 序15有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n16實現“一趟插入排序”可分三步進行：3將Ri 插入(復制)到Rj+1的位置上。2將Rj+1.i

5、-1中的所有記錄均后移 一個位置；1在R1.i-1中查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；17直接插入排序（基于順序查找）表插入排序（基于鏈表存儲）不同的具體實現方法導致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）18一、直接插入排序利用 “順序查找”實現“在R1.i-1中查找Ri的插入位置”算法的實現要點：19從Ri-1起向前進行順序查找， 監視哨設置在R0；R0 = Ri; / 設置“哨兵”循環結束表明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找j=i-1

6、插入位置20 對于在查找過程中找到的那些關鍵字不小于Ri.key的記錄，并在查找的同時實現記錄向后移動；for (j=i-1; R0.keyRj.key; -j) Rj+1 = RjR0jRij= i-1上述循環結束后可以直接進行“插入”插入位置21令 i = 2，3，, n, 實現整個序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 如：1、2、4、3.22void InsertionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i=2; i=L.leng

7、th; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 復制為監視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置23 因為 R1.i-1 是一個按關鍵字有序的有序序列，則可以利用折半查找實現“在R1.i-1中查找Ri的插入位置”，如此實現的插入排序為折半插入排序。二、折半插入排序24void BiInsertionSort ( SqList &L ) / BInsertSort在 L.r1.i-1中折半查找插

8、入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.rhigh+1 = L.r0; / 插入2514 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r26low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key 1) / while / BubbleSorti = n;i

9、= lastExchangeIndex; / 本趟進行過交換的 / 最后一個記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;34注意:2. 一般情況下，每經過一趟“起泡”，“i 減一”，但并不是每趟都如此。例如:2553157989i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=21. 起泡排序的結束條件為， 最后一趟沒有進行“交換記錄”。3

10、5二、一趟快速排序（一次劃分）目標：找一個記錄，以它的關鍵字作為“樞軸”，凡其關鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 樞軸 (i+1jt)。36stlowhigh設 Rs=52 為樞軸 將 Rhigh.key 和 樞軸的關鍵字進行比較，要求Rhigh.key 樞軸的關鍵字 將 Rlow.key 和 樞軸的關鍵字進行比較，要求Rlow.key 樞軸的關鍵字high23low80high14low52例如R

11、052lowhighhighhighlow37 可見，經過“一次劃分” ，將關鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調整過程中，設立了兩個指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，并保證 Rhigh.key52，和 Rlow.key52,否則進行記錄的“交換”。38int Partition (RedType& R, int low, int high) pivotkey = Rlow.key;

12、while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回樞軸所在位置 / Partition39int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索Rlow = Rhi

13、gh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索Rhigh = Rlow;Rlow = R0; return low;40三、快速排序 首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進行快速排序41void QSort (RedType & R, int s, int t ) / 對記錄序列Rs.t進行快速排序 if (s t) / 長度大于1 / QSortpivotloc = Partition(R, s, t)

14、; / 對 Rs.t 進行一次劃分QSort(R, s, pivotloc-1); / 對低子序列遞歸排序，pivotloc是樞軸位置QSort(R, pivotloc+1, t); / 對高子序列遞歸排序42void QuickSort( SqList & L) / 對順序表進行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調用函數 Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。4310.4 選擇 排 序簡 單 選 擇 排 序堆 排 序44一、簡單選擇排序假設排序過程中，待排記錄序列的狀態為：有序序列R1.i-1無序序列

15、 Ri.n 第 i 趟簡單選擇排序從中選出關鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n45簡單選擇排序的算法描述如下：void SelectSort (Elem R, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; in; +i) / 選擇第 i 小的記錄，并交換到位 / SelectSortj = SelectMinKey(R, i); / 在 Ri.n 中選擇關鍵字最小的記錄if (i!=j) RiRj; / 與第 i 個記錄交換46二、堆排序堆是滿足下列性質的數列r1, r2, ，rn：或堆的定義:12, 36, 27, 65, 40, 34, 98

16、, 81, 73, 55, 49例如:是小頂堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆(小頂堆)(大頂堆)47rir2i r2i+1 若將該數列視作完全二叉樹，則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。1236276549817355403498例如:是堆14不48堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。例如：建大頂堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交換 98 和 12重新調整為大

17、頂堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 經過篩選49如何“建堆”？兩個問題:如何“篩選”？定義堆類型為:typedef SqList HeapType; / 堆采用順序表表示之50所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調整”根結點使整個二叉樹也成為一個堆。堆堆篩選5198814973556412362740例如:是大頂堆12但在 98 和 12 進行互換之后，它就不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較52建堆是一個從下

18、往上進行“篩選”的過程。40554973816436122798例如: 排序之前的關鍵字序列為123681734998817355 現在，左/右子樹都已經調整為堆，最后只要調整根結點，使整個二叉樹是個“堆”即可。984940643612275310.7 各種排序方法的綜合比較54一、時間性能1. 平均的時間性能基數排序時間復雜度為 O(nlogn)：快速排序、堆排序和歸并排序時間復雜度為 O(n2)：直接插入排序、起泡排序和簡單選擇排序時間復雜度為 O(n):552. 當待排記錄序列按關鍵字順序有序時3. 簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵字的分布而改變。 直接插入排序

19、和起泡排序能達到O(n)的時間復雜度， 快速排序的時間性能蛻化為O(n2) 。56二、空間性能指的是排序過程中所需的輔助空間大小1. 所有的簡單排序方法(包括：直接插入、起泡和簡單選擇) 和堆排序的空間復雜度為O(1)；2. 快速排序為O(logn)，為遞歸程序執行過程中，棧所需的輔助空間；573. 歸并排序所需輔助空間最多，其空間復雜度為 O(n);4. 鏈式基數排序需附設隊列首尾指針，則空間復雜度為 O(rd)。58三、排序方法的穩定性能 1. 穩定的排序方法指的是，對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經過排序之后，沒有改變。 2. 當對多關鍵字的記錄序列進行LSD方法排序時，必須采用穩定的排序方法。排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 59例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到結果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是穩定的;若排