《外部排序》PPT課件.ppt

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

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

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

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

5、因子） 一個物理記錄包含邏輯記錄的個數(shù) 帶的利用率上升，如上例： 設(shè) B.F = 100 1000 /100 0.6 6 inch ( total IBG ) 1000 80/800 100 inch ( file) 利用率 100/106 = 94.3 %,1、外存信息的存取,3、常用外存：,磁盤：由存取裝置、讀、寫磁頭、活動臂、盤片（磁道、扇區(qū)）、旋轉(zhuǎn)主軸構(gòu)成。 速度快、容量大、直接存取設(shè)備。 種類：固定頭磁盤、活動頭磁盤 固定頭磁盤：每個磁道都有一個磁頭（速度快） 活動頭磁盤：每個盤面共用一個磁頭， 增加了找道的時間，應(yīng)用廣泛。,柱面：各盤面的直徑相同的磁道的總和。,物理位置：盤組號、若

6、干個磁盤構(gòu)成一組，系統(tǒng)可能有許 多組。 柱面號、 磁道號、 塊（扇區(qū)號）,盤文件的讀寫時間：T i/o = tseck + tla + ntwm tseck ：找道時間 tla ：等待時間 twm ：傳輸時間/ 字符，n 字符數(shù)。,2、外部排序的方法,1、步驟：,生成合并段（run）：讀入文件的部分記錄到內(nèi)存 在內(nèi)存中進(jìn)行內(nèi)部排序 將排好序的這些記錄寫入外存，形成合并段 再讀入該文件 的下面的記錄，往復(fù)進(jìn)行，直至文件中的記錄全部形成合并段 為止。,外部合并：將上一階段生成的合并段調(diào)入內(nèi)存，進(jìn)行合并，直至最后形成一個有序的文 件。,平衡合并分類法：被合并的初始合并段均勻分布在 K 條磁帶上，即分

7、布在 T1、T2、 Tk 上。對這 K 條帶進(jìn)行合并，將生成的中間歸并段分布在 TK+1、 TK+2 、 T2K 上。然后，循環(huán)往復(fù)，直至最后形成一個 單一的合并段為止。 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）,T1,T2,T4：空,T3 ：空,7、15、19 8、11、13 16、23、31

8、5、12,2、外部排序的方法,初始分布：,R（1 1000）,R（20013000）,R（4001. 5001）,R（1001 2000）,R（30014000）,R（5001. 6000）,T1,T2,T4：空,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 路歸并，

9、 K 3。 2K = 6, 需 6條磁帶。六個初始合并段均勻分布在 T1、T2 、T3上。每個合并段有 1000 個記錄。T4、T5 、T6 初始為空。合并過程如下： 初始分布：,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, 需 6條磁帶。六個初始合并段均

10、勻分布在 T1、T2 、T3上。每個合并段有 1000 個記錄。T4、T5 、T6 初始為空。合并過程如下：,第一趟歸并：,R（1 3000）,R（30016000）,T4：,T5：,T1：空,T2：空,T3：空,T6：空,第二趟歸并：,R（1 6000）,T1：,T2：空,T3：空,T4：空,T5：空,T6：空,2、外部排序的方法,時間分析: 歸并趟數(shù): logkm where k 是路數(shù)；m 是初始合并段數(shù)。 在上例中： log26 = 3 而 log36 = 2 此外，還有一次生成所有合并段的時間。對 文件中的所有的記錄全部讀寫一次。 每一趟歸并時，對文件中的所有的記錄都要全部讀寫一次。

11、K 大，趟數(shù)減 少，讀寫記錄的總數(shù)將減少。但 K 大，需要的內(nèi)存將越多。 減少初始合并段數(shù) m, 將使趟數(shù)減少，讀寫記錄的總數(shù)將減少。這就要求在 內(nèi)存一定且進(jìn)行內(nèi)部排序時， 生成盡可能長的歸并段，從而減少歸并段的 總數(shù)。,輸入、輸出緩沖區(qū)的安排: 設(shè)進(jìn)行平衡 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）,T1,T2,T4：空,T3 ：空,2、

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

13、個記錄,250 個記錄,250 個記錄,250 個記錄,IBG（Inter Block Gap）,初始合并段 ( R（1 1000）),250 個記錄,T3,250 個記錄大,250 個記錄大,K(2)個輸入緩沖區(qū),250 個記錄大,1個輸出緩沖區(qū),讀入內(nèi)存,讀入內(nèi)存,寫入磁帶,注意：對于緩沖區(qū)的安排，有一定的原則。,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1 12,13 14,15 16,17 18,初始合并段 ( R（1 8）),T3,K(2)個輸入緩沖區(qū),1 10,1個輸出緩沖區(qū),讀入內(nèi)存,讀入內(nèi)存,寫入磁帶,緩沖區(qū)的安排舉例：,10

14、 100,1 12,1 10,另一個初始合并段 ( R（1 8）),i,j,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1 12,13 14,15 16,17 18,初始合并段 ( R（1 8）),T3,K(2)個輸入緩沖區(qū),12,1個輸出緩沖區(qū),緩沖區(qū)的安排舉例：,10 100,1 12,1 10,另一個初始合并段 ( R（1 8）),i,j,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1 12,13 14,15 16,17 18,初始合并段 ( R（1 8）),T3,K(2)個輸入緩沖區(qū),1

15、2,1個輸出緩沖區(qū),讀入內(nèi)存,讀入內(nèi)存,緩沖區(qū)的安排舉例：,10 100,13 14,1 10,另一個初始合并段 ( R（1 8）),i,j,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1 12,13 14,15 16,17 18,初始合并段 ( R（1 8）),T3,K(2)個輸入緩沖區(qū),1個輸出緩沖區(qū),讀入內(nèi)存,緩沖區(qū)的安排舉例：,10 100,13 14,1 10,另一個初始合并段 ( R（1 8）),i,j,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1 12,13 14,15 16,1

16、7 18,初始合并段 ( R（1 8）),T3,K(2)個輸入緩沖區(qū),1個輸出緩沖區(qū),讀入內(nèi)存,寫入磁帶,緩沖區(qū)的安排舉例：,10 100,13 14,1 10,另一個初始合并段 ( R（1 8）),i,j,13 14,13 14,3、多路平衡歸并的實現(xiàn),時間分析: logkm 趟 K 大，趟數(shù)減少，讀寫記錄的總數(shù)將減少。但 K 大，會帶來什么問題呢？,1、帶、盤的平衡多路歸并的性質(zhì)：,e.g: K = 2 時, m 個歸并串?？偣?n 個記錄。,合并段 1,合并段 2,合并段 m-1,合并段 m,中間合并段,中間合并段,中間合并段,中間合并段,有序文件,層數(shù)： log2m +1 歸并趟數(shù)：

17、log2m,3、多路平衡歸并的實現(xiàn),1、帶、盤的平衡多路歸并的性質(zhì)：,e.g: K 2 時, 趟數(shù)將會減少。m 個歸并串?？偣?n 個記錄。,合并段 1,合并段 k,合并段 m-1,合并段 m,中間合并段,中間合并段,有序文件,層數(shù)： logkm +1 歸并趟數(shù)： logkm,設(shè)從 k 個元素中挑選一個最小的元素需 ( k-1) 次比較。 每次比較耗費的時間代價為: tmg，那么在進(jìn)行 k 路平衡歸并時，總的比較時間耗費不會超過： logkm ( k - 1 ) ( n - 1 ) tmg = log2m / log2k ( k - 1 ) ( n - 1 ) tmg k log2m / lo

18、g2k ( k - 1 ),大,大,3、多路平衡歸并的實現(xiàn),1、帶、盤的平衡多路歸并的性質(zhì)：,設(shè)從 k 個元素中挑選一個最小的元素需 ( k-1) 次比較。 每次比較耗費的時間代價為: tmg，那么在進(jìn)行 k 平衡歸并時，總的時間耗費不會超過： logkm ( k - 1 ) ( n - 1 ) tmg = log2m / log2k ( k - 1 ) ( n - 1 ) tmg k log2m / log2k ( k - 1 ),大,大,改進(jìn)：采用勝者樹或者敗者樹，從 K 個元素中挑選一個最小的元素僅需 log2k 次比 較，這時總的時間耗費將下降： logkm log2k ( n - 1

19、 ) tmg log2m ( n - 1 ) tmg,2、勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結(jié) 果，使得更快地挑出亞軍、第三名 。,9,5,3、多路平衡歸并的實現(xiàn),2、勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結(jié) 果，使得更快地挑出亞軍、第三名 。,7,29,5,9,5,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),5,5,9,5,7,29,9,7,6,5,

20、4,3,2,1,5,注意：挑出冠軍 需要進(jìn)行 k-1 次 比較，此處需要 比較 3 次。,9,7,3、多路平衡歸并的實現(xiàn),2、勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結(jié) 果，使得更快地挑出亞軍、第三名 。,7,29,16,9,7,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),7,7,9,16,7,29,9,7,6,5,4,3,2,1,5 7,注意：挑出亞軍 需要進(jìn)行 log2k 次比較，此處需 要比較 2 次。

21、,9,12,3、多路平衡歸并的實現(xiàn),2、勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。決出冠軍之后，充分利用上一次比賽的結(jié) 果，使得更快地挑出亞軍、第三名 。,12,29,16,9,9,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),9,12,9,16,12,29,9,7,6,5,4,3,2,1,5 7 9,注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,3、多路平衡歸并的實現(xiàn),2、勝者樹及其使用 勝者進(jìn)入下一輪，直至決出本次比賽的冠軍。決

22、出冠軍之后，充分利用上一次比賽的 結(jié)果，使得更快地挑出亞軍、第三名 。 決出第一名需比較： k - 1 次 決出第二名需比較： log2k 次 決出第三名需比較： log2k 次,結(jié)果：采用勝者樹后，從 K 個元素中挑選一個最小的元素僅需 log2k 次比 較，這時總的時間耗費下降為： logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 有意思的是該結(jié)果和 k 無關(guān)，這是通過多用空間換來的。,改進(jìn)：采用勝者樹，K 個元素中最小的元素輸出之后，從根結(jié)點到它的相應(yīng)的葉子結(jié) 點路徑上的結(jié)點都需要進(jìn)行修改，為了加快程序運行的速度產(chǎn)生了敗者樹。,29,7,3、多路

23、平衡歸并的實現(xiàn),3、敗者樹及其使用,7,29,5,9,9,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),9,7,29,5,7,29,9,7,6,5,4,3,2,1,5,注意：挑出冠軍 需要進(jìn)行 k-1 次 比較，此處需要 比較 3 次。,5,0,0,5,29,16,3、多路平衡歸并的實現(xiàn),7,29,16,9,9,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,輸 入

24、緩 沖 區(qū),輸 出 緩 沖 區(qū),5 7,注意：挑出亞軍 需要進(jìn)行 log2k 次比較，此處需 要比較 2 次。,3、敗者樹及其使用,1,7,0,9,16,29,16,7,29,9,7,6,5,4,3,2,1,0,5,29,16,3、多路平衡歸并的實現(xiàn),3、敗者樹及其使用,12,29,16,9,12,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),5 7 9,注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,9,0,16,16,29,16,12,

25、29,9,7,6,5,4,3,2,1,0,9,3、多路平衡歸并的實現(xiàn),3、敗者樹的程序?qū)崿F(xiàn) typedef int LoserTree k ; typedef struct KeyType key; Exnode, External k+1 ;,Void K_Merge ( LoserTree / 將含最大關(guān)鍵字MAXKEY的記錄寫至輸出歸并段 / K_Merge,3、多路平衡歸并的實現(xiàn),3、敗者樹的程序?qū)崿F(xiàn),Void Adjust ( LoserTree / Adjust,Void CreateLoserTree ( LoserTree / CreateLoserTree,k,k,3、多路平

26、衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：,7,29,5,9,k,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,3,2,1,0,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,k,0,存于 b0 bk-1之中 注意： bk = - ,存于 ls0 lsk-1 之中,3,3,k,3、多路平衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：,7,29,5,9,k,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,3,2,1,0,2,

27、1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,k,0,存于 b0 bk-1之中 注意： bk = - ,存于 ls0 lsk-1 之中,3,2,k,3、多路平衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：,7,29,5,9,3,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,3,2,1,0,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,k,0,存于 b0 bk-1之中 注意： bk = - ,存于 ls0 ls

28、k-1 之中,3,2,1,3、多路平衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：,7,29,5,9,3,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,3,2,1,0,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,k,0,存于 b0 bk-1之中 注意： bk = - ,存于 ls0 lsk-1 之中,3,2,1,3、多路平衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：,7,29,5,9,3,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 4

29、7 48 59,3,2,1,0,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,0,0,存于 b0 bk-1之中 注意： bk = - ,存于 ls0 lsk-1 之中,3,5,2,1,3、多路平衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：,7,29,5,9,3,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,3,2,1,0,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：在輸出緩 沖區(qū)被寫滿之后 ，全部內(nèi)容輸出 至帶或盤。,1,1,0,0,存于 b0 bk-1之中 注

30、意：bk = - ,存于 ls0 lsk-1 之中,3,5,2,1,3、多路平衡歸并的實現(xiàn),敗者樹程序?qū)崿F(xiàn)：記錄輸出結(jié)束后，可能出現(xiàn)如下情況。此時 bls0 = +，程序結(jié)束。,3,3,2,1,0,2,1,輸 入 緩 沖 區(qū),輸 出 緩 沖 區(qū),注意：每一個歸并段的最后加一個字段為 + ，即書上所說的 MAXKEY，作為結(jié)束條件。,1,1,0,0,存于 b0 bk-1之中 注意：bk = - ,存于 ls0 lsk-1 之中,3,+,+,+,+,+,+,+,+,4、置換-選擇排序,1、作用：產(chǎn)生盡可能長的初始?xì)w并段。在內(nèi)存長度一定時，按照通常的排序方法，產(chǎn)生的 初始?xì)w并段的長度只能和內(nèi)存長度相

31、同，但采用本方法之后可以產(chǎn)生卻可以生成 兩倍內(nèi)存長度的初始?xì)w并段（平均情況下）。,2、實例：F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上 F2： 輸出磁帶 2 假定使用的內(nèi)存只有 3 個記錄長，利用置換-選擇分類法產(chǎn)生初始合并段。,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶

32、 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 13

33、1、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖

34、區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12) #,第一個初始合并段,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)

35、41 6(11)、(37)、(12) # 711、37、1211,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12) # 711、37、1211 815、37、1212,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、2

36、9 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12) # 711、37、1211 815、37、1212 915、37、2315,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、

37、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12) # 711、37、1211 815、37、1212 915、37、2315 1029、37、23 23,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12)

38、 # 711、37、1211 815、37、1212 915、37、2315 1029、37、23 23 11 29、3729,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12) # 711、37、1211 815、37、1212 915、37、2315 1029、37、23

39、 23 11 29、3729 12 3737,4、置換-選擇排序,實例的實現(xiàn)過程： F1：31、21、19、12、26、41、11、37、15、23、29 在帶 1 上,步數(shù)內(nèi)存緩沖區(qū)內(nèi)容（由 F1 輸入）輸出結(jié)果（至帶 F2 ） 131、 21、 1919 231、 21、 (12)21 331、 26、 (12)26 431、 41、 (12)31 5(11)、41、 (12)41 6(11)、(37)、(12) # 711、37、1211 815、37、1212 915、37、2315 1029、37、23 23 11 29、3729 12 3737 13#,第二個初始合并段,第一個初始

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