數(shù)據(jù)結構第12章外排序

1、第第1212章章 外外 排排 序序 12.1 12.1 外排序概述外排序概述12.2 12.2 磁盤排序磁盤排序12.3 12.3 磁帶排序磁帶排序本章小結本章小結12.1 12.1 外排序概述外排序概述 文件存儲在外存上文件存儲在外存上, ,因此外排序方法與各種因此外排序方法與各種外存設備的特征有關外存設備的特征有關, ,外存設備大體上可分為兩外存設備大體上可分為兩類類, ,一類是順序存取設備一類是順序存取設備, ,例如磁帶例如磁帶, ,另一類是直另一類是直接存取設備接存取設備, ,例如磁盤例如磁盤, ,其結構如下圖所示。其結構如下圖所示。 柱面 磁道 盤片 讀寫頭 主軸 外排序的基本方法是

2、歸并排序法。它分為以下外排序的基本方法是歸并排序法。它分為以下兩個步驟：兩個步驟： (1) 生成若干初始歸并段生成若干初始歸并段(順串順串),這一過程也稱為這一過程也稱為文件預處理：文件預處理： 把含有把含有n個記錄的文件個記錄的文件,按內(nèi)存大小分成若干按內(nèi)存大小分成若干長度為長度為l的子文件的子文件(段段)； 分別將各子文件分別將各子文件(段段)調(diào)入內(nèi)存調(diào)入內(nèi)存,采用有效的內(nèi)采用有效的內(nèi)排序方法排序后送回外存。排序方法排序后送回外存。 (2) 多路歸并：對這些初始歸并段進行多遍歸并多路歸并：對這些初始歸并段進行多遍歸并,使得有序的歸并段逐漸擴大使得有序的歸并段逐漸擴大,最后在外存上形成整個最

3、后在外存上形成整個文件的單一歸并段文件的單一歸并段,也就完成了這個文件的外排序。也就完成了這個文件的外排序。12.2 12.2 磁盤排序磁盤排序12.2.1 12.2.1 磁盤排序過程磁盤排序過程 磁盤是直接存取設備磁盤是直接存取設備,讀讀/寫一個數(shù)據(jù)塊的時間寫一個數(shù)據(jù)塊的時間與當前讀與當前讀/寫頭所處的位置關系不大。寫頭所處的位置關系不大。 我們通過一個例子來說明磁盤排序的過程。設我們通過一個例子來說明磁盤排序的過程。設有一個文件有一個文件,內(nèi)含內(nèi)含4500個記錄：個記錄：a1,a2,a4500,現(xiàn)在現(xiàn)在要對該文件進行排序要對該文件進行排序,但可占用的內(nèi)存空間至多只但可占用的內(nèi)存空間至多只能

4、對能對750個記錄進行排序。輸入文件個記錄進行排序。輸入文件(被排序的文件被排序的文件)放在磁盤上放在磁盤上,頁塊長為頁塊長為250個記錄。排序過程可如下個記錄。排序過程可如下進行：進行： r1 r2 r3 r4 r5 r6 r1 r2 r3 r1 r1 6個歸并段的歸并過程個歸并段的歸并過程 12.2.2 12.2.2 多路平衡歸并多路平衡歸并 上上圖所示的歸并過程基本上是圖所示的歸并過程基本上是2路平衡歸并的算路平衡歸并的算法。一般說來法。一般說來,如果初始歸并段有如果初始歸并段有m個個,那么這樣的歸那么這樣的歸并樹就有并樹就有 log2m +1層層,要對數(shù)據(jù)進行要對數(shù)據(jù)進行 log2m

5、遍掃描。遍掃描。采用采用k路平衡歸并時路平衡歸并時,則相應的歸并樹有則相應的歸并樹有 logkm +1層層,要對數(shù)據(jù)進行要對數(shù)據(jù)進行 logkm 遍掃描。遍掃描。 做內(nèi)部歸并時做內(nèi)部歸并時,在在k個記錄中選擇最小者個記錄中選擇最小者,需要順需要順序比較序比較k-1次。每趟歸并次。每趟歸并u個記錄需要做個記錄需要做(u-1)*(k-1)次比較次比較,s趟歸并總共需要的比較次數(shù)為：趟歸并總共需要的比較次數(shù)為： s*(u-1)*(k-1)= logkm *(u-1)*(k-1) = log2m *(u-1)* (k-1) log2k 其中其中, log2m *(u-1)在初始歸并段個數(shù)在初始歸并段個

6、數(shù)m與記錄與記錄個數(shù)個數(shù)u一定時是常量一定時是常量,而而(k-1) log2k 在在k增大時趨增大時趨于無窮大。因此于無窮大。因此,增大歸并路數(shù)增大歸并路數(shù)k,會使內(nèi)部歸并的時會使內(nèi)部歸并的時間增大。若間增大。若k增大到一定的程度增大到一定的程度,就會抵消掉由于減就會抵消掉由于減少讀寫磁盤次數(shù)而贏得的時間。少讀寫磁盤次數(shù)而贏得的時間。下面討論利用敗者樹實現(xiàn)多路平衡歸并。下面討論利用敗者樹實現(xiàn)多路平衡歸并。 敗者樹是一棵有敗者樹是一棵有k個葉結點的完全二叉樹個葉結點的完全二叉樹,葉子結葉子結點存儲記錄點存儲記錄,非葉結點可由關鍵字和它對應的記錄地址非葉結點可由關鍵字和它對應的記錄地址構成構成,為

7、討論方便起見為討論方便起見,設非葉結點的結構為：設非葉結點的結構為： 關鍵字關鍵字,輸入有序段的路號輸入有序段的路號 對對k個輸入有序段進行個輸入有序段進行k路平衡歸并的方法如下：路平衡歸并的方法如下： (1) 取每個輸入有序段的第一個記錄作為敗者樹的取每個輸入有序段的第一個記錄作為敗者樹的葉子結點葉子結點,建立初始敗者樹：兩兩葉結點進行比較建立初始敗者樹：兩兩葉結點進行比較,在在雙親結點中記錄比賽的敗者雙親結點中記錄比賽的敗者(關鍵字較大者關鍵字較大者),而讓勝者而讓勝者去參加更高一層的比賽去參加更高一層的比賽,如此在根結點之上勝出的如此在根結點之上勝出的“冠冠軍軍”是關鍵字最小者。是關鍵字

8、最小者。 (2) 勝出的記錄寫至輸出歸并段勝出的記錄寫至輸出歸并段,在對應的葉結點在對應的葉結點處處,補充其輸入有序段的下一個記錄補充其輸入有序段的下一個記錄,若該有序段變空若該有序段變空,則補充一個大關鍵字則補充一個大關鍵字(比所有記錄關鍵字都大比所有記錄關鍵字都大,設為設為kmax)的虛記錄。的虛記錄。 (3) 調(diào)整敗者樹調(diào)整敗者樹,選擇新的關鍵字最小的記錄：從選擇新的關鍵字最小的記錄：從補充記錄的葉結點向上和雙親結點的關鍵字比較補充記錄的葉結點向上和雙親結點的關鍵字比較,敗敗者留在該雙親結點者留在該雙親結點,勝者繼續(xù)向上勝者繼續(xù)向上,直至樹根的雙親。直至樹根的雙親。 (4) 若勝出的記錄

9、關鍵字等于若勝出的記錄關鍵字等于kmax,則歸并結束；則歸并結束；否則轉否則轉(2)繼續(xù)。繼續(xù)。 例如例如,設有設有5個初始歸并段個初始歸并段,它們中各記錄的關鍵字分它們中各記錄的關鍵字分別是：別是： r1:17,21, r2:5,44, r3:10,12, r4:29,32, r5:15,56, 其中其中,是段結束標志。利用敗者樹進行是段結束標志。利用敗者樹進行5路平衡歸路平衡歸并排序的過程如下圖所示。并排序的過程如下圖所示。 5,2 15,5 10,3 17,1 29 32 15 56 冠軍（最小者冠軍（最小者） (a) 5 路歸并敗者樹路歸并敗者樹 (b) 重購后的敗者樹（標重購后的敗者

10、樹（標*結點發(fā)生改變）結點發(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 * * * * 從上例看到從上例看到,k路平衡歸并的敗者樹的深度為路平衡歸并的敗者樹的深度為 log2k ,在每次調(diào)整找下一個具有最小關鍵字記錄時在每次調(diào)整找下一個具有最小關鍵字記錄時,最多做最多做 log2k 次關鍵字比較。因此次關鍵字比較。因此,利用敗者樹在利用敗者樹在k個個記錄中

11、選擇最小者記錄中選擇最小者,只需要進行只需要進行o( log2k )次關鍵字比次關鍵字比較較,這時歸并總共需要的比較次數(shù)為：這時歸并總共需要的比較次數(shù)為： s*(u-1)* log2k = logkm *(u-1)* log2k = log2m *(u-1)* log2k log2k = log2m *(u-1) 這樣這樣,關鍵字比較次數(shù)與關鍵字比較次數(shù)與k無關無關,總的內(nèi)部歸并時總的內(nèi)部歸并時間不會隨間不會隨k的增大而增大。因此的增大而增大。因此,只要內(nèi)存空間允許只要內(nèi)存空間允許,增大歸并路數(shù)增大歸并路數(shù)k,將有效地減少歸并樹的深度將有效地減少歸并樹的深度,從而減從而減少讀寫磁盤次數(shù)少讀寫磁

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

13、-選擇排序選擇排序生成初始歸并段時生成初始歸并段時,內(nèi)部排序基內(nèi)部排序基于選擇排序于選擇排序,同時在此過程中伴隨記錄的輸入和同時在此過程中伴隨記錄的輸入和輸出輸出,生成的初始歸并段長度超過平均數(shù)生成的初始歸并段長度超過平均數(shù),且長度且長度可能各不相同?？赡芨鞑幌嗤?(1) 從待排文件從待排文件fin中按內(nèi)存工作區(qū)中按內(nèi)存工作區(qū)wa的容量的容量w讀讀入入w個記錄。設歸并段編號個記錄。設歸并段編號i=1。 (2) 使用敗者樹從使用敗者樹從wa中選出關鍵字最小的記錄中選出關鍵字最小的記錄rmin。 (3) 將將rmin記錄輸出到記錄輸出到fout中中,作為當前歸并段的作為當前歸并段的一個成員。一個

14、成員。 (4) 若若fin不空不空,則從則從fin中讀入下一個記錄中讀入下一個記錄x放在放在rmin所在的工作區(qū)位置代替所在的工作區(qū)位置代替rmin。 (5) 在工作區(qū)中所有大于或等于在工作區(qū)中所有大于或等于rmin的記錄中選擇的記錄中選擇出最小記錄作為新的出最小記錄作為新的rmin,轉轉(3),直到選不出這樣的直到選不出這樣的rmin。 (6) 設設i=i+1,開始一個新的歸并段。開始一個新的歸并段。 (7) 若工作區(qū)已空若工作區(qū)已空,則初始歸并段已全部產(chǎn)生；否則則初始歸并段已全部產(chǎn)生；否則轉轉(2)。 例例12.1 設磁盤文件中共有設磁盤文件中共有18個記錄個記錄,記錄的關鍵字記錄的關鍵字

15、分別為：分別為：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)生幾個初始歸并段可產(chǎn)生幾個初始歸并段,每個初始歸并段包含哪些記每個初始歸并段包含哪些記錄錄? 讀入記錄讀入記錄內(nèi)存工作區(qū)狀態(tài)內(nèi)存工作區(qū)狀態(tài)rmin輸出之后的初輸出之后的初始歸并段狀態(tài)始歸并段狀態(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(

16、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,17,32,44初始歸并段的生成過程初始歸并段的生成過程 讀入記讀入記錄錄內(nèi)存工作區(qū)狀內(nèi)存工作區(qū)狀態(tài)態(tài)rmin輸出之后的初始歸并段狀態(tài)輸出之后的初始歸并段狀態(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)

17、歸并段歸并段1:4,15,17,32,44,64,76,8256108,56,97,39,997(i=1) 歸并段歸并段1:4,15,17,32,44,64,76,82,9731108,56,31,39,9108(i=1)歸并段歸并段1:4,15,17,32,44,64,76,82,97,108讀入讀入記錄記錄內(nèi)存工作區(qū)狀態(tài)內(nèi)存工作區(qū)狀態(tài)rmin輸出之后的初始歸并輸出之后的初始歸并段狀態(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

18、,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)生兩個初始歸并段共產(chǎn)生兩個初始歸并段: 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輸出之后的初始歸并輸出之后的初始歸并段狀態(tài)段狀態(tài)80,255,7373(i=2)歸并段歸并段2:9,31,39,56,68,73 80,255,80(i

19、=2)歸并段歸并段2:9,31,39,56,68,73,80 ,255,255(i=2)歸并段歸并段2:9,31,39,56,68,73,80,255 12.2.4 12.2.4 最佳歸并樹最佳歸并樹 由于采用置換由于采用置換-選擇排序的方法生成的初始歸并選擇排序的方法生成的初始歸并段長度不等段長度不等,在進行逐趟在進行逐趟k路歸并時對歸并段的組合路歸并時對歸并段的組合不同不同,會導致歸并過程中對外存的讀寫次數(shù)不同。會導致歸并過程中對外存的讀寫次數(shù)不同。為提高歸并的時間效率為提高歸并的時間效率,有必要對各歸并段進行合理有必要對各歸并段進行合理的搭配組合。按照最佳歸并樹的設計可以使歸并過的搭配組

20、合。按照最佳歸并樹的設計可以使歸并過程中對外存的讀寫次數(shù)最少。程中對外存的讀寫次數(shù)最少。 最佳歸并樹是帶權路徑長度最短的最佳歸并樹是帶權路徑長度最短的k叉叉(階階)哈夫哈夫曼樹曼樹,構造步驟如下：構造步驟如下： (1) 若若(n-1)%(k-1)0,則需附加則需附加(k-1)-(n-1)%(k-1)個長度為個長度為0的虛段的虛段,以使每次歸并都可以對應以使每次歸并都可以對應k個段。個段。 (2) 按照哈夫曼樹的構造原則按照哈夫曼樹的構造原則(權值越小的結點離權值越小的結點離根結點越遠根結點越遠)構造最佳歸并樹。構造最佳歸并樹。例例12.2 設文件經(jīng)預處理后設文件經(jīng)預處理后,得到長度為得到長度為

21、 47,9,39,18,4,12,23,7,21,16,26的的11個初始歸并段個初始歸并段,試為試為4路歸并設計一個讀寫文件次路歸并設計一個讀寫文件次數(shù)最少的歸并方案。數(shù)最少的歸并方案。 初始歸并段的個數(shù)初始歸并段的個數(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構造構造4階哈夫曼樹階哈夫曼樹,如下圖所示。如下圖所示。 49 35 26 23 18 21 14 12 9

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

23、路平衡歸并排序過程基本上相同。先對輸入文件的各段進行并排序過程基本上相同。先對輸入文件的各段進行內(nèi)排序內(nèi)排序,生成初始歸并段生成初始歸并段,再把它們寫到磁帶上再把它們寫到磁帶上,然后再然后再把這些歸并段進行反復的歸并把這些歸并段進行反復的歸并,直到只剩下一個歸并直到只剩下一個歸并段段(即為排好序的文件即為排好序的文件)為止。為止。 我們先看一個我們先看一個2路歸并磁帶排序的例子路歸并磁帶排序的例子,了解磁帶了解磁帶排序所涉及的各種因素。排序所涉及的各種因素。 設有一個文件包含設有一個文件包含4500個記錄個記錄,現(xiàn)在要對其進行排現(xiàn)在要對其進行排序序,可供使用的磁帶有四臺可供使用的磁帶有四臺t1