數(shù)據(jù)結(jié)構(gòu)2015秋 PPT課件版 第11章 外排序

第11章外排序

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

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

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

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

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

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

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

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

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

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

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

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

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

例11.1

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

若內(nèi)存工作區(qū)可容納5個(gè)記錄，用置換-選擇排序可產(chǎn)生幾個(gè)初始?xì)w并段，每個(gè)初始?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并段的生成過(guò)程

讀入記錄內(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（沒(méi)有大于等于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)生兩個(gè)初始?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路平衡歸并的效率分析

圖中的歸并過(guò)程基本上是2路平衡歸并的算法。一般說(shuō)來(lái)，如果初始?xì)w并段有m個(gè)，那么這樣的歸并樹(shù)就有l(wèi)og2m+1層，要對(duì)數(shù)據(jù)進(jìn)行l(wèi)og2m遍掃描。采用k路平衡歸并時(shí)，則相應(yīng)的歸并樹(shù)有l(wèi)ogkm+1層，要對(duì)數(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)部歸并時(shí)，在k個(gè)記錄中選擇最小者，需要順序比較k-1次。每趟歸并u個(gè)記錄需要做(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并段個(gè)數(shù)m與記錄個(gè)數(shù)u一定時(shí)是常量，而(k-1)／log2k在k增大時(shí)趨于無(wú)窮大。因此增大歸并路數(shù)k，會(huì)使內(nèi)部歸并的時(shí)間增大。若k增大到一定的程度，就會(huì)抵消掉由于減少讀寫磁盤次數(shù)而贏得的時(shí)間。u個(gè)記錄log2m趟

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

2.k路平衡歸并過(guò)程

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

例11.2

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

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

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

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

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

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

例11.3

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

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

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

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

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