中國計量學院數據結構第10章排序

1、第十章 內部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.6 基數排序基數排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.1 概概 述述一、何為排序一、何為排序二、內部排序和外部排序二、內部排序和外部排序三、內部排序方法的分類三、內部排序方法的分類一、何為排序？一、何為排序？將一組“無序無序”的記錄序列調整為“有序有序”的記錄序列。例如：將如下序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調整為14, 23, 36, 49, 52, 58, 61 ,75, 8

2、0, 97二、內部排序和外部排序二、內部排序和外部排序 整個排序過程不需要訪問外存不需要訪問外存便能完成，則為內部排序內部排序； 反之，若參加排序的記錄很多，整個排序過程不可能在內存中完成，稱為外部排序外部排序。三、內部排序的方法三、內部排序的方法內部排序內部排序的過程實質是一個逐步逐步擴大有序序列長度擴大有序序列長度的過程。經過一趟排序經過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)基于不同的“擴大擴大” 有序序列長度的方法，方法，內部排序內部排序大致可分下列幾種類型：插入類插入類交換類交換類選擇類選擇類歸并類歸并類其它方法其它方法1. 插入類插入類將無序子序列中的一個（

3、或幾個）“插入插入”到有序序列中，從而增加有序子序列的長度。2. 交換類交換類通過“交換交換”無序序列中的記錄以得到其中最小或最大記錄，將它加入到有序子序列中，從而增加有序子序列的長度。3. 選擇類選擇類從記錄的無序子序列中“選擇”最小或最大的記錄，將它加入到有序子序列中，從而增加有序子序列的長度。4. 歸并類歸并類 通過“歸并歸并”兩個或兩個以上的記錄有序子序列，逐步增加有序序列的長度。5. 其它方法其它方法 10. 2 插插 入入 排排 序序有序序列R1.i-1Ri無序序列 Ri.n插入排序的基本思想有序序列R1.i無序序列 Ri+1.n（一趟）（一趟）插入排序插入排序分三步走：分三步走：

4、3將Ri 插入插入到Rj+1的位置上。2將Rj+1.i-1中的所有記錄所有記錄均后移后移一個位置；1在R1.i-1中查找查找Ri的插入位置，即 R1.j.key Ri.key Rj+1.i-1.key；直接插入排序直接插入排序（基于順序查找）（基于順序查找）不同的實現方法導致不同的算法不同的實現方法導致不同的算法折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）一、直接插入排序一、直接插入排序利用 “順序查找順序查找”實現在R1.i-1中查找查找Ri的插入位置。void InsertionSort ( SqList &L )

5、 / 對順序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertionSortL.r0 = L.ri; / 設置監(jiān)視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置 因為 R1.i-1 是一個有序序列，因此可以利用折半查找折半查找在R1.i-1中找出Ri的插入位置。稱這種排序為折半插入排序折半插入排序。二、折半插入排序二、折半插入排序void BiInsertionSort ( S

6、qList &L ) / BiInsertionSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.rhigh+1 = L.r0; / 插入low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點在低半區(qū)else low = m+1; / 插入點在高半區(qū)三、希爾排序三、希爾排序(又稱縮小增量排序又稱縮小增量排序)也是一種插入排序方法

7、，但時間復雜度也是一種插入排序方法，但時間復雜度有較大改進有較大改進基本思想基本思想對無序序列先作對無序序列先作“宏觀宏觀”調整，后作調整，后作“微觀微觀”調整調整所謂所謂“宏觀宏觀”調整，指的是，調整，指的是，“跳躍式跳躍式”的插入排序的插入排序將序列分成若干子序列，對每個子序列進行插入排序。其中，d 稱為增量，它的值在排序過程中逐漸縮小，直至為 1 例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 增量為增量為5 5原始序列原始序列818194941111969612123

8、5351717959528285858414175751515子序列子序列1 18181 3535 4141 子序列子序列2 29494 1717 7575 子序列子序列3 31111 9595 1515子序列子序列4 49696 2828 子序列子序列5 51212 5858 結果結果子序列子序列1 13535 4141 8181 子序列子序列2 21717 7575 9494 子序列子序列3 31111 1515 9595子序列子序列4 42828 9696 子序列子序列5 51212 5858 原始序列原始序列353517171111282812124141757515159696585

9、8818194949595增量為增量為3 3原始序列原始序列35171128124175159658819495子序列子序列1 135 28 75 58 95子序列子序列2 217 12 15 81 子序列子序列3 311 41 96 94 結果結果子序列子序列1 128 35 58 75 95子序列子序列2 212 15 17 81 子序列子序列3 311 41 94 96 原始序列原始序列28121135154158179475819695增量為增量為1 1原始序列原始序列28121135154158179475819695子序列子序列1 1111215172834415875819495

10、96void ShellInsert ( SqList &L, int d ) for ( i=d+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=d) L.rj+d = L.rj; / 記錄后移，查找插入位置 L.rj+d = L.r0; / 插入 / if / ShellInsertvoid ShellSort (SqList &L, int delta, int t) / 增量為delta的希爾排序 for (k=0; kt; +t) ShellInsert(L, deltak); /一趟增量為deltak的插

11、入排序 / ShellSort 首先對無序序列進行“劃分劃分”，之后將兩個子序列“遞歸遞歸”進行快速排序進行快速排序。無 序 的 記 錄 序 列無序子序列 1無序子序列 2樞軸樞軸劃分分別進行快速排序10.3 快快 速速 排排 序序int partition(int a, int left, int right) /劃分劃分 int low = left; int high = right; int key = alow; /第一個記錄作為樞軸第一個記錄作為樞軸 while(low high) while(low = key) high-; alow = ahigh; /將比樞軸小的移到低端將

12、比樞軸小的移到低端 while(low high & alow = right) return; s=partition(a, left, right); Qsort(a, left, s-1); /排序前半部分排序前半部分 Qsort(a, s+1, right); /排序后半部分排序后半部分10.4 選選 擇擇 排排 序序簡 單 選 擇 排 序堆 排 序樹 形 選 擇 排 序一、簡單選擇排序一、簡單選擇排序有序序列R1.i-1無序序列 Ri.n 第第 i 趟趟從中選出最小的記錄有序序列R1.i無序序列 Ri+1.nvoid SelectSort (Elem R, int n ) /

13、 對記錄序列R1.n作簡單選擇排序。 for (i=1; in; +i) / SelectSortj = SelectMinKey(R, i); / 在 Ri.n 中選擇最小的記錄if (i!=j) RiRj; /交換交換二、樹形選擇排序二、樹形選擇排序按照錦標賽思想進行的選擇排序。三、堆排序三、堆排序堆滿足下列性質的序列r1, r2, ，rn：或或122iiiirrrr122iiiirrrr12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如例如:是是小頂堆小頂堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是

14、堆(小頂堆小頂堆)(大頂堆大頂堆)rir2i r2i+1 若將該序列視作完全二叉樹，則 r2i 是 ri 的左孩子， r2i+1 是 ri 的右孩子。1236276549817355403498例如例如:是堆是堆14不不堆排序堆排序 小頂（根）堆 堆頂是最小值，輸出并從堆上刪除， 調整剩余的n-1個數據元素序列，使之再次成為小頂堆，即可得到次小值 如此反復執(zhí)行，便能得到一個有序序列 大頂（根）堆 堆排序的步驟 建立堆 刪除根（具有最小/大值） 根和最后一個元素交換（不再是堆） 篩選：調整完全二叉樹，使之成為堆所謂“篩選篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調整調整”根結點根結點使

15、整個二叉樹也成為一個堆。堆堆篩選篩選98814973556412362740例如例如:是大頂堆是大頂堆12但在 98 和 12 進行互換之后，它就不不是堆了，因此，需要對它進行“篩選”。98128173641298比較交換建堆是一個從下往上進行建堆是一個從下往上進行“篩選篩選”的過程。的過程。40554973816436122798例如例如: 排序之前的關鍵字序列為123681734998817355 現在，左/右子樹都已經調整為堆，最后只要調整根結點，使整個二叉樹是個“堆”即可。98494064361227從哪個結點開始篩選？從哪個結點開始篩選？最后一個非葉子結點最后一個非葉子結點堆排序即是

16、利用堆排序即是利用堆的特性堆的特性對記錄序列對記錄序列進行排序的一種排序方法。進行排序的一種排序方法。例如：例如：建大頂堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交換 98 和 12重新調整為大頂堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 經過篩選定義堆類型為定義堆類型為:typedef SqList HeapType; / 采用順序表表示 void HeapAd

17、just (RcdType &R, int s, int m) / 已知 Rs.m中記錄的關鍵字除 Rs 之外均 / 滿足堆的特征，本函數自上而下調整 Rs 的 / 關鍵字，使 Rs.m 也成為一個大頂堆 / HeapAdjustrc = Rs; / 暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調整 Rs = Rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調整if ( jm & Rj.key0; -i ) HeapAdjust

18、 ( H.r, i, H.length ); / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當前無序序列 / H.r1.i中最后一個記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對 H.r1 進行篩選10.5 歸歸 并并 排排 序序歸并排序的過程基于下列基本思基本思想想： 將兩個或兩個以上的有序子序列 “歸并”為一個有序序列。通常采用的是2-路歸并排序。即：將兩個位置相鄰位置相鄰的有序子序列歸并為一個一個有序序列。有有 序序 序序 列列 Ri.n有序子序列有序子序列 Ri.m有序子序列有序子序列 Rm+1.n這個操作

19、對順序表而言，是輕而易舉的。SRmm+1nTR12ikj15292240 516063418470for (k=i, j=m+1; i=m & j=n; +k) / 將SR中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的記錄序列 SRi.m 和 SRm+1.n / 歸并為有序的記錄序列 TRi.n / Mergefor (k=i, j=m+1; i=m & j=n;

20、+k) / 將SR中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的 SRi.m 復制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復制到 TR歸并排序的算法歸并排序的算法如果無序序列 Rs.t 的兩部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分別按關鍵字有序，則利用上述歸并算法很容易將它們歸并成整個序列是一個有序序列。 因此，應該先分別對這兩部分進行 2-路歸并排序。例如：例如：52, 23, 80, 3

21、6, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23歸歸并并歸歸并并void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將SRs.t 歸并排序為 TR1s.t if (s= =t) TR1s=SRs; else / Msort m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2,

22、 s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.tvoid MergeSort (SqList &L) / 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對 n 個記錄進行歸并排序的時間復雜度為(nlogn)。即： 每一趟歸并的時間復雜度為 O(n)， 總共需進行 log2n 趟。10.6 基

23、基 數數 排排 序序基數排序基數排序是一種借助“多關鍵字排序”的思想來實現“單關鍵字排序”的內部排序算法。多關鍵字的排序多關鍵字的排序鏈式基數排序鏈式基數排序一、多關鍵字的排序一、多關鍵字的排序 n 個記錄的序列個記錄的序列 R1, R2, ，Rn對關鍵字對關鍵字 (Ki0, Ki1, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被稱為被稱為 “最主最主”位關鍵字位關鍵字Kd-1 被稱為被稱為 “最次最次”位關鍵字位關鍵字 對于序列中任意兩個記錄 Ri 和 Rj(1ijn) 都滿足滿足下列(詞典詞典)有序有序關系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1

24、, , ,Kjd-1) )多關鍵字排序通常有兩種做法最低位優(yōu)先最低位優(yōu)先LSD法法最高位優(yōu)先最高位優(yōu)先MSD法 先對先對K0進行排序進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關鍵字排序完直至最后對最次位關鍵字排序完成為止成為止。 先對 Kd-1 進行排序，然后對 Kd-2 進行排序， .，依次類推，直至對直至對最主位關鍵字最主位關鍵字 K0 排序完成為止排序完成為止。假設假設學生記錄含三個關鍵字:系別系別、班號班號和班內的序列號班內的序列號，其中以系別為最主位關鍵字。LSD的排序過程如下: 無序序列無序序列對對K2排序排

25、序對對K1排序排序對對K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30二、鏈式基數排序二、鏈式基數排序假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配分配- -收集收集”的方法，其好處是不需要進行關鍵字間的比較。對于數字型或字符型的單關鍵字單關鍵字，可以看成看成是由多個數位或多個字符構成的多關鍵多關鍵字字，采用采用這種“分配分配- -收集收集”的辦法

26、進行排序進行排序，稱作基數排序法稱作基數排序法。例如：例如：對下列這組關鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個位數”取值分別為 0, 1, , 9“分配分配” 成 10 組，之后按從 0 至 9 的順序將它們 “收集” 在一起； 然后按其 “十位數”取值分別為 0, 1, , 9 “分配分配” 成 10 組，之后再按從 0 至 9 的順序將它們 “收集收集” 在一起；最后按其“百位數”重復一遍上述操作。實現基數排序時，為減少輔助存儲空間，應采用鏈表作存儲結構，即鏈式基數排序，具體作法為： 待排序記錄以指針相鏈，構成一個鏈表；

27、“分配” 時，按當前“關鍵字位”取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中的“關鍵字位” 相同；“收集”時，按當前關鍵字位取值從小到大將各隊列首尾相鏈，構成一個鏈表;對每個關鍵字位均重復 2 和 3 兩步。例如：p369367167239237138230139進行第一次分配進行第一次分配進行第一次收集進行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138368239139369 239139138進行第二次分配進行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368進行第二次收集 進行第三次收集之后便得到記錄的有序序列進行第三次收集之后便得到記錄的有序序列f1 r1p230237138239139367167368進行第三次分配進行第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368 基數排序的時間復雜度為基數排序的時間復雜度為O(d(n+rd)其中：分配為O(n) 收集為O(rd)(rd為“基”) d為“分配-收集”的趟數10.7 各種