數(shù)據(jù)結(jié)構(gòu)第12章外排序課件

1、數(shù)據(jù)結(jié)構(gòu)第12章外排序第第1212章章 外外 排排 序序 12.1 12.1 外排序概述外排序概述12.2 12.2 磁盤排序磁盤排序12.3 12.3 磁帶排序磁帶排序本章小結(jié)本章小結(jié)數(shù)據(jù)結(jié)構(gòu)第12章外排序12.1 12.1 外排序概述外排序概述 文件存儲在外存上文件存儲在外存上, ,因此外排序方法與各種因此外排序方法與各種外存設(shè)備的特征有關(guān)外存設(shè)備的特征有關(guān), ,外存設(shè)備大體上可分為兩外存設(shè)備大體上可分為兩類類, ,一類是順序存取設(shè)備一類是順序存取設(shè)備, ,例如磁帶例如磁帶, ,另一類是直另一類是直接存取設(shè)備接存取設(shè)備, ,例如磁盤例如磁盤, ,其結(jié)構(gòu)如下圖所示。其結(jié)構(gòu)如下圖所示。 柱面

2、磁道 盤片 讀寫頭 主軸 數(shù)據(jù)結(jié)構(gòu)第12章外排序 外排序的基本方法是歸并排序法。它分為以下外排序的基本方法是歸并排序法。它分為以下兩個步驟：兩個步驟： (1) 生成若干初始?xì)w并段生成若干初始?xì)w并段(順串順串),這一過程也稱為這一過程也稱為文件預(yù)處理：文件預(yù)處理： 把含有把含有n個記錄的文件個記錄的文件,按內(nèi)存大小分成若干按內(nèi)存大小分成若干長度為長度為L的子文件的子文件(段段)； 分別將各子文件分別將各子文件(段段)調(diào)入內(nèi)存調(diào)入內(nèi)存,采用有效的內(nèi)采用有效的內(nèi)排序方法排序后送回外存。排序方法排序后送回外存。 (2) 多路歸并：對這些初始?xì)w并段進(jìn)行多遍歸并多路歸并：對這些初始?xì)w并段進(jìn)行多遍歸并,使得

3、有序的歸并段逐漸擴(kuò)大使得有序的歸并段逐漸擴(kuò)大,最后在外存上形成整個最后在外存上形成整個文件的單一歸并段文件的單一歸并段,也就完成了這個文件的外排序。也就完成了這個文件的外排序。數(shù)據(jù)結(jié)構(gòu)第12章外排序12.2 12.2 磁盤排序磁盤排序12.2.1 12.2.1 磁盤排序過程磁盤排序過程 磁盤是直接存取設(shè)備磁盤是直接存取設(shè)備,讀讀/寫一個數(shù)據(jù)塊的時間寫一個數(shù)據(jù)塊的時間與當(dāng)前讀與當(dāng)前讀/寫頭所處的位置關(guān)系不大。寫頭所處的位置關(guān)系不大。 我們通過一個例子來說明磁盤排序的過程。設(shè)我們通過一個例子來說明磁盤排序的過程。設(shè)有一個文件有一個文件,內(nèi)含內(nèi)含4500個記錄：個記錄：A1,A2,A4500,現(xiàn)在現(xiàn)

4、在要對該文件進(jìn)行排序要對該文件進(jìn)行排序,但可占用的內(nèi)存空間至多只但可占用的內(nèi)存空間至多只能對能對750個記錄進(jìn)行排序。輸入文件個記錄進(jìn)行排序。輸入文件(被排序的文件被排序的文件)放在磁盤上放在磁盤上,頁塊長為頁塊長為250個記錄。排序過程可如下個記錄。排序過程可如下進(jìn)行：進(jìn)行：數(shù)據(jù)結(jié)構(gòu)第12章外排序 R1 R2 R3 R4 R5 R6 R1 R2 R3 R1 R1 6個歸并段的歸并過程個歸并段的歸并過程 數(shù)據(jù)結(jié)構(gòu)第12章外排序12.2.2 12.2.2 多路平衡歸并多路平衡歸并 上上圖所示的歸并過程基本上是圖所示的歸并過程基本上是2路平衡歸并的算路平衡歸并的算法。一般說來法。一般說來,如果初始

5、歸并段有如果初始?xì)w并段有m個個,那么這樣的歸那么這樣的歸并樹就有并樹就有 log2m +1層層,要對數(shù)據(jù)進(jìn)行要對數(shù)據(jù)進(jìn)行 log2m 遍掃描。遍掃描。采用采用k路平衡歸并時路平衡歸并時,則相應(yīng)的歸并樹有則相應(yīng)的歸并樹有 logkm +1層層,要對數(shù)據(jù)進(jìn)行要對數(shù)據(jù)進(jìn)行 logkm 遍掃描。遍掃描。數(shù)據(jù)結(jié)構(gòu)第12章外排序 做內(nèi)部歸并時做內(nèi)部歸并時,在在k個記錄中選擇最小者個記錄中選擇最小者,需要順需要順序比較序比較k-1次。每趟歸并次。每趟歸并u個記錄需要做個記錄需要做(u-1)*(k-1)次比較次比較,s趟歸并總共需要的比較次數(shù)為：趟歸并總共需要的比較次數(shù)為： s*(u-1)*(k-1)= lo

6、gkm *(u-1)*(k-1) = log2m *(u-1)* (k-1) log2k 其中其中, log2m *(u-1)在初始?xì)w并段個數(shù)在初始?xì)w并段個數(shù)m與記錄與記錄個數(shù)個數(shù)u一定時是常量一定時是常量,而而(k-1) log2k 在在k增大時趨增大時趨于無窮大。因此于無窮大。因此,增大歸并路數(shù)增大歸并路數(shù)k,會使內(nèi)部歸并的時會使內(nèi)部歸并的時間增大。若間增大。若k增大到一定的程度增大到一定的程度,就會抵消掉由于減就會抵消掉由于減少讀寫磁盤次數(shù)而贏得的時間。少讀寫磁盤次數(shù)而贏得的時間。數(shù)據(jù)結(jié)構(gòu)第12章外排序下面討論利用敗者樹實(shí)現(xiàn)多路平衡歸并。下面討論利用敗者樹實(shí)現(xiàn)多路平衡歸并。 敗者樹是一棵

7、有敗者樹是一棵有k個葉結(jié)點(diǎn)的完全二叉樹個葉結(jié)點(diǎn)的完全二叉樹,葉子結(jié)葉子結(jié)點(diǎn)存儲記錄點(diǎn)存儲記錄,非葉結(jié)點(diǎn)可由關(guān)鍵字和它對應(yīng)的記錄地址非葉結(jié)點(diǎn)可由關(guān)鍵字和它對應(yīng)的記錄地址構(gòu)成構(gòu)成,為討論方便起見為討論方便起見,設(shè)非葉結(jié)點(diǎn)的結(jié)構(gòu)為：設(shè)非葉結(jié)點(diǎn)的結(jié)構(gòu)為： 關(guān)鍵字關(guān)鍵字,輸入有序段的路號輸入有序段的路號 對對k個輸入有序段進(jìn)行個輸入有序段進(jìn)行k路平衡歸并的方法如下：路平衡歸并的方法如下： (1) 取每個輸入有序段的第一個記錄作為敗者樹的取每個輸入有序段的第一個記錄作為敗者樹的葉子結(jié)點(diǎn)葉子結(jié)點(diǎn),建立初始敗者樹：兩兩葉結(jié)點(diǎn)進(jìn)行比較建立初始敗者樹：兩兩葉結(jié)點(diǎn)進(jìn)行比較,在在雙親結(jié)點(diǎn)中記錄比賽的敗者雙親結(jié)點(diǎn)中記錄

8、比賽的敗者(關(guān)鍵字較大者關(guān)鍵字較大者),而讓勝者而讓勝者去參加更高一層的比賽去參加更高一層的比賽,如此在根結(jié)點(diǎn)之上勝出的如此在根結(jié)點(diǎn)之上勝出的“冠冠軍軍”是關(guān)鍵字最小者。是關(guān)鍵字最小者。數(shù)據(jù)結(jié)構(gòu)第12章外排序 (2) 勝出的記錄寫至輸出歸并段勝出的記錄寫至輸出歸并段,在對應(yīng)的葉結(jié)點(diǎn)在對應(yīng)的葉結(jié)點(diǎn)處處,補(bǔ)充其輸入有序段的下一個記錄補(bǔ)充其輸入有序段的下一個記錄,若該有序段變空若該有序段變空,則補(bǔ)充一個大關(guān)鍵字則補(bǔ)充一個大關(guān)鍵字(比所有記錄關(guān)鍵字都大比所有記錄關(guān)鍵字都大,設(shè)為設(shè)為kmax)的虛記錄。的虛記錄。 (3) 調(diào)整敗者樹調(diào)整敗者樹,選擇新的關(guān)鍵字最小的記錄：從選擇新的關(guān)鍵字最小的記錄：從補(bǔ)充

9、記錄的葉結(jié)點(diǎn)向上和雙親結(jié)點(diǎn)的關(guān)鍵字比較補(bǔ)充記錄的葉結(jié)點(diǎn)向上和雙親結(jié)點(diǎn)的關(guān)鍵字比較,敗敗者留在該雙親結(jié)點(diǎn)者留在該雙親結(jié)點(diǎn),勝者繼續(xù)向上勝者繼續(xù)向上,直至樹根的雙親。直至樹根的雙親。 (4) 若勝出的記錄關(guān)鍵字等于若勝出的記錄關(guān)鍵字等于kmax,則歸并結(jié)束；則歸并結(jié)束；否則轉(zhuǎn)否則轉(zhuǎn)(2)繼續(xù)。繼續(xù)。數(shù)據(jù)結(jié)構(gòu)第12章外排序 例如例如,設(shè)有設(shè)有5個初始?xì)w并段個初始?xì)w并段,它們中各記錄的關(guān)鍵字分它們中各記錄的關(guān)鍵字分別是：別是： R1:17,21, R2:5,44, R3:10,12, R4:29,32, R5:15,56, 其中其中,是段結(jié)束標(biāo)志。利用敗者樹進(jìn)行是段結(jié)束標(biāo)志。利用敗者樹進(jìn)行5路平衡歸路

10、平衡歸并排序的過程如下圖所示。并排序的過程如下圖所示。 數(shù)據(jù)結(jié)構(gòu)第12章外排序 5,2 15,5 10,3 17,1 29 32 15 56 冠軍（最小者冠軍（最小者） (a) 5 路歸并敗者樹路歸并敗者樹 (b) 重購后的敗者樹（標(biāo)重購后的敗者樹（標(biāo)*結(jié)點(diǎn)發(fā)生改變）結(jié)點(diǎn)發(fā)生改變） 17 21 5 44 10 12 4 5 1 2 3 5 17 29,4 29 10 15 10,3 15,5 17,1 44,2 29 32 15 56 冠軍（最小者）冠軍（最小者） 17 21 44 10 12 4 5 1 2 3 44 17 29,4 29 10 15 * * * * 數(shù)據(jù)結(jié)構(gòu)第12章外排序

11、從上例看到從上例看到,k路平衡歸并的敗者樹的深度為路平衡歸并的敗者樹的深度為 log2k ,在每次調(diào)整找下一個具有最小關(guān)鍵字記錄時在每次調(diào)整找下一個具有最小關(guān)鍵字記錄時,最多做最多做 log2k 次關(guān)鍵字比較。因此次關(guān)鍵字比較。因此,利用敗者樹在利用敗者樹在k個個記錄中選擇最小者記錄中選擇最小者,只需要進(jìn)行只需要進(jìn)行O( log2k )次關(guān)鍵字比次關(guān)鍵字比較較,這時歸并總共需要的比較次數(shù)為：這時歸并總共需要的比較次數(shù)為： s*(u-1)* log2k = logkm *(u-1)* log2k = log2m *(u-1)* log2k log2k = log2m *(u-1)數(shù)據(jù)結(jié)構(gòu)第12章

12、外排序 這樣這樣,關(guān)鍵字比較次數(shù)與關(guān)鍵字比較次數(shù)與k無關(guān)無關(guān),總的內(nèi)部歸并時總的內(nèi)部歸并時間不會隨間不會隨k的增大而增大。因此的增大而增大。因此,只要內(nèi)存空間允許只要內(nèi)存空間允許,增大歸并路數(shù)增大歸并路數(shù)k,將有效地減少歸并樹的深度將有效地減少歸并樹的深度,從而減從而減少讀寫磁盤次數(shù)少讀寫磁盤次數(shù),提高外排序的速度。提高外排序的速度。數(shù)據(jù)結(jié)構(gòu)第12章外排序12.2.3 12.2.3 初始?xì)w并段的生成初始?xì)w并段的生成 采用上一章中介紹的常規(guī)內(nèi)排序方法采用上一章中介紹的常規(guī)內(nèi)排序方法,可以實(shí)現(xiàn)初可以實(shí)現(xiàn)初始?xì)w并段的生成始?xì)w并段的生成,但所生成的歸并段的大小正好等于一但所生成的歸并段的大小正好等于一

13、次能放入內(nèi)存中的記錄個數(shù)。顯然存在局限性。如果次能放入內(nèi)存中的記錄個數(shù)。顯然存在局限性。如果采用前面所述的敗者樹方法采用前面所述的敗者樹方法,可以使初始?xì)w并段的長度可以使初始?xì)w并段的長度增大。這里介紹一種稱為置換增大。這里介紹一種稱為置換-選擇排序方法用于生成選擇排序方法用于生成初始?xì)w并段。初始?xì)w并段。數(shù)據(jù)結(jié)構(gòu)第12章外排序 置換置換-選擇排序選擇排序生成初始?xì)w并段時生成初始?xì)w并段時,內(nèi)部排序基內(nèi)部排序基于選擇排序于選擇排序,同時在此過程中伴隨記錄的輸入和同時在此過程中伴隨記錄的輸入和輸出輸出,生成的初始?xì)w并段長度超過平均數(shù)生成的初始?xì)w并段長度超過平均數(shù),且長度且長度可能各不相同?？赡芨鞑幌嗤?/p>

14、。數(shù)據(jù)結(jié)構(gòu)第12章外排序 (1) 從待排文件從待排文件Fin中按內(nèi)存工作區(qū)中按內(nèi)存工作區(qū)WA的容量的容量w讀讀入入w個記錄。設(shè)歸并段編號個記錄。設(shè)歸并段編號i=1。 (2) 使用敗者樹從使用敗者樹從WA中選出關(guān)鍵字最小的記錄中選出關(guān)鍵字最小的記錄Rmin。 (3) 將將Rmin記錄輸出到記錄輸出到Fout中中,作為當(dāng)前歸并段的作為當(dāng)前歸并段的一個成員。一個成員。 (4) 若若Fin不空不空,則從則從Fin中讀入下一個記錄中讀入下一個記錄x放在放在Rmin所在的工作區(qū)位置代替所在的工作區(qū)位置代替Rmin。 (5) 在工作區(qū)中所有大于或等于在工作區(qū)中所有大于或等于Rmin的記錄中選擇的記錄中選擇出

15、最小記錄作為新的出最小記錄作為新的Rmin,轉(zhuǎn)轉(zhuǎn)(3),直到選不出這樣的直到選不出這樣的Rmin。 (6) 設(shè)設(shè)i=i+1,開始一個新的歸并段。開始一個新的歸并段。 (7) 若工作區(qū)已空若工作區(qū)已空,則初始?xì)w并段已全部產(chǎn)生；否則則初始?xì)w并段已全部產(chǎn)生；否則轉(zhuǎn)轉(zhuǎn)(2)。數(shù)據(jù)結(jié)構(gòu)第12章外排序 例例12.1 設(shè)磁盤文件中共有設(shè)磁盤文件中共有18個記錄個記錄,記錄的關(guān)鍵字記錄的關(guān)鍵字分別為：分別為：15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68 若內(nèi)存工作區(qū)可容納若內(nèi)存工作區(qū)可容納5個記錄個記錄,用用置換置換-選擇排序選擇排序可產(chǎn)生幾個初始

16、歸并段可產(chǎn)生幾個初始?xì)w并段,每個初始?xì)w并段包含哪些記每個初始?xì)w并段包含哪些記錄錄? 數(shù)據(jù)結(jié)構(gòu)第12章外排序讀入記錄讀入記錄內(nèi)存工作區(qū)狀態(tài)內(nèi)存工作區(qū)狀態(tài)Rmin輸出之后的初輸出之后的初始?xì)w并段狀態(tài)始?xì)w并段狀態(tài)15,4,97,64,17 15,4,97,64,174(i=1)歸并段歸并段1:43215,32,97,64,1715(i=1)歸并段歸并段1:4,15108108,32,97,64,1717(i=1)歸并段歸并段1:4,15,1744108,32,97,64,4432(i=1)歸并段歸并段1:4,15,17,3276108,76,97,64,4444(i=1)歸并段歸并段1:4,15,1

17、7,32,44初始?xì)w并段的生成過程初始?xì)w并段的生成過程 數(shù)據(jù)結(jié)構(gòu)第12章外排序讀入記讀入記錄錄內(nèi)存工作區(qū)狀內(nèi)存工作區(qū)狀態(tài)態(tài)Rmin輸出之后的初始?xì)w并段狀態(tài)輸出之后的初始?xì)w并段狀態(tài)9108,76,97,64,964(i=1) 歸并段歸并段:1:4,15,17,32,44,6439108,76,97,39,976(i=1) 歸并段歸并段1:4,15,17,32,44,64,7682108,82,97,39,982(i=1) 歸并段歸并段1:4,15,17,32,44,64,76,8256108,56,97,39,997(i=1) 歸并段歸并段1:4,15,17,32,44,64,76,82,973

18、1108,56,31,39,9108(i=1)歸并段歸并段1:4,15,17,32,44,64,76,82,97,108數(shù)據(jù)結(jié)構(gòu)第12章外排序讀入讀入記錄記錄內(nèi)存工作區(qū)狀態(tài)內(nèi)存工作區(qū)狀態(tài)Rmin輸出之后的初始?xì)w并輸出之后的初始?xì)w并段狀態(tài)段狀態(tài)8080,56,31,39,99(沒有大于等沒有大于等于于 1 0 8 的 記的 記錄錄,i=2)歸并段歸并段2:97380,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 8

19、0,255,68,7368(i=2)歸并段歸并段2:9,31,39,56,68 數(shù)據(jù)結(jié)構(gòu)第12章外排序共產(chǎn)生兩個初始?xì)w并段共產(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ū)狀內(nèi)存工作區(qū)狀態(tài)態(tài)Rmin輸出之后的初始?xì)w并輸出之后的初始?xì)w并段狀態(tài)段狀態(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,

20、73,80,255 數(shù)據(jù)結(jié)構(gòu)第12章外排序12.2.4 12.2.4 最佳歸并樹最佳歸并樹 由于采用置換由于采用置換-選擇排序的方法生成的初始?xì)w并選擇排序的方法生成的初始?xì)w并段長度不等段長度不等,在進(jìn)行逐趟在進(jìn)行逐趟k路歸并時對歸并段的組合路歸并時對歸并段的組合不同不同,會導(dǎo)致歸并過程中對外存的讀寫次數(shù)不同。會導(dǎo)致歸并過程中對外存的讀寫次數(shù)不同。為提高歸并的時間效率為提高歸并的時間效率,有必要對各歸并段進(jìn)行合理有必要對各歸并段進(jìn)行合理的搭配組合。按照最佳歸并樹的設(shè)計(jì)可以使歸并過的搭配組合。按照最佳歸并樹的設(shè)計(jì)可以使歸并過程中對外存的讀寫次數(shù)最少。程中對外存的讀寫次數(shù)最少。數(shù)據(jù)結(jié)構(gòu)第12章外排序

21、 最佳歸并樹是帶權(quán)路徑長度最短的最佳歸并樹是帶權(quán)路徑長度最短的k叉叉(階階)哈夫哈夫曼樹曼樹,構(gòu)造步驟如下：構(gòu)造步驟如下： (1) 若若(n-1)%(k-1)0,則需附加則需附加(k-1)-(n-1)%(k-1)個長度為個長度為0的虛段的虛段,以使每次歸并都可以對應(yīng)以使每次歸并都可以對應(yīng)k個段。個段。 (2) 按照哈夫曼樹的構(gòu)造原則按照哈夫曼樹的構(gòu)造原則(權(quán)值越小的結(jié)點(diǎn)離權(quán)值越小的結(jié)點(diǎn)離根結(jié)點(diǎn)越遠(yuǎn)根結(jié)點(diǎn)越遠(yuǎn))構(gòu)造最佳歸并樹。構(gòu)造最佳歸并樹。數(shù)據(jù)結(jié)構(gòu)第12章外排序例例12.2 設(shè)文件經(jīng)預(yù)處理后設(shè)文件經(jīng)預(yù)處理后,得到長度為得到長度為 47,9,39,18,4,12,23,7,21,16,26的的1

22、1個初始?xì)w并段個初始?xì)w并段,試為試為4路歸并設(shè)計(jì)一個讀寫文件次路歸并設(shè)計(jì)一個讀寫文件次數(shù)最少的歸并方案。數(shù)最少的歸并方案。 數(shù)據(jù)結(jié)構(gòu)第12章外排序 初始?xì)w并段的個數(shù)初始?xì)w并段的個數(shù)n=11,歸并路數(shù)歸并路數(shù)k=4,由于由于(n-1)%(k-1)=1,不為不為0,因此需附加：因此需附加： (k-1)-(n-1)%(k-1)=2個長度為個長度為0的虛段。根據(jù)集合：的虛段。根據(jù)集合： 49,9,35,18,4,12,23, 7,21,14,26,0,0構(gòu)造構(gòu)造4階哈夫曼樹階哈夫曼樹,如下圖所示。如下圖所示。數(shù)據(jù)結(jié)構(gòu)第12章外排序 49 35 26 23 18 21 14 12 9 7 4 0 0 8

23、8 218 11 46 4 4路最佳歸并樹路最佳歸并樹 數(shù)據(jù)結(jié)構(gòu)第12章外排序 若每個記錄占用一個物理頁塊若每個記錄占用一個物理頁塊, ,則此方案對外存則此方案對外存的讀寫次數(shù)為：的讀寫次數(shù)為： 2(4+7)3+ (9+12+14+18+21+23+26)2+(35+49)1 =726次。次。數(shù)據(jù)結(jié)構(gòu)第12章外排序12.3 12.3 磁帶排序磁帶排序 由于磁帶的特性不同于磁盤的特性由于磁帶的特性不同于磁盤的特性,所以兩者采用所以兩者采用的外排序方法也不盡相同。的外排序方法也不盡相同。12.3.1 12.3.1 多路平衡歸并排序多路平衡歸并排序 磁帶多路平衡歸并排序過程與磁盤的多路平衡歸磁帶多路

24、平衡歸并排序過程與磁盤的多路平衡歸并排序過程基本上相同。先對輸入文件的各段進(jìn)行并排序過程基本上相同。先對輸入文件的各段進(jìn)行內(nèi)排序內(nèi)排序,生成初始?xì)w并段生成初始?xì)w并段,再把它們寫到磁帶上再把它們寫到磁帶上,然后再然后再把這些歸并段進(jìn)行反復(fù)的歸并把這些歸并段進(jìn)行反復(fù)的歸并,直到只剩下一個歸并直到只剩下一個歸并段段(即為排好序的文件即為排好序的文件)為止。為止。數(shù)據(jù)結(jié)構(gòu)第12章外排序 我們先看一個我們先看一個2路歸并磁帶排序的例子路歸并磁帶排序的例子,了解磁帶了解磁帶排序所涉及的各種因素。排序所涉及的各種因素。 設(shè)有一個文件包含設(shè)有一個文件包含4500個記錄個記錄,現(xiàn)在要對其進(jìn)行排現(xiàn)在要對其進(jìn)行排序序,可供使用的磁帶有四臺可供使用的磁帶有四臺T1,T2,T3,T