第11章外排序

11.1外排序概述11.2磁盤排序11.3磁帶排序11.1外排序概述

文件存儲在外存上，因此外排序方法與各種外存設(shè)備的特征有關(guān)，外存設(shè)備大體上可分為兩類，一類是順序存取設(shè)備，例如磁帶,另一類是直接存取設(shè)備，例如磁盤，其結(jié)構(gòu)如下圖所示。外排序的基本方法是歸并排序法。它分為以下兩個步驟：

（1）生成若干初始?xì)w并段（順串）：這一過程也稱為文件預(yù)處理：

①把含有n個記錄的文件，按內(nèi)存大小分成若干長度為L的子文件（歸并段）；

②分別將各子文件（歸并段）調(diào)入內(nèi)存，采用有效的內(nèi)排序方法排序后送回外存。（2）多路歸并：對這些初始?xì)w并段進(jìn)行多遍歸并，使得有序的歸并段逐漸擴(kuò)大，最后在外存上形成整個文件的單一歸并段，也就完成了這個文件的外排序。內(nèi)存abc.databc1.databc2.dat…abcn.dat內(nèi)存abc1.databc2.dat…abcn.databc.dat第1步第2步有序均有序某內(nèi)排序算法某排序算法：只能是歸并算法11.2磁盤排序磁盤排序過程如下：磁盤是一種直接存取設(shè)備。文件Fin.dat（含4500個記錄）容量為750個記錄產(chǎn)生6個長度為750個記錄的有序文件F1～F6。第一階段

通過一個例子來說明磁盤排序的過程。設(shè)有一個文件Fin.dat，內(nèi)含4500個記錄：A1,A2,…,A4500，現(xiàn)在要對該文件進(jìn)行排序，但可占用的內(nèi)存空間至多只能對750個記錄進(jìn)行排序。輸入文件（被排序的文件）放在磁盤上，頁塊長為250個記錄。某種內(nèi)排序方法可用內(nèi)存空間大小為750個記錄第二階段：歸并過程

11.2.1初始?xì)w并段的生成

采用上一章中介紹的常規(guī)內(nèi)排序方法，可以實現(xiàn)初始?xì)w并段的生成，但所生成的歸并段的大小正好等于一次能放入內(nèi)存中的記錄個數(shù)。顯然存在局限性。如果采用前面所述的敗者樹方法,可以使初始?xì)w并段的長度增大。這里介紹一種稱為置換－選擇排序方法用于生成初始?xì)w并段。

置換－選擇排序生成初始?xì)w并段時，內(nèi)部排序基于選擇排序，同時在此過程中伴隨記錄的輸入和輸出，生成的初始?xì)w并段長度超過平均數(shù)，且長度可能各不相同。（1）從待排文件Fin中按內(nèi)存工作區(qū)WA的容量w讀入w個記錄。設(shè)歸并段編號i=1。

（2）使用敗者樹從WA中選出關(guān)鍵字最小的記錄Rmin。

（3）將Rmin記錄輸出到Fout中，作為當(dāng)前歸并段的一個成員。（4）若Fin不空，則從Fin中讀入下一個記錄x放在Rmin所在的工作區(qū)位置代替Rmin。

（5）在工作區(qū)中所有大于或等于Rmin的記錄中選擇出最小記錄作為新的Rmin,轉(zhuǎn)（3），直到選不出這樣的Rmin。

（6）設(shè)i=i+1，開始一個新的歸并段。（7）若工作區(qū)已空，則初始?xì)w并段已全部產(chǎn)生；否則轉(zhuǎn)（2）。

例11.1

設(shè)磁盤文件中共有18個記錄，記錄的關(guān)鍵字分別為：{15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68}

若內(nèi)存工作區(qū)可容納5個記錄，用置換-選擇排序可產(chǎn)生幾個初始?xì)w并段，每個初始?xì)w并段包含哪些記錄?讀入記錄內(nèi)存工作區(qū)狀態(tài)Rmin輸出之后的初始?xì)w并段狀態(tài)15,4,97,64,1715,4,97,64,174（i=1）歸并段1:{4}3215,32,97,64,1715（i=1）歸并段1:{4,15}108108,32,97,64,1717（i=1）歸并段1:{4,15,17}44108,32,97,64,4432（i=1）歸并段1:{4,15,17,32}76108,76,97,64,4444（i=1）歸并段1:{4,15,17,32,44}初始?xì)w并段的生成過程

讀入記錄內(nèi)存工作區(qū)狀態(tài)Rmin輸出之后的初始?xì)w并段狀態(tài)9108,76,97,64,964（i=1）歸并段1:{4,15,17,32,44,64}39108,76,97,39,976（i=1）歸并段1:{4,15,17,32,44,64,76}82108,82,97,39,982（i=1）歸并段1:{4,15,17,32,44,64,76,82}56108,56,97,39,997（i=1）歸并段1:{4,15,17,32,44,64,76,82,97}31108,56,31,39,9108（i=1）歸并段1:{4,15,17,32,44,64,76,82,97,108}讀入記錄內(nèi)存工作區(qū)狀態(tài)Rmin輸出之后的初始?xì)w并段狀態(tài)8080,56,31,39,99（沒有大于等于108的記錄，i=2）歸并段2:{9}7380,56,31,39,7331（i=2）歸并段2:{9,31}25580,56,255,39,7339（i=2）歸并段2:{9,31,39}6880,56,255,68,7356（i=2）歸并段2:{9,31,39,56}

－80,∞,255,68,7368（i=2）歸并段2:{9,31,39,56,68}共產(chǎn)生兩個初始?xì)w并段:

歸并段1:{4,15,17,32,44,64,76,82,97,108},

歸并段2:{9,31,39,56,68,73,80,255}讀入記錄內(nèi)存工作區(qū)狀態(tài)Rmin輸出之后的初始?xì)w并段狀態(tài)－80,∞,255,∞,7373（i=2）歸并段2:{9,31,39,56,68,73}－80,∞,255,∞,∞80（i=2）歸并段2:{9,31,39,56,68,73,80}－∞,∞,255,∞,∞255（i=2）歸并段2:{9,31,39,56,68,73,80,255}11.2.2多路平衡歸并

1.k路平衡歸并的效率分析

圖中的歸并過程基本上是2路平衡歸并的算法。一般說來，如果初始?xì)w并段有m個，那么這樣的歸并樹就有l(wèi)og2m+1層，要對數(shù)據(jù)進(jìn)行l(wèi)og2m遍掃描。采用k路平衡歸并時，則相應(yīng)的歸并樹有l(wèi)ogkm+1層，要對數(shù)據(jù)進(jìn)行l(wèi)ogkm遍掃描。log2m+1層總的讀寫次數(shù)＝[(F1+F2+F3+F4)*3+(F5+F6)*2]*2=(3000*3+1500*2)*2=24000。k越大，總的讀寫次數(shù)越少。做內(nèi)部歸并時，在k個記錄中選擇最小者，需要順序比較k-1次。每趟歸并u個記錄需要做(u-1)*(k-1)次比較，s趟歸并總共需要的關(guān)鍵字比較次數(shù)為：

s*(u-1)*(k-1)=logkm*(u-1)*(k-1)=log2m*(u-1)*(k-1)／log2k

其中，log2m*(u-1)在初始?xì)w并段個數(shù)m與記錄個數(shù)u一定時是常量，而(k-1)／log2k在k增大時趨于無窮大。因此增大歸并路數(shù)k，會使內(nèi)部歸并的時間增大。若k增大到一定的程度，就會抵消掉由于減少讀寫磁盤次數(shù)而贏得的時間。u個記錄log2m趟

利用敗者樹實現(xiàn)k路平衡歸并的過程是，先建立敗者樹，然后對k個輸入有序段進(jìn)行k路平衡歸并。敗者樹是一棵有k個葉子節(jié)點的完全二叉樹（相應(yīng)地，可將大根堆稱為勝者樹），其中葉子節(jié)點存儲記錄，分支節(jié)點存放關(guān)鍵字對應(yīng)的段號。所謂敗者是兩個記錄比較時關(guān)鍵字較大者，勝者是兩個記錄比較時關(guān)鍵字較小者。建立敗者樹是采用類似于堆調(diào)整的方法實現(xiàn)的，其初始時令所有的分支節(jié)點指向一個含最小關(guān)鍵字（MINKEY）的葉子節(jié)點，然后從各葉子節(jié)點出發(fā)調(diào)整分支節(jié)點為新的敗者即可。

2.k路平衡歸并過程

（1）取每個輸入有序段的第一個記錄作為敗者樹的葉子節(jié)點，建立初始敗者樹：兩兩葉子節(jié)點進(jìn)行比較，在雙親節(jié)點中記錄比賽的敗者（關(guān)鍵字較大者），而讓勝者去參加更高一層的比賽，如此在根節(jié)點之上勝出的“冠軍”是關(guān)鍵字最小者。（2）勝出的記錄寫至輸出歸并段，在對應(yīng)的葉子節(jié)點處，補充其輸入有序段的下一個記錄，若該有序段變空，則補充一個大關(guān)鍵字（比所有記錄關(guān)鍵字都大，設(shè)為kmax）的虛記錄。（3）調(diào)整敗者樹，選擇新的關(guān)鍵字最小的記錄：從補充記錄的葉子節(jié)點向上和雙親節(jié)點的關(guān)鍵字比較，敗者留在該雙親節(jié)點，勝者繼續(xù)向上，直至樹的根節(jié)點，最后將勝者放在根節(jié)點的雙親節(jié)點中。（4）若勝出的記錄關(guān)鍵字等于kmax，則歸并結(jié)束；否則轉(zhuǎn)（2）繼續(xù)。對k個有序段進(jìn)行k路平衡歸并的方法如下：

例11.2

設(shè)有5個初始?xì)w并段，它們中各記錄的關(guān)鍵字分別是：

F0:{17,21,∞} F1:{5,44,∞} F2:{10,12,∞} F3:{29,32,∞} F4:{15,56,∞}其中，∞是段結(jié)束標(biāo)志。說明利用敗者樹進(jìn)行k=5路平衡歸并排序的過程。解：這里k=5，其初始?xì)w并段的段號分別為0～4（與F0～F4相對應(yīng)）。先構(gòu)造含有5個葉子節(jié)點的敗者樹，由于敗者樹中不存在單分支節(jié)點，所以其中有4個分支節(jié)點，再加上一個冠軍節(jié)點（用于存放最小關(guān)鍵字）。用ls[0]存放冠軍節(jié)點，ls[1]～ls[4]存放分支節(jié)點，b0～b4存放葉子節(jié)點。初始時ls[0]～ls[4]分別取5（對應(yīng)的F5是虛擬段，只含一個最小關(guān)鍵字MINKEY），b0～b4分別取F0～F4中的第一個關(guān)鍵字，如下圖所示。為了方便，圖中每個分支節(jié)點中除了段號外，另加有相應(yīng)的關(guān)鍵字。敗者樹中：n0=k=5，n1=0，n2=n0-1=k-1，所以n=2k-1。

調(diào)整b4～b0的過程與此類似，它們調(diào)整后得到的結(jié)果分別如下圖所示。建立初始敗者樹過程產(chǎn)生最小關(guān)鍵字記錄的過程如下圖所示，其中粗線部分為調(diào)整路徑。利用敗者樹，不僅用F0到F4中產(chǎn)生最小關(guān)鍵字記錄，還能確定它在哪個Fi（F0～F4）中。這正是k路歸并需要的基本操作。

結(jié)論：利用敗者樹進(jìn)行多路平衡歸并，關(guān)鍵字比較次數(shù)與k無關(guān)，總的內(nèi)部歸并時間不會隨k的增大而增大。因此只要內(nèi)存空間允許，增大歸并路數(shù)k，將有效地減少歸并樹的深度，從而減少讀寫磁盤次數(shù)，提高外排序的速度。從上例看到，k路平衡歸并的敗者樹的深度為log2k+1，在每次調(diào)整找下一個具有最小關(guān)鍵字記錄時，僅需要做log2k次關(guān)鍵字比較。因此，若初始?xì)w并段為m個，利用敗者樹在k個記錄中選擇最小者，只需要進(jìn)行l(wèi)og2k次關(guān)鍵字比較，則s=logkm趟歸并總共需要的關(guān)鍵字比較次數(shù)為：

s×(u-1)×log2k=logkm×(u-1)×log2k

=log2m×(u-1)×log2k/log2k

=log2m×(u-1)u為每趟歸并的記錄數(shù)11.2.3最佳歸并樹

由于采用置換－選擇排序的方法生成的初始?xì)w并段長度不等，在進(jìn)行逐趟k路歸并時對歸并段的組合不同，會導(dǎo)致歸并過程中對外存的讀／寫次數(shù)不同。為提高歸并的時間效率，有必要對各歸并段進(jìn)行合理的搭配組合。按照最佳歸并樹的設(shè)計可以使歸并過程中對外存的讀／寫次數(shù)最少。

最佳歸并樹是帶權(quán)路徑長度最短的k叉（階）哈夫曼樹，構(gòu)造步驟如下：（1）若(n-1)Mod(k-1)≠0，則需附加(k-1)-(n-1)Mod(k-1)個長度為0的虛段，以使每次歸并都可以對應(yīng)k個段。（2）按照哈夫曼樹的構(gòu)造原則（權(quán)值越小的結(jié)點離根結(jié)點越遠(yuǎn)）構(gòu)造最佳歸并樹。

例11.3

設(shè)文件經(jīng)預(yù)處理后,得到長度為

{47,9,39,18,4,12,23,7,21,16,26}的11個初始?xì)w并段，試為4路歸并設(shè)計一個讀寫文件次數(shù)最少的歸并方案。

解：初始?xì)w并段的個數(shù)n=11，歸并路數(shù)k=4，由于(n-1)Mod(k-1)=1，不為0，因此需附加：

(k-1)-(n-1)Mod(k-1)=2個長度為0的虛段。根據(jù)集合：

{49,9,35,18,4,12,23,7,21,14,26,0,0}構(gòu)造4階哈夫曼樹，如下圖所示。4路最