第十一章 外部排序

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

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

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

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

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

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

=內部排序所需的時間+外存信息讀寫的時間+內部歸并所需的時間

m*tisd*tIOs*utmg

其中：tis是為得到一個初始歸并段進行排序所需時間的均值；tIO是進行一次外存讀/寫時間的均值；

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

11.2外部排序的方法例:有10000條記錄,通過10次內部排序得到10個初始歸并段R1-R10,每段有1000條記錄.

R1

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

R1’

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

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

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

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

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

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置換-選擇排序問題:是否可以不用內部排序構造初始歸并段?例:若初始文件含有24個記錄，其的關鍵字為:51,49,39,46,38,29,14,61,15,1,48,52,3,63,27,4,1389,24,46,58,33,76。假設內存工作區(qū)可容納6個記錄，則可得如下4個初始歸并段：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置換-選擇排序置換-選擇排序就是新的構造方法:上例用此法,可求得如下3個初始歸并段：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

問題:怎樣構造呢?

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

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

結論:

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

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

并樹如下圖：93012183172624

51

38

32

121

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

30