《數(shù)據(jù)結構(C++版)(第二版)》第10章

1、2020/7/7,1,第10章 外排序,本章學習內容,10.1 外排序的基本概念,10.2 多路平衡歸并的實現(xiàn),2020/7/7,2,10.1 外排序的基本概念,內排序是直接在計算機內存中進行的。若要排序的數(shù)據(jù)一次可以裝入計算機內存，則對這批數(shù)據(jù)的排序可以直接在內存中完成，因而，利用前面的內排序就可以了。若要排序的數(shù)據(jù)量很大，內存中一次裝不下，要將數(shù)據(jù)放入外存（磁帶、磁盤），這時，用內排序達不到我們的要求，必須用到本章介紹的外排序。而外排序是利用內存、外存來共同完成的。,外排序可以看成由兩個獨立的階段組成。首先，按可用內存的大小，將外存上含n個記錄的文件分成若干長度為m的子文件或段，依次讀入內

2、存并用上一章的內排序方法（一般用堆排序實現(xiàn)）完成每段的排序，再保存到外存；然后，對這些段進行歸并，使歸并段逐漸由小到大，直到得到整個文件有序為止。第一階段就是上一章介紹的內排序方法，因此，本章主要討論第二階段的歸并實現(xiàn)。,第二階段的歸并有二路平衡歸并和多路平衡歸并。下面先給出例子來說明，具體實現(xiàn)方法見下一節(jié)。,2020/7/7,3,假設有一個含10000個記錄的文件，內存一次只能裝入1000個記錄，則可以將文件分成10段，每段含1000個記錄。首先通過10次內部排序得到10個初始歸并段R1R10，其中每一段都含有1000個記錄（已經有序），再保存到外存中，然后可以利用二路平衡歸并使整個文件有序

3、。二路平衡歸并見圖10-1。,圖10-1 二路平衡歸并過程,2020/7/7,4,若對剛才的文件，首先通過10次內部排序得到10個初始歸并段R1R10，其中每一段都含有1000個記錄，再保存到外存中，然后也可以利用五路平衡歸并使整個文件有序，五路平衡歸并見圖10-2。,圖10-2 五路平衡歸并過程,2020/7/7,5,一般情況下，外排序所需總的時間=內排序所需時間（生成初始歸并段）m*tIS+外存信息讀寫的時間d*tIO+平衡歸并所需的時間s*utmg。,m為初始歸并段的個數(shù)，tIS是得到一個初始歸并段進行內排序所需的時間均值；d為總的讀寫次數(shù)，tIO是進行一次外存讀寫時間的均值；s為歸并的

4、趟數(shù)，utmg是對u個記錄進行內部歸并所需時間。,對同一文件而言，假設有m個初始歸并段，進行k路平衡歸并，歸并的趟數(shù)可以表示為s=logkm 。若增加k或減少m則可以減少s，外排序所需總的時間就可以減少。,2020/7/7,6,10.2 多路平衡歸并的實現(xiàn),10.2.1 初始歸并段的生成,假設初始待排文件為輸入文件FI，初始歸并段文件為輸出文件FO，內存工作區(qū)為WA，F(xiàn)O和WA的初始狀態(tài)為空，并假設內存工作區(qū)WA的容量為W個記錄，則生成初始歸并段的操作過程為：,(1) 從FI輸入W個記錄到工作區(qū)WA。 (2) 從WA中選關鍵字最小的記錄，記為MINKEY。 (3) 將MINKEY記錄輸出到FO

5、中。 (4) 若FI不空，則從FI輸入下一個記錄到WA中。 (5) 從WA中選比MINKEY大的所有關鍵字中選最小的關鍵字，作為新的MINKEY。 (6) 重復（3）（5），直到WA中選不出新的MINKEY為止，由此得到一個初始歸并段。 (7) 重復（2）（6）直到WA為空。則得到全部初始歸并段。,例如，給定初始文件含有24個記錄，對應的關鍵字分別為：51，49，39，46，38，29，14，61，15，30，1，48，52，3，63，27，4，13，89，24，46，58，33，76。利用上面的方法生成初始歸并段過程如下表（假設內存工作區(qū)WA的容量為6個記錄）。,2020/7/7,7,表10

6、-1 生成初始歸并段,2020/7/7,8,表10-1 生成初始歸并段 (續(xù)),2020/7/7,9,表10-1 生成初始歸并段(續(xù)),2020/7/7,10,從表10-1可知，上面的24個記錄可以生成三個初始歸并段分別為：,第一歸并段R0：29,38,39,46,49,51,61 第二歸并段R1：1,3,14,15,27,30,48,52,63,89 第三歸并段R2：4,13,24,33,46,58,76,上面的三個初始歸并段都是有序序列，故可以用二路平衡歸并進行排序或用三路平衡歸并進行排序。,若用二路平衡歸并，可以得到如下結果：,29,38,39,46,49,51,61 1,3,14,15

7、,27,30,48,52,63,89 4,13,24,33,46,58,76 1,3,14,15,27,29,30,38,39,46,48,49,51,52,61,63,89 4,13,24,33,46,58,76 1,3,4,13,14,15,24,27,29,30,33,38,39,46,46,48,49,51,52,58,61,63,76,89,若用三路平衡歸并，可以得到如下結果：,29,38,39,46,49,51,61 1,3,14,15,27,30,48,52,63,89 4,13,24,33,46,58,76 1,3,4,13,14,15,24,27,29,30,33,38,39

8、,46,46,48,49,51,52,58,61,63,76,89,2020/7/7,11,10.2.2 多路平衡歸并的實現(xiàn),1. 多路平衡歸并的敗者樹,將9.4.2節(jié)中樹形選擇排序得到的樹稱為勝者樹（每次選最小的關鍵字），因為每個非終端結點均表示其左、右孩子結點中的“勝者”。反之，若在雙親結點中記下剛進行比賽的“敗者”，而讓勝者去參加更高一層的比賽，則可以得到一棵“敗者樹”。,現(xiàn)以五路平衡歸并為例來建立“敗者樹”，假設已經用前面的方法得到五個初始歸并段為（其中 表示該段的結束）：,第一歸并段B0：17，21， ,第二歸并段B1：05，44， ,第三歸并段B2：10，12， ,第四歸并段B3：

9、29，32， ,第五歸并段B4：15，56， ,2020/7/7,12,在建立“敗者樹”中，按完全二叉樹形式，從每個初始歸并段取一個關鍵字（第一個），作為“敗者樹”的葉子結點，用B0B4表示，而非葉子結點用Ls1Ls4表示，表示兩者比較的敗者，Ls0表示整個比較的勝者。B3和B4比較，B3為敗者，將它的段號存入Ls4中，B3和B4的勝者再與B0比較，敗者為B0，將它的段號存入Ls2中，B1與B2比較，敗者的段號存入Ls3中，B0、B1、B2、B3、B4比較的敗者段號存入Ls1中，勝者的段號存入Ls0中，得到的敗者樹見圖10-3。,圖10-3 五路歸并建立的初始敗者樹,2020/7/7,13,2

10、. 多路平衡歸并的實現(xiàn),多路平衡歸并的實現(xiàn)，是反復調整敗者樹，并輸出Ls0的值，直到樹中葉結點都表示為 。,現(xiàn)以五路平衡歸并舉例說明。,【例10-1】假設有五個初始歸并段為（其中 表示該段的結束）：,第一歸并段B0：17，21， ,第二歸并段B1：05，44， ,第三歸并段B2：10，12， ,第五歸并段B4：15，56， ,第四歸并段B3：29，32， ,試用“敗者樹”實現(xiàn)五路平衡歸并，并給出歸并的結果。,2020/7/7,14,解：先建立初始敗者樹，然后不斷的調整敗者樹，并輸出Ls0所對應段的值，直到樹中葉結點都表示為 。,具體實現(xiàn)過程見圖10-4各步驟。,（a）生成的初始敗者樹,(b)輸

11、出05后的敗者樹,2020/7/7,15,（c）輸出05,10后的敗者樹,(d)輸出05,10,12后的敗者樹,（e）輸出05,10,12,15后的敗者樹,(f)輸出05,10,12,15,17后的敗者樹,2020/7/7,16,（g）輸出05,10,12,15,17,21后的敗者樹,(h)輸出05,10,12,15,17,21,29后的敗者樹,（i）輸出05,10,12,15,17,21,29,32后敗者樹,(j)輸出05,10,12,15,17,21,29,32,44后敗者樹,2020/7/7,17,(k)輸出05,10,12,15,17,21,29,32,44,56后敗者樹,圖10-4

12、利用敗者樹實現(xiàn)五路平衡歸并,2020/7/7,18,3.多路平衡歸并的算法實現(xiàn),#include #define MAXKEY 32767 /定義最大值 #define min 0 /定義最小值 #define k 5 /K路平衡歸并 int lsk; /敗者樹中非葉子結點的存儲空間 int bk+1;/敗者樹中葉子結點的存儲空間,void adjust(int lsk,int s) int t=(s+k)/2; int temp; while(t0) if(bsblst) temp=s;s=lst;lst=temp; t=t/2; ls0=s;,2020/7/7,19,void createlosttree(int lsk) /建立敗者樹 for(int i=0;i=0;-i) adjust(ls,i); ,void k_merge(int lsk,int bk) /K路平衡歸并 for(int i=0;ibi; /輸入葉子結點的值 createlosttree(ls); while(bls0!=MAXKEY) int q=ls0; coutbq; /輸入最小值所屬段的下一個值 adjust(ls,