第十一章 外部排序

本文格式為Word版，下載可任意編輯——第十一章外部排序

第十一章外部排序外存信息的存取外部排序的方法多路平衡歸并的實現(xiàn)置換——選擇排序最正確歸并樹

11.1外部信息的存取計算機一般有兩種存儲器：內(nèi)存儲器(主存)和外存儲器(輔存)。內(nèi)存的信息可隨機存取，且存取速度快，但價格貴。容量小。外存儲器包括磁帶和磁盤(或磁鼓),前者為順序存取的設(shè)備，后者為隨機存取的設(shè)備。1.磁帶信息的存取2.磁盤信息的存取3.光盤信息的存取

11.2外部排序的方法外部排序基本上由兩個相對獨立的階段組成。

1.按可以用內(nèi)存大小，將外存上含n個記錄的文件分成若干長度為L的子文件或段(segment),依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對它們進(jìn)行排序，2.將排序后得到的有序子文件重新寫入外存，尋常稱這些有序子文件為歸并段或順串(run);然后，對這些歸并進(jìn)行逐趟歸并，使歸并段(有序的子文件)逐漸有小變大，直至得到整個有序文件為止。

11.2外部排序的方法一般狀況下，外部排序所需總的時間

=內(nèi)部排序所需的時間+外存信息讀寫的時間+內(nèi)部歸并所需的時間

m*tisd*tIOs*utmg

其中：tis是為得到一個初始?xì)w并段進(jìn)行排序所需時間的均值；tIO是進(jìn)行一次外存讀/寫時間的均值；

utmg是對u個記錄進(jìn)行內(nèi)部歸并所需時間；m為經(jīng)過內(nèi)部排序之后得到的初始?xì)w并段的個數(shù)；s為歸并的趟數(shù)；d為總的讀/寫次數(shù)。

11.2外部排序的方法例:有10000條記錄,通過10次內(nèi)部排序得到10個初始?xì)w并段R1-R10,每段有1000條記錄.

R1

R2R3R4R5R6R7R8R9R10R2’R1’’R1’’’有序文件R3’R2’’R4’R5’R3’’R2’’’

R1’

11.2外部排序的方法從上例中我們可以得到:一共歸并了4趟

外存信息讀寫500次問題:是否可以改進(jìn)減少外存信息讀寫?可以采用多路歸并即:R1R2R3R4R5R6R7R8R9R10R1’有序文件R2’

一共歸并了2趟,外存讀寫300次

11.2外部排序的方法結(jié)論:對同一文件,進(jìn)行外部排序時所需讀寫外存的次數(shù)和歸并趟數(shù)s成正比.對m個初始?xì)w并段進(jìn)行k-路平衡歸并時,歸并趟數(shù)為:s=向上取整(logkm)顯然:增加k可以減少s

11.3多路平衡歸并的實現(xiàn)為了減少歸并趟數(shù),我們增大k.問題:增大了k又會出現(xiàn)新的問題.增加內(nèi)部歸并所需的時間,由于比較的元素多了,比較的次數(shù)也就多了.為減少比較次數(shù),解決方法我們引出:敗者樹.敗者樹：在雙親結(jié)點中記錄下來剛進(jìn)行完的這場比賽中的敗者，而讓勝者去參與更高一層的比賽，便可得到一棵“敗者樹〞。

11.3多路平衡歸并的實現(xiàn)例:31

勝利者

失敗者0b0b3661525.

2b1991820.b

220

4

b412123748.

10

101516.

202240.

11.3多路平衡歸并的實現(xiàn)例:1301

勝利者

失敗者40b0b3151525.

2b1991820.b220

34

b412123748.

10

101516.

202240.

11.4置換-選擇排序問題:是否可以不用內(nèi)部排序構(gòu)造初始?xì)w并段?例:若初始文件含有24個記錄，其的關(guān)鍵字為:51,49,39,46,38,29,14,61,15,1,48,52,3,63,27,4,1389,24,46,58,33,76。假設(shè)內(nèi)存工作區(qū)可容納6個記錄，則可得如下4個初始?xì)w并段：RUN1:29,38,39,46,49,51RUN2:1,14,15,30,48,61RUN3:3,4,13,27,52,63RUN4:24,33,46,58,76,89

11.4置換-選擇排序置換-選擇排序就是新的構(gòu)造方法:上例用此法,可求得如下3個初始?xì)w并段：RUN1:29,38,39,46,49,51,61RUN2:1,3,14,15,27,30,48,52,63,89RUN3:4,13,24,33,46,58,76

問題:怎樣構(gòu)造呢?

置換-選擇排序算法思想:初始化:輸入文件FI,輸出文件FO,內(nèi)存工作區(qū)為WA.FO和WA置空，內(nèi)存工作區(qū)為空，WA的容量可容納w個記錄.(1)從FI輸入w個記錄到工作區(qū)WA。(2)從WA中選出最小關(guān)鍵字記錄，記MIN記錄。(3)將MIN輸出到FO中去。(4)若FI不為空，則從FI輸入下一個記錄到WA中。(5)從WA中所有關(guān)鍵字比MIN大的記錄中選出最小關(guān)鍵字記錄，作為新的MIN記錄。(6)重復(fù)(3)—(5),直至在WA中選不出新的MIN為止，則得一初始?xì)w并段，輸出之。(7)重復(fù)(2)—(6),直至WA為空。則得全部初始?xì)w并段。

FO空空292929,3829,38

WA空51,49,39,46,38,2951,49,39,46,3851,49,39,46,38,1451,49,39,46,,1451,49,39,46,61,14

FI51,49,39,46,38,29,14,61,15,30,1,48,52,…14,61,15,30,1,48,52,3,63,27,4,…14,61,15,30,1,48,52,3,63,27,4,…61,15,30,1,48,52,3,63,27,4,…61,15,30,1,48,52,3,63,27,4,…15,30,1,48,52,3,63,27,4,…

29,38,3929,38,3929,38,39,4629,38,39,4629,38,39,46,4929,38,39,46,49,51

51,49,,46,61,1451,49,15,46,61,1451,49,15,,61,1451,49,15,30,61,1451,1,15,30,61,1448,1,15,30,61,14

15,30,1,48,52,3,63,27,4,…30,1,48,52,3,63,27,4,…30,1,48,52,3,63,27,4,…1,48,52,3,63,27,4,…48,52,3,63,27,4,…52,3,63,27,4,…

FO29,38,39,46,49,51,61

WA48,1,15,30,52,143,63,27,4,…

FI3,63,27,4,…63,27,4,…27,4,…4,……………

29,38,39,46,49,51,6148,1,15,30,52,1411,31,3,141,3,14,15……

48,3,15,30,52,1448,63,15,30,52,1448,63,15,30,52,2748,63,4,30,52,27……

RUN1:29,38,39,46,49,51,61

結(jié)論:

RUN2:1,3,14,15,27,30,48,52,63,89RUN3:4,13,24,33,46,58,76

11.5最正確歸并樹問題:由置換-選擇生成所得的初始?xì)w并段，其各段長度不等對平衡歸并有何影響？假設(shè)由置換-選擇得到9個初始?xì)w并段，其長度(即記錄數(shù))依次為：9,30,12,18,3,17,2,6,24。現(xiàn)作3-路平衡歸并，其歸

并樹如下圖：93012183172624

51

38

32

121

假設(shè)每個記錄占一個物理塊，則兩趟歸并所需對外存進(jìn)行的讀/寫次數(shù)為(9+30+12+18+3+17+2+6+24)*2*2=484顯然，歸并方案不同，所得歸并樹亦不同，樹的帶權(quán)路徑長度(或外存讀/寫次數(shù))亦不同。回想在第六章中哈夫曼樹構(gòu)造方法?？傻萌缦聢D所示：3-路平衡歸并的最正確歸并樹(446次讀/寫)29311612171824

30