1、第十章 內(nèi)部排序10.1 概述10.2 插入排序10.3 交換排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序10.7 各種內(nèi)部排序方法比較10.8 例題解析110.1 概述10.1.1 什么是排序 是根據(jù)記錄關(guān)鍵字的值的遞增(遞減)的關(guān)系將多個(gè)記錄的次序重新排列。定義： 設(shè)有含n個(gè)記錄的文件 R1, R2,., Rn， 對(duì)應(yīng)的關(guān)鍵字序列為 K1, K2,., Kn， 求一個(gè)置換 p1,p2,.,pn 使文件按關(guān)鍵字有序 Rp1, Rp2,., Rpn， 滿足 Kp1 Kp2. Kpn 或 Kp1 Kp2 . Kpn210.1.2 排序的分類根據(jù)排序時(shí)文件記錄的存放位置： 內(nèi)部排序：

2、排序過(guò)程中將全部記錄放在內(nèi)存中處理。 外部排序：排序過(guò)程中需在內(nèi)外存之間交換信息。根據(jù)排序前后相同關(guān)鍵字記錄的相對(duì)次序： 穩(wěn)定排序：設(shè)文件中任意兩個(gè)記錄的關(guān)鍵字值相同，即Ki=Kj(ij)，若排序之前記錄Ri領(lǐng)先于記錄Rj ，排序后這種關(guān)系不變(對(duì)所有輸入實(shí)例而言)。 不穩(wěn)定排序：只要有一個(gè)實(shí)例使排序算法不滿足穩(wěn)定性要求。3根據(jù)文件的存儲(chǔ)結(jié)構(gòu)劃分排序的種類 連續(xù)順序文件排序 鏈表排序 地址排序: 待排記錄順序存儲(chǔ)，排序時(shí)只對(duì)輔助 表(關(guān)鍵字+指針)的表目進(jìn)行物理重排。根據(jù)排序中使用的主要方法 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序根據(jù)排序算法所需的輔助空間 就地排序： O(1) 非就

3、地排序： O(n)或與n有關(guān) 410.1.3 評(píng)價(jià)排序算法的主要標(biāo)準(zhǔn) 時(shí)間開銷 考察算法的兩個(gè)基本操作的次數(shù)：比較關(guān)鍵字移動(dòng)記錄 算法時(shí)間還與輸入實(shí)例的初試狀態(tài)有關(guān)時(shí)，分情況：最好最壞平均空間開銷 所需的輔助空間討論約定：(1)連續(xù)順序文件 (2)關(guān)鍵字非遞減TYPE list = ARRAY 0 . maxn OF RECORD key : keytype; . . . . . . END;var r: list510.2 插入排序10.2.1 直接插入排序（增量法） 示例 R(0) R(-4) R(8) R(1) R(-4) R(-6) n=6 i=1 0 -4 8 1 -4 -6 i=2

4、 -4 0 8 1 -4 -6 i=3 -4 0 8 1 -4 -6 i=4 -4 0 1 8 -4 -6 i=5 -4 -4 0 1 8 -6 i=6 -6 -4 -4 0 1 8 算法思想 每次使有序區(qū)增加一個(gè)記錄穩(wěn)定排序6算法步驟 0 1 i-1 i i+1 nr0.n ri (有序區(qū)) (無(wú)序區(qū))循環(huán)(n-1)次，初值 i=21) 把第i個(gè)記錄取出保存在r0中，j=i-1 2 )若r0 rj，則rj后移一位，j=j-1，轉(zhuǎn)2)； 否則r0放在rj+1處，i=i+1，轉(zhuǎn)1)7哨兵/監(jiān)視哨的作用 簡(jiǎn)化邊界條件的測(cè)試，提高算法時(shí)間效率。性能分析最好情況(原始數(shù)據(jù)按正序即非遞減序排列) Cmi

5、n=n-1 Mmin= 2(n-1)最壞情況(原始數(shù)據(jù)按逆序即非遞增序排列) Cmax=(n+2)(n-1)/2 Mmax=(n+4)(n-1)/2隨機(jī)情況 Cavg=(Cmin+ Cmax)/2n2/4 Mavg n2/4時(shí)間復(fù)雜度O(n2) 輔助空間復(fù)雜度O(1)8改進(jìn)措施折半插入排序 O(n2) 算法思想：將循環(huán)中每一次在區(qū)間 1,i-1 上為確定插入位置的順序查找操作改為折半查找操作。 效果：減少關(guān)鍵字間的比較次數(shù)。2-路插入排序 O(n2) 算法思想：設(shè)置與r同樣大小的輔助空間d，將r1賦值給d1，將d看作循環(huán)向量。對(duì)于ri (2in)，若rid1，則插入d1之后的有序序列中，反之則

6、插入d1之前的有序序列中。(避免r1關(guān)鍵字最小/最大) 效果：減少記錄的移動(dòng)次數(shù)。表插入排序 O(n2) 算法思想：采用靜態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)。 若要利用折半查找，需將記錄按序重排。9算法要點(diǎn)是穩(wěn)定排序更適合于原始記錄基本呈正序的情況算法思想也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1010.2.2 希爾排序(漸減/縮小增量排序)算法思想的出發(fā)點(diǎn)直接插入排序在待排序列的關(guān)鍵字基本有序時(shí)，效率較高在待排序的記錄個(gè)數(shù)較少時(shí)，效率較高算法思想 先選定一個(gè)記錄下標(biāo)的增量d，將整個(gè)記錄序列按增量d從第一個(gè)記錄開始劃分為若干組，對(duì)每組使用直接插入排序的方法；然后減小增量d，不斷重復(fù)上述過(guò)程，如此下去，直到d=1(此時(shí)整個(gè)序列是一

7、組)。11 示例 46 82 52 40 67 31 40 73 d1=4 46 67 31 82 40 52 40 73 46 31 40 40 67 82 52 73 d2=2 40 46 52 67 31 40 73 82 40 31 46 40 52 73 67 82 d3=1 31 40 40 46 52 67 73 82 31 40 40 46 52 67 73 82不穩(wěn)定排序4組2組1組12性能分析時(shí)間復(fù)雜度是n和d的函數(shù)實(shí)驗(yàn)結(jié)果：當(dāng)n較大時(shí)，比較和移動(dòng)次數(shù)約在n1.25到1.6n1.25。就地排序算法要點(diǎn)是不穩(wěn)定排序算法的時(shí)間性能優(yōu)于直接插入排序如何選擇最佳d序列，目前尚未解決

8、最后一個(gè)增量值必須為1避免增量序列中的值（尤其是相鄰的值）有公因子不宜在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)1310.3 交換排序10.3.1 起泡排序(冒泡排序)算法思想 將兩個(gè)相鄰記錄的關(guān)鍵字進(jìn)行比較，若為逆序則交換兩者位置，小者往上浮，大者往下沉。算法步驟 記錄1和2、2和3、(n-1)和n的關(guān)鍵字比較(交換)； 記錄1和2、2和3、(n-2)和(n-1)的關(guān)鍵字比較(交換)； 直到某一趟不出現(xiàn)交換操作為止。14 示例 0 -4 -4 -6 -6 -4 0 -6 -4 -4 8 -6 -4 -4 -4 -6 -4 0 0 0 -4 1 1 1 1 1 8 8 8 8 sorted F F F T穩(wěn)定排序1

9、5性能分析最好情況(原始數(shù)據(jù)按正序即非遞減序排列) Cmin=n-1 Mmin=0最壞情況(原始數(shù)據(jù)按逆序即非遞增序排列) Cmax=n(n-1)/2 Mmax=3n(n-1)/2時(shí)間復(fù)雜度O(n2) 輔助空間復(fù)雜度O(1)算法的改進(jìn)每趟排序中，記錄最后一次發(fā)生交換的位置雙向交替掃描，下上，最輕升頂；上下，最重沉底算法要點(diǎn)是穩(wěn)定排序移動(dòng)記錄次數(shù)較多，平均時(shí)間性能比直接插入排序差也可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1610.3.2 快速排序(分劃交換排序/分治法)分治算法原理1)分解：將原問(wèn)題分解為若干子問(wèn)題2)求解：遞歸地解各子問(wèn)題，若子問(wèn)題的規(guī)模足夠小，則直接求解3)組合：將各子問(wèn)題的解組合成原問(wèn)題的解快速

10、排序算法思想 指定樞軸/支點(diǎn)/基準(zhǔn)記錄rp(通常為第一個(gè)記錄)，通過(guò)一趟排序?qū)⑵浞旁谡_的位置上，它把待排記錄分割為獨(dú)立的兩部分，使得 左邊記錄的關(guān)鍵字rp.key右邊記錄的關(guān)鍵字 對(duì)左右兩部分記錄序列重復(fù)上述過(guò)程，依次類推，直到子序列中只剩下一個(gè)記錄或不含記錄為止。(可以用遞歸方法實(shí)現(xiàn))17 示例 (49) 38 65 97 76 13 27 49 x=49 i j 27 38 65 97 76 13 ( ) 49 i j 27 38 ( ) 97 76 13 65 49 i j 27 38 13 97 76 ( ) 65 49 i j 27 38 13 ( ) 76 97 65 49 i

11、j 27 38 13 49 76 97 65 49 (i =j)18性能分析最壞情況(原始數(shù)據(jù)正/逆序排列) Cmax=n(n-1)/2 Mmax Cmax O(n2)最好情況：每次劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無(wú)序子區(qū)間的長(zhǎng)度大致相等 Cmin O(nlog2n) Mmin Cmin O(nlog2n)平均時(shí)間性能 Tavg(n)=kn ln(n) k：某個(gè)常數(shù)； n：待排序序列中記錄個(gè)數(shù)輔助空間復(fù)雜度 取決于遞歸深度 最好情況 O(log2 n) 最壞情況 O(n)19算法要點(diǎn)非穩(wěn)定排序 反例 2，2，1 ：1 2 2 就平均時(shí)間而言，快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法。樞軸記錄的合

12、理選擇可改善性能。例如，三者取中隨機(jī)產(chǎn)生難于在單向鏈表結(jié)構(gòu)上實(shí)現(xiàn)2010.4 選擇排序10.4.1 簡(jiǎn)單選擇排序(直接選擇排序)算法步驟 第1趟：從n個(gè)記錄中選關(guān)鍵字最小的記錄，與 第1個(gè)記錄交換； 第2趟：從剩余的n-1個(gè)記錄中選關(guān)鍵字最小的 記錄，與第2個(gè)記錄交換； 第i趟：從剩余的n-i+1個(gè)記錄中選關(guān)鍵字最小的 記錄，與第i個(gè)記錄交換； 直到第n-1趟執(zhí)行完為止。21 示例 （n=8） 49 38 65 97 76 49 13 27 13 38 65 97 76 49 49 27 13 27 65 97 76 49 49 38 13 27 38 97 76 49 49 65 13 27

13、 38 49 76 97 49 65 13 27 38 49 49 97 76 65 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 （每趟排序使有序區(qū)增加一個(gè)記錄）不穩(wěn)定排序22性能分析總的比較次數(shù)與記錄排列的初始狀態(tài)無(wú)關(guān) C=(n-1)+(n-2)+.+2+1=n(n-1)/2移動(dòng)次數(shù) 初始記錄逆序時(shí)：Mmax = 3(n-1) 初始記錄正序時(shí)：Mmin = 0平均時(shí)間復(fù)雜度O(n2) 輔助空間復(fù)雜度O(1)算法要點(diǎn)是不穩(wěn)定排序當(dāng)一個(gè)記錄占用的空間較多時(shí)，此方法比直接插入排序快可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2310.4.2 樹形選擇排序(錦標(biāo)賽排序)算法

14、思想 錦標(biāo)賽名次產(chǎn)生過(guò)程。 較簡(jiǎn)單選擇排序減少“比較”次數(shù)。示例 23 23 40 38 23 40 46 38 23 38 40 時(shí)間復(fù)雜度 每次都走樹的一條分支， O( n log2 n )。缺陷 輔助空間較多；需與“最大值”進(jìn)行多余的比較233838383846383838 464040 4646 穩(wěn)定排序2410.4.3 堆排序特點(diǎn)較直接選擇排序減少重復(fù)比較；較樹形選擇排序減少輔助存儲(chǔ)空間(僅需一個(gè))堆的概念(二叉)堆的定義：n個(gè)關(guān)鍵字的序列（ k1, k2,., kn）當(dāng)且僅當(dāng)滿足下列條件之一： (1)KiK2i 且 KiK2i+1 小根堆 (2)KiK2i 且 KiK2i+1 大根

15、堆 則稱該序列為一個(gè)堆。堆的存儲(chǔ)結(jié)構(gòu) 對(duì)應(yīng)于完全二叉樹的順序存儲(chǔ) ( i=1,2,.,n/2 )96832738119堆頂大根堆示例96 83 27 38 11 925堆排序基本思想將初始文件R1.n建成一個(gè)大根堆；第1趟：將關(guān)鍵字最大的記錄(堆頂)R1與無(wú)序區(qū) 的最后一個(gè)記錄Rn交換；再將新的無(wú)序 區(qū)R1.n-1調(diào)整為堆；第2趟：將R1與Rn-1交換； 再將新的無(wú)序區(qū)R1.n-2調(diào)整為堆；.第i趟：將R1與Rn-i+1交換； 再將新的無(wú)序區(qū) R1.n-i調(diào)整為堆；.直到執(zhí)行完第(n-1)趟為止。 R126算法步驟將剩余元素調(diào)整為一個(gè)新堆 1)將堆頂元素作為當(dāng)前結(jié)點(diǎn)位置； 2)若當(dāng)前結(jié)點(diǎn)無(wú)左子

16、結(jié)點(diǎn)，結(jié)束調(diào)整； 否則，比較當(dāng)前結(jié)點(diǎn)與其左右孩子的關(guān)鍵字值 3)若前者后者，則結(jié)束調(diào)整； 否則，前者與后者中關(guān)鍵字值較大的結(jié)點(diǎn)交換位置，前 者交換后的位置作為當(dāng)前結(jié)點(diǎn)位置，轉(zhuǎn)2) 67 80 80 80 75 67 75 76 75 篩選法49 76 65 49 49 76 65 49 49 67 65 49堆堆27 將初始記錄序列R1.n建成大根堆 方法：依次把以i=n/2，n/2-1，n/2-2，.，1為根的子樹調(diào)整為堆，則完成了整個(gè)建堆的過(guò)程。算法分析最壞情況O(nlog2n)建初始堆時(shí)，比較次數(shù)4n反復(fù)調(diào)整堆時(shí)，比較次數(shù)2nlog2n 實(shí)驗(yàn)表明：平均性能接近于最壞性能O(nlog2n)

17、輔助空間復(fù)雜度：O(1)算法要點(diǎn)不穩(wěn)定排序初始建堆所需比較次數(shù)較多，因此記錄數(shù)較少時(shí)不宜采用在最壞情況下時(shí)間性能優(yōu)于快速排序2810.5 歸并排序(合并排序)歸并的概念 指將兩個(gè)或兩個(gè)以上的同序序列歸并成一個(gè)序列的操作。10.5.1 兩路歸并排序算法思想第1趟：將待排序列R1.n看作n個(gè)長(zhǎng)度為1的有序子序列，兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列(或最后一個(gè)子序列長(zhǎng)度為1)；第2趟：將上述n/2個(gè)有序子序列兩兩歸并；.直到合并成一個(gè)序列為止。29示例 (n=7) (49) (38) (65) (97) (76) (49) (13) (38 49) (65 97) (49 76) (13)

18、(38 49 65 97) (13 49 76) (13 38 49 49 65 76 97)性能分析任何情況時(shí)間復(fù)雜度O(nlog2n)輔助空間復(fù)雜度O(n)算法要點(diǎn)是穩(wěn)定排序若采用單鏈表作為存儲(chǔ)結(jié)構(gòu)，可實(shí)現(xiàn)就地排序很少用于內(nèi)部排序穩(wěn)定排序3010.5.2 自然兩路歸并排序特點(diǎn) 以游程(自然的有序段)作為子序列進(jìn)行歸并，可以比直接兩路歸并更有效。示例 503 87 512 61 908 170 897 275 653 426 154 512 503 512 61 275 897 908 170 653 512 426 154 87 87 154 426 503 512 512 653 908

19、 897 275 170 61 61 87 154 170 275 426 503 512 512 653 897 908不穩(wěn)定排序3110.6 基數(shù)排序(分配排序)特點(diǎn) 通過(guò)“分配”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序，時(shí)間復(fù)雜度可以突破基于關(guān)鍵字比較一類方法的下界O(nlgn)，達(dá)到O(n) 。方法借助多關(guān)鍵字排序的思想對(duì)單關(guān)鍵字排序多關(guān)鍵字排序示例 撲克牌排序(點(diǎn)數(shù)+花色) 花色： 點(diǎn)數(shù)：23QKA 最高位優(yōu)先法：按花色分成4堆； （MSD法） 對(duì)每一堆：按面值分堆； 從小到大排序； 按花色從小到大排序32最低位優(yōu)先法：按點(diǎn)數(shù)大小分成13堆； （LSD法） 按點(diǎn)數(shù)從小到大收集起來(lái)； 再按花色分成四堆

20、； 按花色從小到大收集起來(lái)基數(shù)排序算法思想 借鑒LSD法 設(shè)參加排序的序列為K=K1, K2,., Kn，其中Ki是d位rd進(jìn)制的數(shù)，rd稱為基數(shù)； d由所有元素中最長(zhǎng)的一個(gè)元素的位數(shù)計(jì)量， Ki = Ki1 Ki2. Kid從低位到高位依次對(duì)Kj(j=d, d-1, ., 1)根據(jù)基數(shù)分配，再按基數(shù)遞增序收集，則可得有序序列。33例 (1) K=3621 0724 8385 0075 0514 7368 0008 rd=10, d=4(2) K=Zhang Wang Li Zhao rd=27, d=534基數(shù)排序示例 477 241 467 5 363 81 5 第1趟：分配 0 1 2

21、3 4 5 6 7 8 9 241 363 5 477 81 5 467 收集 241 81 363 5 5 477 467第2趟：分配 0 1 2 3 4 5 6 7 8 9 5 241 363 477 81 5 467 收集 5 5 241 363 467 477 81第3趟：分配 0 1 2 3 4 5 6 7 8 9 5 241 363 467 5 477 81 收集 5 5 81 241 363 467 477 rd=10 d=3穩(wěn)定排序35鏈?zhǔn)交鶖?shù)排序的性能分析每一趟：分配O(n) 收集O(rd) d趟總計(jì)：O(d(n+rd)O(n) 通常d, rd均為常數(shù)輔助空間n個(gè)指針域空間隊(duì)

22、頭指針數(shù)組f1.rd和隊(duì)尾指針數(shù)組e1.rd 輔助空間復(fù)雜度：O(rd+n)3610.7 各種內(nèi)部排序方法的比較排序方法 最好時(shí)間 平均時(shí)間 最壞時(shí)間 輔助空間 穩(wěn)定性直接插入 O(n) O(n2) O(n2) O(1) 希爾 O(n1.3) O(1) 冒泡 O(n) O(n2) O(n2) O(1) 快速 O(nlog2n) O(nlog2n) O(n2) O(log2n) 簡(jiǎn)單選擇 O(n2) O(n2) O(n2) O(1) 堆 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 歸并 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 基數(shù) O(d(

23、rd+n) O(d(rd+n) O(d(rd+n) O(rd+n) 37按平均時(shí)間排序方法分為四類 O(n2)、O(nlgn)、O(n1+)、O(n)快速排序是目前基于比較的內(nèi)部排序中最好的方法關(guān)鍵字隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短，堆排序次之，但后者所需的輔助空間少當(dāng)n較小時(shí)如(np.key then q:=p; p:=p.next if q.pre nil then q.pre.next:=q.next; if q.next nil then q.next.pre:=q.pre; q.next:=t.next; t.next:=q; q.pre:=t; t:=q r:=sENDP; SelectSort612.閱讀下列函數(shù)arrange() FUNC arrange (a:ARRAY1.n of integer, l, h, x: integer):integer; l和h分別為數(shù)據(jù)區(qū)的下界和上界 i:=l; j:=h; while ( ij ) do while ( i=x ) do j:=j-1; while ( ij and aix ) i:=