1、10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較基數(shù)排序基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序10.6 基基 數(shù)數(shù) 排排 序序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序 n 個(gè)記錄的序列個(gè)記錄的序列 R1, R2, , Ri, , Rn, 每個(gè)記錄每個(gè)記錄Ri 都有多可關(guān)鍵字都有多可關(guān)鍵字 (Ki0, Ki1, ,Kid-1) )。 其中其中: : K0 被

2、稱為被稱為 “最主最主”位關(guān)鍵字位關(guān)鍵字，Kd-1 被稱為被稱為 “最次最次”位關(guān)鍵字位關(guān)鍵字。 如果對(duì)于序列中任意兩個(gè)記錄 Ri 和 Rj (1ijn) 都滿滿足足下列 (詞典詞典) 有序有序關(guān)系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) ) (1,2,15)(2,1,20)(2,3,18)(3,1,20)(3,2,30) (1,2,15)(2,1,20) (2,3,18) (3,1,20) (3,2,30)有序有序無(wú)序無(wú)序 則稱序列 R1, , Rn 對(duì)多關(guān)鍵字對(duì)多關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序。有序。 實(shí)現(xiàn)多關(guān)鍵字排序通常有

3、兩種作法:最高位優(yōu)先最高位優(yōu)先MSD法： 先對(duì)先對(duì)K0進(jìn)行排序進(jìn)行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別在每個(gè)子序列中對(duì) K1 進(jìn)行排序，.， 依次類推，直直至最后對(duì)最次位關(guān)鍵字排序完成為止至最后對(duì)最次位關(guān)鍵字排序完成為止。最低位優(yōu)先最低位優(yōu)先LSD法：法： 先對(duì) Kd-1 進(jìn)行排序，然后在次基礎(chǔ)上直接對(duì) Kd-2 進(jìn)行排序，依次類推，直至對(duì)直至對(duì)最主位關(guān)鍵字最主位關(guān)鍵字 K0 排序完成為止排序完成為止。例如例如: : 學(xué)生記錄含三個(gè)關(guān)鍵字:( (系號(hào)系號(hào),班號(hào)班號(hào),序號(hào)序號(hào)),), 要求對(duì)對(duì)學(xué)生記錄排序，系號(hào)為主關(guān)鍵字。對(duì)對(duì)K0排序排序?qū)?duì)K1排序排序?qū)?duì)K2排序排序

4、無(wú)序序列無(wú)序序列3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,30最高位優(yōu)先最高位優(yōu)先MSD的排序過(guò)程如下:1,2,152,1,202,3,183,1,203,2,301,2,152,1,202,3,183,1,203,2,30例如例如: : 學(xué)生記錄含三個(gè)關(guān)鍵字:( (系號(hào)系號(hào),班號(hào)班號(hào),序號(hào)序號(hào)),), 要求對(duì)對(duì)學(xué)生記錄排序，系號(hào)為主關(guān)鍵字。對(duì)對(duì)K2排序排序?qū)?duì)K1排序排序?qū)?duì)K0排序排序 無(wú)序序列無(wú)序序列3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,

5、303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30最低位優(yōu)先最低位優(yōu)先LSD的排序過(guò)程如下:二、鏈?zhǔn)交鶖?shù)排序二、鏈?zhǔn)交鶖?shù)排序基數(shù)排序法基數(shù)排序法是一種不需要進(jìn)行關(guān)鍵字間比較的排序方法。其特點(diǎn)是： 對(duì)于數(shù)字型或字符型的單關(guān)鍵字單關(guān)鍵字，可以看成看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字多關(guān)鍵字，此時(shí)可以采用采用“分配分配- -收集收集”的辦法按最低位優(yōu)先最低位優(yōu)先LSD進(jìn)行排序進(jìn)行排序。例如：例如：對(duì)下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個(gè)位數(shù)”

6、 取值分別為 0, 1, , 9 “分配分配” 成 10 組； (230), (834) ,(185), (386 , 606), (247), (768),(539 ,209) 230 , 834, 185, 386, 606, 247, 768, 539, 209 之后按從 0 至 9 的順序?qū)?它們 “收集收集” 在一起; 然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配分配” 成 10 組；最后按其“百位數(shù)”重復(fù)一遍上述操作。“分配分配” 230 , 834, 185, 386, 606, 247, 768 , 539, 209 之后再按從 0 至 9 的順序?qū)⑺鼈?“收集

7、收集” ” 在一起； (606, 209), (230 , 834, 539), (247), (768), (185, 386) 606, 209, 230 , 834, 539, 247, 768, 185, 386(185),(209, 230 , 247), (386), (539), (606), (768), (834)185,209, 230 , 247, 386, 539, 606, 768, 834 然后 “收集收集” ” 在一起；在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： 待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表；“分配”

8、 時(shí)，按當(dāng)前“關(guān)鍵字位”所取值，將 記錄分配到不同的 “鏈隊(duì)列” 中，每個(gè)隊(duì) 列中記錄的 “關(guān)鍵字位” 相同；“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大 將各隊(duì)列首尾相鏈成一個(gè)鏈表;對(duì)每個(gè)關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。例如：p369367167239237138230139進(jìn)行第一次分配進(jìn)行第一次分配進(jìn)行第一次收集進(jìn)行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138368239139369 239139138進(jìn)行第二次分配進(jìn)行第二次分配p230237138239139p230367167237138368239139f3 r3f6

9、 r6230 237138239139367 167368367167368進(jìn)行第二次收集 進(jìn)行第三次收集之后便得到記錄的有序序列進(jìn)行第三次收集之后便得到記錄的有序序列f1 r1p230237138239139367167368進(jìn)行第三次分配進(jìn)行第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368 基數(shù)排序的時(shí)間復(fù)雜度為：基數(shù)排序的時(shí)間復(fù)雜度為：O( d ( n+rd ) )其中， 分配為O(n)（n為記錄數(shù)）; 收集為O(rd) (rd為“基”關(guān)鍵字的取值范圍), d為“分配-收集”的趟數(shù)（記錄的關(guān)鍵字個(gè)數(shù)）。

10、10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.7 各種排序方法的綜合比較各種排序方法的綜合比較一、時(shí)間性能一、時(shí)間性能二、空間性能二、空間性能一、時(shí)間性能一、時(shí)間性能1. 平均的時(shí)間性能平均的時(shí)間性能基數(shù)排序基數(shù)排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(nlogn)：快速排序、堆排序和希爾排序快速排序、堆排序和希爾排序歸并排序、錦標(biāo)排序歸并排序、錦標(biāo)排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡(jiǎn)單

11、選擇排序簡(jiǎn)單選擇排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n):不穩(wěn)定不穩(wěn)定! !2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3. 簡(jiǎn)單選擇排序、堆排序和歸并排序簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨不隨記錄序列中關(guān)鍵字的分布而改變。 直接插入排序直接插入排序和起泡排序起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度; 快速排序快速排序的時(shí)間性能蛻化為O(n2) 二、空間性能二、空間性能指的是排序過(guò)程中所需的輔助空間大小1. 所有的簡(jiǎn)單排序方法簡(jiǎn)單排序方法(包括：直接插入、起泡和簡(jiǎn)單選擇) 和堆排序堆排序的空間復(fù)雜度為為O(1)；2. 快速排序?yàn)榭焖倥判驗(yàn)镺(logn)，為遞歸程序執(zhí)

12、行過(guò)程中，棧所需的輔助空間;3. 歸并排序和錦標(biāo)排序歸并排序和錦標(biāo)排序所需輔助空間最多，其空間復(fù)雜度為 O(n);4. 鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為 O( rd )。 基數(shù)排序基數(shù)排序 d(n + rd) d(n + rd) rd二、二、“勝者樹勝者樹”和和 “ “敗者敗者樹樹”三、多路平衡歸并的實(shí)現(xiàn)三、多路平衡歸并的實(shí)現(xiàn)四、置換四、置換- -選擇排序選擇排序五、最佳歸并樹五、最佳歸并樹第第11章章 外部排序外部排序一、概述一、概述1.1. 外存信息的存取外存信息的存取計(jì)算機(jī)的外存儲(chǔ)器磁帶磁盤順序存取的設(shè)備直接存取的設(shè)備計(jì)算機(jī)中進(jìn)行內(nèi)外存信息交換的基本單位是一個(gè)字

13、符序列(字符組)，對(duì)外存言，它是一個(gè)“物理記錄” 或“頁(yè)塊”，內(nèi)存中用來(lái)暫時(shí)存放一個(gè)頁(yè)塊的區(qū)域被稱作“緩沖區(qū)”。磁帶是一種“啟停”的設(shè)備，信息在磁帶上不能連續(xù)存放，在相鄰的兩個(gè)字符組之間均留有空隙。從磁帶存取一個(gè)頁(yè)塊的信息所需時(shí)間為:其中: ta 為延遲時(shí)間， tw 為傳輸一個(gè)字符的時(shí)間， n 為頁(yè)塊內(nèi)的字符個(gè)數(shù)。TI/O = ta + n tw磁盤的組織結(jié)構(gòu): 記錄盤面、磁道和扇面。磁盤信息的存取單位為一個(gè)扇面的字符組，它由一個(gè)三維地址確定:柱面號(hào)、記錄面號(hào)和頁(yè)塊號(hào)。從磁盤存取一個(gè)頁(yè)塊的信息所需時(shí)間為:其中: tseek 為延遲時(shí)間，tla為等待時(shí)間， twm 為傳輸一個(gè)字符的時(shí)間， n 為

14、頁(yè)塊內(nèi)的字符個(gè)數(shù)。TI/O = tseek + tla + n tw2.2. 外部排序的基本過(guò)程外部排序的基本過(guò)程 采用“2-路迭代歸并”策略，由相對(duì)獨(dú)立的兩個(gè)步驟組成：( () ) 按可用內(nèi)存大小，利用內(nèi)部排序方法，構(gòu)造若干個(gè)( 初始）有序子序列，并存到外存，通常稱外存中這些記錄有序子序列為 “歸并段歸并段”;( () ) 通過(guò)“逐趟歸并歸并”，逐步擴(kuò)大各個(gè)歸并段的長(zhǎng)度，直至外存中整個(gè)記錄序列按關(guān)鍵字有序?yàn)橹埂Ｅe例舉例: : 已知有一個(gè)含10,000個(gè)記錄的磁盤文件，而當(dāng)前所用的計(jì)算機(jī)一次只能對(duì)1,000個(gè)記錄進(jìn)行內(nèi)部排序。 則首先利用內(nèi)部排序的方法得到 1010 個(gè)“初始?xì)w并段初始?xì)w并段”

15、 ，然后進(jìn)行逐趟歸并。則歸并過(guò)程如下則歸并過(guò)程如下: :R1R2R3R4R5R6R7R8R9R10R11R12R13R14R15R21R22R23R31R32記錄有序序列記錄有序序列第一趟歸并第一趟歸并第二趟歸并第二趟歸并第三趟歸并第三趟歸并第四趟歸并第四趟歸并每個(gè)每個(gè)Ri 包含包含1000個(gè)記錄個(gè)記錄初始排序使每個(gè)初始排序使每個(gè)Ri 中的記錄有序中的記錄有序歸并排序過(guò)程包括歸并排序過(guò)程包括: : 一次初始排序一次初始排序 四趟歸并排序四趟歸并排序1000200040008000100002000外排的特點(diǎn)外排的特點(diǎn): :( () ) 待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，待排序的記錄數(shù)量很

16、大，不能一次裝入內(nèi)存，則無(wú)法利用上一章討論的排序方法進(jìn)行排序則無(wú)法利用上一章討論的排序方法進(jìn)行排序 ( (否則將引起頻繁訪問(wèn)內(nèi)存否則將引起頻繁訪問(wèn)內(nèi)存););（2 2）數(shù)據(jù)的讀）數(shù)據(jù)的讀/ /寫以寫以“頁(yè)塊頁(yè)塊”為單位進(jìn)行；為單位進(jìn)行；( 2) ( 2) 外排所需時(shí)間由外排所需時(shí)間由三部分三部分組成組成: : 內(nèi)部初始排序內(nèi)部初始排序的時(shí)間，的時(shí)間，內(nèi)部歸并排序內(nèi)部歸并排序的時(shí)間的時(shí)間內(nèi)外存的信息交換內(nèi)外存的信息交換的時(shí)間，主要取決于的時(shí)間，主要取決于 外排過(guò)程中訪問(wèn)外存的次數(shù)外排過(guò)程中訪問(wèn)外存的次數(shù); ;例如上頁(yè)的歸并例子例如上頁(yè)的歸并例子 假設(shè)外存的頁(yè)塊大小為假設(shè)外存的頁(yè)塊大小為 200

17、(每訪問(wèn)外存一次可讀每訪問(wèn)外存一次可讀/寫寫200個(gè)記個(gè)記錄錄)，則對(duì)含，則對(duì)含10000個(gè)記錄的文件，處理一遍需訪問(wèn)外存?zhèn)€記錄的文件，處理一遍需訪問(wèn)外存500次。次。操操 作作訪問(wèn)外存次數(shù)訪問(wèn)外存次數(shù)內(nèi)部初始排序一趟歸并總計(jì)50讀+50寫 = 100100讀讀/ /寫寫50+50 = 100100讀讀/ /寫寫100+1004 = 500500讀讀/ /寫寫 除去內(nèi)部初始排序和逐趟歸并時(shí)進(jìn)行的內(nèi)部歸并所需時(shí)間除去內(nèi)部初始排序和逐趟歸并時(shí)進(jìn)行的內(nèi)部歸并所需時(shí)間的因素外，的因素外，外部排序的時(shí)間主要取決于逐趟歸并所需進(jìn)行的外部排序的時(shí)間主要取決于逐趟歸并所需進(jìn)行的“趟數(shù)趟數(shù)”。如何減少歸并趟數(shù)？

18、如何減少歸并趟數(shù)？假設(shè)采用“5-路平衡歸并”策略R1R2R3R4R5R6R7R8R9R10R11R12記錄有序序列記錄有序序列第一趟歸并第一趟歸并第二趟歸并第二趟歸并只需要進(jìn)行 2 趟歸并, 訪問(wèn)外存次數(shù) = 100+1002 = 300。1000500010000每一趟將每一趟將5 5個(gè)或個(gè)或5 5個(gè)以下的子序列歸并成一個(gè)有序序列。個(gè)以下的子序列歸并成一個(gè)有序序列。 即：首先從每個(gè)（共即：首先從每個(gè)（共5 5個(gè)）子序列中各選擇一個(gè)記錄（從第個(gè)）子序列中各選擇一個(gè)記錄（從第1 1個(gè)開始），在這個(gè)開始），在這5 5個(gè)記錄中選擇一個(gè)最小記錄。依次類推。個(gè)記錄中選擇一個(gè)最小記錄。依次類推。S log

19、logk kmm n增大歸并路數(shù)增大歸并路數(shù) k , 可減少歸并趟數(shù)可減少歸并趟數(shù) S , 從而減少總從而減少總讀寫磁盤次數(shù)讀寫磁盤次數(shù) d 。n第一趟可將第一趟可將 m 個(gè)初始?xì)w并段歸并為個(gè)初始?xì)w并段歸并為 l = m/k 個(gè)歸并段，個(gè)歸并段， 以后每一趟歸并將以后每一趟歸并將 l 個(gè)歸并段歸并成個(gè)歸并段歸并成 l = l / k 個(gè)歸并段，直到最后形成一個(gè)大的歸并段個(gè)歸并段，直到最后形成一個(gè)大的歸并段為止。樹的高度為止。樹的高度 logkm 。即：歸并趟數(shù)。即：歸并趟數(shù)S。增大增大 k 或者減少或者減少 m。是否是否 k 越大越好？越大越好？結(jié)論：結(jié)論：?jiǎn)栴}：?jiǎn)栴}：n從從 k 個(gè)歸并段中各

20、取一個(gè)記錄進(jìn)行比較，選出最小個(gè)歸并段中各取一個(gè)記錄進(jìn)行比較，選出最小者，共需要比較者，共需要比較 k-1 次；次；n如果每一趟需要?dú)w并的記錄總數(shù)為如果每一趟需要?dú)w并的記錄總數(shù)為n，則每趟歸并，則每趟歸并 需要做需要做(n-1)*(k-1)次比較；次比較；nS 趟歸并總共需要的比較次數(shù)為趟歸并總共需要的比較次數(shù)為: S*(u-1)* (k-1) = log k m * (n-1) * (k-1) = log2m * (n-1) * (k-1) / log2k v當(dāng)初始?xì)w并段個(gè)數(shù)當(dāng)初始?xì)w并段個(gè)數(shù) m 與記錄總數(shù)與記錄總數(shù) n 一定時(shí)一定時(shí), log2m *(n-1) constv而而 (k-1)

21、/ log2k 在在 k 增大時(shí)趨于無(wú)窮大。增大時(shí)趨于無(wú)窮大。v因此因此, 增大歸并路數(shù)增大歸并路數(shù) k, 使得內(nèi)部歸并的時(shí)間增大。使得內(nèi)部歸并的時(shí)間增大。 首先考慮在內(nèi)存中進(jìn)行內(nèi)部首先考慮在內(nèi)存中進(jìn)行內(nèi)部 k 路歸并時(shí)的情況：路歸并時(shí)的情況：矛盾！矛盾！增大歸并路數(shù)增大歸并路數(shù) k, 使訪問(wèn)外存次數(shù)減少。使訪問(wèn)外存次數(shù)減少。 2. 勝者樹和敗者樹勝者樹和敗者樹勝者樹勝者樹每個(gè)非終端結(jié)點(diǎn)均表示其左右孩子結(jié)點(diǎn)中的每個(gè)非終端結(jié)點(diǎn)均表示其左右孩子結(jié)點(diǎn)中的“勝者勝者” ” ( (關(guān)鍵字值小者關(guān)鍵字值小者),),223647321525405522321540221515992525229836322522364732152540553622473225155540322240152215敗者樹敗者樹每個(gè)非終端結(jié)點(diǎn)均表示其左右孩子結(jié)點(diǎn)中的每個(gè)非終端結(jié)點(diǎn)均表示其左右孩子結(jié)點(diǎn)中的“敗者敗者” ” ( (關(guān)鍵字碼大者關(guān)鍵字碼大者) )。敗者樹敗者樹是樹型選擇排序的一種變型。是樹型選擇排序的一種變型。22364732152540553647255532402215敗者樹敗者樹每個(gè)非終端結(jié)點(diǎn)均表示其左右孩子結(jié)點(diǎn)中的每個(gè)非終端結(jié)點(diǎn)均表示其左右孩子結(jié)點(diǎn)中的“敗者敗者” ” ( (關(guān)鍵字碼小者關(guān)鍵字碼小者) )。敗者樹敗