數(shù)據(jù)結(jié)構(gòu) 第11章外排序PPT學(xué)習(xí)課件

1、第11章 外 排 序,11.1 外排序概述,11.2 磁盤排序,11.3 磁帶排序,1,11.1 外排序概述 文件存儲在外存上,因此外排序方法與各種外存設(shè)備的特征有關(guān),外存設(shè)備大體上可分為兩類,一類是順序存取設(shè)備,例如磁帶,另一類是直接存取設(shè)備,例如磁盤,其結(jié)構(gòu)如下圖所示。,2,外排序的基本方法是歸并排序法。它分為以下兩個(gè)步驟： （1）生成若干初始?xì)w并段（順串）：這一過程也稱為文件預(yù)處理： 把含有n個(gè)記錄的文件，按內(nèi)存大小分成若干長度為L的子文件（歸并段）； 分別將各子文件（歸并段）調(diào)入內(nèi)存，采用有效的內(nèi)排序方法排序后送回外存。 （2）多路歸并：對這些初始?xì)w并段進(jìn)行多遍歸并，使得有序的歸并段逐

2、漸擴(kuò)大，最后在外存上形成整個(gè)文件的單一歸并段，也就完成了這個(gè)文件的外排序。,3,內(nèi)存,abc.dat,abc1.dat abc2.dat abcn.dat,內(nèi)存,abc1.dat abc2.dat abcn.dat,abc.dat,第1步,第2步,有序,均有序,某算法,某排序算法：只能是歸并算法,4,11.2 磁盤排序 11.2.1 磁盤排序過程 磁盤是直接存取設(shè)備,讀/寫一個(gè)數(shù)據(jù)塊的時(shí)間與當(dāng)前讀/寫頭所處的位置關(guān)系不大。 通過一個(gè)例子來說明磁盤排序的過程。設(shè)有一個(gè)文件，內(nèi)含4500個(gè)記錄：A1,A2,A4500,現(xiàn)在要對該文件進(jìn)行排序，但可占用的內(nèi)存空間至多只能對750個(gè)記錄進(jìn)行排序。輸入文

3、件（被排序的文件）放在磁盤上，頁塊長為250個(gè)記錄。排序過程可如下進(jìn)行：,5,6個(gè)歸并段的歸并過程,6,11.2.2 多路平衡歸并 圖中的歸并過程基本上是2路平衡歸并的算法。一般說來，如果初始?xì)w并段有m個(gè)，那么這樣的歸并樹就有l(wèi)og2m+1層，要對數(shù)據(jù)進(jìn)行l(wèi)og2m遍掃描。采用k路平衡歸并時(shí)，則相應(yīng)的歸并樹有l(wèi)ogkm+1層，要對數(shù)據(jù)進(jìn)行l(wèi)ogkm遍掃描。,7,做內(nèi)部歸并時(shí)，在k個(gè)記錄中選擇最小者，需要順序比較k-1次。每趟歸并u個(gè)記錄需要做(u-1)*(k-1)次比較，s趟歸并總共需要的比較次數(shù)為： s*(u-1)*(k-1)=logkm*(u-1)*(k-1) =log2m*(u-1)*

4、(k-1)log2k 其中，log2m*(u-1)在初始?xì)w并段個(gè)數(shù)m與記錄個(gè)數(shù)u一定時(shí)是常量,而(k-1)log2k在k增大時(shí)趨于無窮大。因此增大歸并路數(shù)k，會使內(nèi)部歸并的時(shí)間增大。若k增大到一定的程度，就會抵消掉由于減少讀寫磁盤次數(shù)而贏得的時(shí)間。,u個(gè)記錄,log2m趟,8,下面討論利用敗者樹實(shí)現(xiàn)多路平衡歸并。 敗者樹是一棵有k個(gè)葉結(jié)點(diǎn)的完全二叉樹，葉子結(jié)點(diǎn)存儲記錄，非葉結(jié)點(diǎn)可由關(guān)鍵字和它對應(yīng)的記錄地址構(gòu)成，為討論方便起見，設(shè)非葉結(jié)點(diǎn)的結(jié)構(gòu)為： 關(guān)鍵字,輸入有序段的路號 對k個(gè)輸入有序段進(jìn)行k路平衡歸并的方法如下： （1）取每個(gè)輸入有序段的第一個(gè)記錄作為敗者樹的葉子結(jié)點(diǎn),建立初始敗者樹：兩兩

5、葉結(jié)點(diǎn)進(jìn)行比較，在雙親結(jié)點(diǎn)中記錄比賽的敗者（關(guān)鍵字較大者），而讓勝者去參加更高一層的比賽，如此在根結(jié)點(diǎn)之上勝出的“冠軍”是關(guān)鍵字最小者。,9,（2）勝出的記錄寫至輸出歸并段，在對應(yīng)的葉結(jié)點(diǎn)處，補(bǔ)充其輸入有序段的下一個(gè)記錄，若該有序段變空，則補(bǔ)充一個(gè)大關(guān)鍵字（比所有記錄關(guān)鍵字都大，設(shè)為kmax）的虛記錄。 （3）調(diào)整敗者樹，選擇新的關(guān)鍵字最小的記錄：從補(bǔ)充記錄的葉結(jié)點(diǎn)向上和雙親結(jié)點(diǎn)的關(guān)鍵字比較，敗者留在該雙親結(jié)點(diǎn)，勝者繼續(xù)向上，直至樹根的雙親。 （4）若勝出的記錄關(guān)鍵字等于kmax，則歸并結(jié)束；否則轉(zhuǎn)（2）繼續(xù)。,10,例如,設(shè)有5個(gè)初始?xì)w并段，它們中各記錄的關(guān)鍵字分別是： R1:17,21,

6、R2:5,44, R3:10,12, R4:29,32, R5:15,56, 其中,是段結(jié)束標(biāo)志。利用敗者樹進(jìn)行5路平衡歸并排序的過程如下圖所示。,11,建立初始敗者樹,12,重購后的敗者樹（粗線部分結(jié)點(diǎn)發(fā)生改變）,13,從中看到，k路平衡歸并的敗者樹的深度為log2k，在每次調(diào)整找下一個(gè)具有最小關(guān)鍵字記錄時(shí)，最多做log2k 次關(guān)鍵字比較。因此利用敗者樹在k個(gè)記錄中選擇最小者，只需要進(jìn)行O(log2k)次關(guān)鍵字比較，這時(shí)歸并總共需要的比較次數(shù)為： s*(u-1)* log2k=logkm*(u-1)* log2k =log2m*(u-1)* log2klog2k =log2m*(u-1),u

7、個(gè)記錄,logkm趟,14,這樣，關(guān)鍵字比較次數(shù)與k無關(guān)，總的內(nèi)部歸并時(shí)間不會隨k的增大而增大。因此只要內(nèi)存空間允許，增大歸并路數(shù)k，將有效地減少歸并樹的深度，從而減少讀寫磁盤次數(shù)，提高外排序的速度。,15,11.2.3 初始?xì)w并段的生成 采用上一章中介紹的常規(guī)內(nèi)排序方法,可以實(shí)現(xiàn)初始?xì)w并段的生成,但所生成的歸并段的大小正好等于一次能放入內(nèi)存中的記錄個(gè)數(shù)。顯然存在局限性。 如果采用前面所述的敗者樹方法,可以使初始?xì)w并段的長度增大。這里介紹一種稱為置換-選擇排序方法用于生成初始?xì)w并段。,16,置換-選擇排序生成初始?xì)w并段時(shí)，內(nèi)部排序基于選擇排序，同時(shí)在此過程中伴隨記錄的輸入和輸出，生成的初始?xì)w并

8、段長度超過平均數(shù)，且長度可能各不相同。,17,（1）從待排文件Fin中按內(nèi)存工作區(qū)WA的容量w讀入w個(gè)記錄。設(shè)歸并段編號i=1。 （2）使用敗者樹從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,開始一個(gè)新的歸并段。 （7）若工作區(qū)已空,則初始?xì)w并段已全部產(chǎn)生；否則轉(zhuǎn)（2）。,18,例11.1 設(shè)磁盤文件中共有18

9、個(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并段包含哪些記錄?,19,初始?xì)w并段的生成過程,20,21,22,共產(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,23,11.2.4 最佳歸并樹,由于采用置換-選擇排序的方法生成的初始?xì)w并段長度不等，在進(jìn)行逐趟k路歸并時(shí)對歸并段的組合不同，會導(dǎo)致歸并過程中對外存的讀寫次數(shù)不同。 為提高歸并的

10、時(shí)間效率，有必要對各歸并段進(jìn)行合理的搭配組合。按照最佳歸并樹的設(shè)計(jì)可以使歸并過程中對外存的讀寫次數(shù)最少。,24,最佳歸并樹是帶權(quán)路徑長度最短的k叉（階）哈夫曼樹，構(gòu)造步驟如下： （1）若(n-1) Mod (k-1)0，則需附加(k-1)-(n-1) Mod (k-1)個(gè)長度為0的虛段，以使每次歸并都可以對應(yīng)k個(gè)段。 （2）按照哈夫曼樹的構(gòu)造原則（權(quán)值越小的結(jié)點(diǎn)離根結(jié)點(diǎn)越遠(yuǎn)）構(gòu)造最佳歸并樹。,25,例11.2 設(shè)文件經(jīng)預(yù)處理后,得到長度為 47,9,39,18,4,12,23,7,21,16,26 的11個(gè)初始?xì)w并段，試為4路歸并設(shè)計(jì)一個(gè)讀寫文件次數(shù)最少的歸并方案。,26,初始?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è)長度為0的虛段。根據(jù)集合： 49,9,35,18,4,12,23, 7,2