我的數(shù)據(jù)結構講義第十一章外部排序

1、1、外存信息的存取2、外部排序的方法3、多路平衡歸并的實現(xiàn)4、置換-選擇排序5、最佳歸并樹目錄第 11 章 外部排序 1、外存信息的存取1、外部排序：內部排序：信息一次可全部調入內存，信息在內存中的處理時間是主要的時間耗費。外部排序：信息量巨大，無法一次調入內存。只能駐留在帶、盤、CD-ROM 上。特點 為內存運行時間短，內、外存進行交換需要時間長。減少 I/O 時間成為主 要矛盾。 記錄（Record）：數(shù)據(jù)項的集合存于內存，稱之為結點。如果存之于外存，則叫做記 錄。原因起源于是在歷史上研究管理應用和計算機科學的兩部分人員的習慣。 域（場）：記錄中的每個數(shù)據(jù)項，稱之為域（Field） 。 文

2、件：記錄的集合。 關鍵字：唯一標識記錄的域，稱之為關鍵字。 有序文件：文件根據(jù)關鍵字的大小。排成遞增或遞減的序列。2、基本術語：3、常用外存： 磁帶：由磁帶介質、讀、寫磁頭、驅動器、接收盤和原始盤組成。 便宜、可反復使用、是一種順序存取設備。 查找費時、速度幔。1、外存信息的存取3、常用外存： 磁帶：由磁帶介質、讀、寫磁頭、驅動器、接收盤和原始盤組成。 便宜、可反復使用、是一種順序存取設備。 查找費時、速度慢。 帶信息的表示：一種磁化方向、代表1另一種磁化方向，代表001001001101011111、外存信息的存取3、常用外存： 磁帶：由磁帶介質、讀、寫磁頭、驅動器、接收盤和原始盤組成。 便

3、宜、可反復使用、是一種順序存取設備。 查找費時、速度慢（尤其是查找末端記錄時）。.磁帶機走向讀出頭寫入頭原始盤接收盤 帶文件的組織：記錄 1記錄 3記錄 2IRG（Inter Record Gap）記錄間隙1、外存信息的存取3、常用外存： 帶文件的組織：記錄 1記錄 3記錄 2IRG（Inter Record Gap）記錄間隙vt可靠讀寫區(qū) IRG：.5.75 inch，帶來的問題是什么？ 帶的利用率下降，如： 密度 800 byte per inch 的帶。設每個記錄有 80 byte ，共 1000 個記錄。如果， IRG .6 inch ; 帶的利用率？ 1000 (80/800) 10

4、0 inch ( filel ) 1000 0.6 600 inch ( total IRG) 利用率 1/7= 14 % 必須改進帶的利用率 ! 帶文件的讀寫時間：T i/o = ta + ntw ta 延遲時間：讀寫頭到達相應的物理塊的起始位置的時間。 tw 讀/寫一個字符的時間； n 記錄數(shù)。讀寫頭1、外存信息的存取3、常用外存： 帶文件的組織的改進：塊 1塊 3塊 2IBG（Inter Block Gap）塊間間隙 IBG：.5.75 inch，帶來的好處是什么？ 每一塊是一個物理記錄，包含若干個邏輯記錄。 B.F（塊因子） 一個物理記錄包含邏輯記錄的個數(shù) 帶的利用率上升，如上例： 設

5、 B.F = 100 1000 /100 0.6 6 inch ( total IBG ) 1000 80/800 100 inch ( file) 利用率 100/106 = 94.3 %1、外存信息的存取3、常用外存： 磁盤：由存取裝置、讀、寫磁頭、活動臂、盤片（磁道、扇區(qū)）、旋轉主軸構成。 速度快、容量大、直接存取設備。 種類：固定頭磁盤、活動頭磁盤 固定頭磁盤：每個磁道都有一個磁頭（速度快） 活動頭磁盤：每個盤面共用一個磁頭， 增加了找道的時間，應用廣泛。 柱面：各盤面的直徑相同的磁道的總和。 物理位置：盤組號、若干個磁盤構成一組，系統(tǒng)可能有許 多組。 柱面號、 磁道號、 塊（扇區(qū)號）

6、 盤文件的讀寫時間：T i/o = tseck + tla + ntwm tseck ：找道時間tla ：等待時間twm ：傳輸時間/ 字符，n 記錄數(shù)。2、外部排序的方法1、步驟： 生成合并段（run）：讀入文件的部分記錄到內存 在內存中進行內部排序 將排好序的這些記錄寫入外存，形成合并段 再讀入該文件 的下面的記錄，往復進行，直至文件中的記錄全部形成合并段 為止。 外部合并：將上一階段生成的合并段調入內存，進行合并，直至最后形成一個有序的文 件。 平衡合并分類法：被合并的初始合并段均勻分布在 K 條磁帶上，即分布在 T1、T2、 Tk 上。對這 K 條帶進行合并，將生成的中間歸并段分布在

7、TK+1、 TK+2 、 T2K 上。然后，循環(huán)往復，直至最后形成一個 單一的合并段為止。e.g: 平衡 2 路歸并， K 2。 2K = 4, 需 4條磁帶。六個初始合并段均勻分布在 T1、T2 上。每個合并段有 1000 個記錄。T3、T4 初始為空。合并過程如下：初始分布：R（1 1000）R（20012000）R（4001. 5001）R（1001 2000）R（30014000）R（5001. 6000）T1T2T4：空T3 ：空7、15、19 8、11、13 16、23、31 5、122、外部排序的方法 初始分布：R（1 1000）R（20013000）R（4001. 5000）R

8、（1001 2000）R（30014000）R（5001. 6000）T1T2T4：空T3 ：空 第一趟歸并：T1 ：空T2 ：空T3 ：T4：R（1 2000）R（40016000）R（2001 4000）2、外部排序的方法 第二趟歸并：T3 ：空T4 ：空T1 ：T2：R（1 4000）R（4001 6000） 第三趟歸并：T3 ：T4 ：空T1 ：空T2：空R（1 6000）2、外部排序的方法e.g: 平衡 3 路歸并， K 3。 2K = 6, 需 4條磁帶。六個初始合并段均勻分布在 T1、T2 、T3上。每個合并段有 1000 個記錄。T4、T5 、T6 初始為空。合并過程如下：初始

9、分布：R（1 1000）R（30014000）R（1001 2000）R（40015000）T1：T2：T4：空T3 ：R（2001 3000）R（50016000）T5：空T6：空 第一趟歸并：R（1 3000）R（30016000）T4：T5：T1：空T2：空T3：空T6：空2、外部排序的方法e.g: 平衡 3 路歸并， K 3。 2K = 6, 需 4條磁帶。六個初始合并段均勻分布在 T1、T2 、T3上。每個合并段有 1000 個記錄。T4、T5 、T6 初始為空。合并過程如下： 第一趟歸并：R（1 3000）R（30016000）T4：T5：T1：空T2：空T3：空T6：空 第二趟歸

10、并：R（1 6000）T1：T2：空T3：空T4：空T5：空T6：空2、外部排序的方法 時間分析: 歸并趟數(shù): logkm where k 是路數(shù)；m 是初始合并段數(shù)。 在上例中： log26 = 3 而 log36 = 2 此外，還有一次生成所有合并段的時間。對 文件中的所有的記錄全部讀寫一次。 每一趟歸并時，對文件中的所有的記錄都要全部讀寫一次。K 大，趟數(shù)減 少，讀寫記錄的總數(shù)將減少。但 K 大，需要的內存將越多。 減少初始合并段數(shù) m, 將使趟數(shù)減少，讀寫記錄的總數(shù)將減少。這就要求在 內存一定且進行內部排序時， 生成盡可能長的歸并段，從而減少歸并段的 總數(shù)。 輸入、輸出緩沖區(qū)的安排:

11、設進行平衡 2 路歸并， K 2。 2K = 4, 需 4條磁帶。六個初 始合并段均勻分布在 T1、T2 。每個合并段有 1000 個記錄。T3、T4 初始為空。R（1 1000）R（20012000）R（4001. 5001）R（1001 2000）R（30014000）R（5001. 6000）T1T2T4：空T3 ：空2、外部排序的方法 輸入、輸出緩沖區(qū)的安排: 設進行平衡 2 路歸并， K 2。 2K = 4, 需 4條磁帶。六個初 始合并段均勻分布在 T1、T2 。每個合并段有 1000 個記錄。T3、T4 初始為空。設每 個物理塊包含 250 個記錄，則每個初始合并段包含 4 個物

12、理塊。K 路合并，K 個輸入 輸入緩沖區(qū)和一個輸出緩沖區(qū)。R（1 1000）R（20012000）R（4001. 5001）R（1001 2000）R（30014000）R（5001. 6000）T1T2T4： 空T3 ：空 250 個記錄T1T2 250 個記錄 250 個記錄 250 個記錄 250 個記錄 250 個記錄 250 個記錄 250 個記錄IBG（Inter Block Gap）初始合并段 ( R（1 1000）) 250 個記錄T3 250 個記錄大 250 個記錄大 K(2)個輸入緩沖區(qū) 250 個記錄大 1個輸出緩沖區(qū)讀入內存讀入內存寫入磁帶3、多路平衡歸并的實現(xiàn) 時間

13、分析: logkm 趟 K 大，趟數(shù)減少，讀寫記錄的總數(shù)將減少。但 K 大，會帶來什么問題呢？1、帶、盤的平衡多路歸并的性質： e.g: K = 2 時, m 個歸并串。總共 n 個記錄。合并段 1合并段 2合并段 m-1合并段 m中間合并段 中間合并段 中間合并段中間合并段有序文件層數(shù)： log2m +1歸并趟數(shù)： log2m3、多路平衡歸并的實現(xiàn)1、帶、盤的平衡多路歸并的性質： e.g: K 2 時, 趟數(shù)將會減少。m 個歸并串。總共 n 個記錄。合并段 1合并段 k合并段 m-1合并段 m中間合并段 中間合并段有序文件層數(shù)： logkm +1歸并趟數(shù)： logkm 設從 k 個元素中挑選

14、一個最小的元素需 ( k-1) 次比較。 每次比較耗費的時間代價為: tmg，那么在進行 k 路平衡歸并時，總的時間耗費不會超過： logkm ( k - 1 ) ( n - 1 ) tmg = log2m / log2k ( k - 1 ) ( n - 1 ) tmgk log2m / log2k ( k - 1 )大大3、多路平衡歸并的實現(xiàn)1、帶、盤的平衡多路歸并的性質： 設從 k 個元素中挑選一個最小的元素需 ( k-1) 次比較。 每次比較耗費的時間代價為: tmg，那么在進行 k 平衡歸并時，總的時間耗費不會超過： logkm ( k - 1 ) ( n - 1 ) tmg = lo

15、g2m / log2k ( k - 1 ) ( n - 1 ) tmgk log2m / log2k ( k - 1 )大大 改進：采用勝者樹或者敗者樹，從 K 個元素中挑選一個最小的元素僅需 log2k 次比 較，這時總的時間耗費將下降： logkm log2k ( n - 1 ) tmg 2、勝者樹及其使用勝者進入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結果，使得更快地挑出亞軍、第三名 。953、多路平衡歸并的實現(xiàn)2、勝者樹及其使用勝者進入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結果，使得更快地挑出亞軍、第三名 。729595516495

16、27871225849129385766719224748597654321輸入緩沖區(qū)輸出 緩沖區(qū)5595729976543215注意：挑出冠軍需要進行 k-1 次比較，此處需要比較 3 次。973、多路平衡歸并的實現(xiàn)2、勝者樹及其使用勝者進入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結果，使得更快地挑出亞軍、第三名 。729169751649527871225849129385766719224748597654321輸入緩沖區(qū)輸出 緩沖區(qū)779167299765432157注意：挑出亞軍需要進行 log2k 次比較，此處需要比較 2 次。9123、多路平衡歸并的實現(xiàn)

17、2、勝者樹及其使用勝者進入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結果，使得更快地挑出亞軍、第三名 。1229169951649527871225849129385766719224748597654321輸入緩沖區(qū)輸出 緩沖區(qū)912916122997654321579注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。3、多路平衡歸并的實現(xiàn)2、勝者樹及其使用 勝者進入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的 結果，使得更快地挑出亞軍、第三名 。 決出第一名需比較： k - 1 次 決出第二名需比較： log2k 次 決出第三名需比較： lo

18、g2k 次 結果：采用勝者樹后，從 K 個元素中挑選一個最小的元素僅需 log2k 次比 較，這時總的時間耗費下降為： logkm log2k ( n - 1 ) tmg 有意思的是該結果和 k 無關，這是通過多用空間換來的。 改進：采用勝者樹，K 個元素中最小的元素輸出之后，從根結點到它的相應的葉子結 點路徑上的結點都需要進行修改，為了加快程序運行的速度產生了敗者樹。2973、多路平衡歸并的實現(xiàn)3、敗者樹及其使用72959951649527871225849129385766719224748597654321輸入緩沖區(qū)輸出 緩沖區(qū)97295729976543215注意：挑出冠軍需要進行 k

19、-1 次比較，此處需要比較 3 次。500529163、多路平衡歸并的實現(xiàn)729169951649527871225849129385766719224748597654321輸入緩沖區(qū)輸出 緩沖區(qū)57注意：挑出亞軍需要進行 log2k 次比較，此處需要比較 2 次。3、敗者樹及其使用1709162916729976543210529163、多路平衡歸并的實現(xiàn)3、敗者樹及其使用12291691651649527871225849129385766719224748597654321輸入緩沖區(qū)輸出 緩沖區(qū)579注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。11901616291612299

20、7654321093、多路平衡歸并的實現(xiàn)3、敗者樹的程序實現(xiàn)typedef int LoserTree k ;typedef struct KeyType key; Exnode, External k+1 ;Void K_Merge ( LoserTree &ls，External & b) for ( i = 0; i 0 ) if (bs.key blst.key) s lst; t = t / 2; ls0 = s; / AdjustVoid CreateLoserTree ( LoserTree &ls ) bk.key = MINKEY; for ( i=0; i = 0; - -

21、i ) Adjust(ls,i); / CreateLoserTreekk3、多路平衡歸并的實現(xiàn) 敗者樹程序實現(xiàn)：72959k5164952787122584912938576671922474859321021輸入緩沖區(qū)輸出 緩沖區(qū)注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。11k0存于 b0 bk-1之中初值： bk = - 存于 ls0 lsk-1 之中33k3、多路平衡歸并的實現(xiàn) 敗者樹程序實現(xiàn)：72959k5164952787122584912938576671922474859321021輸入緩沖區(qū)輸出 緩沖區(qū)注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。11k0存于

22、 b0 bk-1之中初值： bk = - 存于 ls0 lsk-1 之中32k3、多路平衡歸并的實現(xiàn) 敗者樹程序實現(xiàn)：7295935164952787122584912938576671922474859321021輸入緩沖區(qū)輸出 緩沖區(qū)注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。11k0存于 b0 bk-1之中初值： bk = - 存于 ls0 lsk-1 之中3213、多路平衡歸并的實現(xiàn) 敗者樹程序實現(xiàn)：7295935164952787122584912938576671922474859321021輸入緩沖區(qū)輸出 緩沖區(qū)注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。11k0

23、存于 b0 bk-1之中初值： bk = - 存于 ls0 lsk-1 之中3213、多路平衡歸并的實現(xiàn) 敗者樹程序實現(xiàn)：7295935164952787122584912938576671922474859321021輸入緩沖區(qū)輸出 緩沖區(qū)注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。1100存于 b0 bk-1之中初值： bk = - 存于 ls0 lsk-1 之中35213、多路平衡歸并的實現(xiàn) 敗者樹程序實現(xiàn)：7295935164952787122584912938576671922474859321021輸入緩沖區(qū)輸出 緩沖區(qū)注意：在輸出緩沖區(qū)被寫滿之后，全部內容輸出至帶或盤。1

24、100存于 b0 bk-1之中初值： bk = - 存于 ls0 lsk-1 之中354、置換-選擇排序1、作用：產生盡可能長的初始歸并段。在內存長度一定時，按照通常的排序方法，產生的 初始歸并段的長度只能和內存長度相同，但采用本方法之后可以產生卻可以生成 兩倍內存長度的初始歸并段（平均情況下）。2、實例：F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 F2： 輸出磁帶 2 假定使用的內存只有 3 個記錄長，利用置換-選擇分類法產生初始合并段。4、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶

25、 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 19194、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)214、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12

26、)264、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)314、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12

27、)315(11)、41、 (12)414、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #第一個初始合并段4、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2

28、 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、12114、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、121181

29、5、37、12124、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23154、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F

30、1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23151029、37、23 234、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (1

31、2)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23151029、37、23 2311 29、37294、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、121291

32、5、37、23151029、37、23 2311 29、372912 29374、置換-選擇排序 實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 步數(shù)內存緩沖區(qū)內容（由 F1 輸入）輸出結果（至帶 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23151029、37、23 2311 29、372912 373713#第二個初始合并段4、置換

33、-選擇排序 3、長度分析： 設內存可以存放 m 個記錄，則首先從文件讀入 m 記錄到內存。這 m 個記錄 肯定可以歸入本初始合并段內。這樣，必須從文件中讀入 m 個記錄。這 m 個 記錄中平均有一半可以歸入本合并段，一半歸入下一合并段。 因此，合并段的平均長度為：m + m/2 + m/4 + = 2m 所以，在平均情況下，合并段的平均長度為 2m 。書上介紹：該結論由：EFMoore 在 1961 年從置換選擇排序同掃雪機的類比中得到 的。不過我認為這種證明完全是胡扯。4、程序實現(xiàn)： 可以用敗者樹的辦法 加以實現(xiàn)。32144、置換-選擇排序5、敗者樹實現(xiàn)置換-選擇排序522901051、49、39、46、38、29、14、61、1546139149151129138154332044、置換-選擇排序5、敗者樹實現(xiàn)置換-選擇排序52293801151、49、39、46、38、29、14、61、1546139149151114238154312044、置換-選擇排序5、敗者樹實現(xiàn)置換-選擇排序5229383901351、49、39、46、38、29、14、61、1546139149