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

2、稱為被稱為 “最主最主”位關鍵字位關鍵字，Kd-1 被稱為被稱為 “最次最次”位關鍵字位關鍵字。 如果對于序列中任意兩個記錄 Ri 和 Rj (1ijn) 都滿滿足足下列 (詞典詞典) 有序有序關系： (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)有序有序無序無序 則稱序列 R1, , Rn 對多關鍵字對多關鍵字 (Ki0, Ki1,Kid-1) 有序。有序。 實現多關鍵字排序通常有

3、兩種作法:最高位優先最高位優先MSD法： 先對先對K0進行排序進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別在每個子序列中對 K1 進行排序，.， 依次類推，直直至最后對最次位關鍵字排序完成為止至最后對最次位關鍵字排序完成為止。最低位優先最低位優先LSD法：法： 先對 Kd-1 進行排序，然后在次基礎上直接對 Kd-2 進行排序，依次類推，直至對直至對最主位關鍵字最主位關鍵字 K0 排序完成為止排序完成為止。例如例如: : 學生記錄含三個關鍵字:( (系號系號,班號班號,序號序號),), 要求對對學生記錄排序，系號為主關鍵字。對對K0排序排序對對K1排序排序對對K2排序排序

4、無序序列無序序列3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,30最高位優先最高位優先MSD的排序過程如下:1,2,152,1,202,3,183,1,203,2,301,2,152,1,202,3,183,1,203,2,30例如例如: : 學生記錄含三個關鍵字:( (系號系號,班號班號,序號序號),), 要求對對學生記錄排序，系號為主關鍵字。對對K2排序排序對對K1排序排序對對K0排序排序 無序序列無序序列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最低位優先最低位優先LSD的排序過程如下:二、鏈式基數排序二、鏈式基數排序基數排序法基數排序法是一種不需要進行關鍵字間比較的排序方法。其特點是： 對于數字型或字符型的單關鍵字單關鍵字，可以看成看成是由多個數位或多個字符構成的多關鍵字多關鍵字，此時可以采用采用“分配分配- -收集收集”的辦法按最低位優先最低位優先LSD進行排序進行排序。例如：例如：對下列這組關鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個位數”

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 的順序將 它們 “收集收集” 在一起; 然后按其 “十位數” 取值分別為 0, 1, , 9 “分配分配” 成 10 組；最后按其“百位數”重復一遍上述操作。“分配分配” 230 , 834, 185, 386, 606, 247, 768 , 539, 209 之后再按從 0 至 9 的順序將它們 “收集

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 然后 “收集收集” ” 在一起；在計算機上實現基數排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結構，即鏈式基數排序，具體作法為： 待排序記錄以指針相鏈，構成一個鏈表；“分配”

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

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

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

11、選擇排序簡單選擇排序時間復雜度為時間復雜度為 O(n):不穩定不穩定! !2. 當待排記錄序列按關鍵字順序有序時當待排記錄序列按關鍵字順序有序時3. 簡單選擇排序、堆排序和歸并排序簡單選擇排序、堆排序和歸并排序的時間性能不隨不隨記錄序列中關鍵字的分布而改變。 直接插入排序直接插入排序和起泡排序起泡排序能達到O(n)的時間復雜度; 快速排序快速排序的時間性能蛻化為O(n2) 二、空間性能二、空間性能指的是排序過程中所需的輔助空間大小1. 所有的簡單排序方法簡單排序方法(包括：直接插入、起泡和簡單選擇) 和堆排序堆排序的空間復雜度為為O(1)；2. 快速排序為快速排序為O(logn)，為遞歸程序執

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

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

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

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

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

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

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

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

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

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