《數(shù)據(jù)結(jié)構(gòu)(C++版)(第二版)》第10章

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

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

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

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

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

6、-1 生成初始?xì)w并段,2020/7/7,8,表10-1 生成初始?xì)w并段 (續(xù)),2020/7/7,9,表10-1 生成初始?xì)w并段(續(xù)),2020/7/7,10,從表10-1可知，上面的24個(gè)記錄可以生成三個(gè)初始?xì)w并段分別為：,第一歸并段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,上面的三個(gè)初始?xì)w并段都是有序序列，故可以用二路平衡歸并進(jìn)行排序或用三路平衡歸并進(jìn)行排序。,若用二路平衡歸并，可以得到如下結(jié)果：,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,若用三路平衡歸并，可以得到如下結(jié)果：,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 多路平衡歸并的實(shí)現(xiàn),1. 多路平衡歸并的敗者樹,將9.4.2節(jié)中樹形選擇排序得到的樹稱為勝者樹（每次選最小的關(guān)鍵字），因?yàn)槊總€(gè)非終端結(jié)點(diǎn)均表示其左、右孩子結(jié)點(diǎn)中的“勝者”。反之，若在雙親結(jié)點(diǎn)中記下剛進(jìn)行比賽的“敗者”，而讓勝者去參加更高一層的比賽，則可以得到一棵“敗者樹”。,現(xiàn)以五路平衡歸并為例來建立“敗者樹”，假設(shè)已經(jīng)用前面的方法得到五個(gè)初始?xì)w并段為（其中 表示該段的結(jié)束）：,第一歸并段B0：17，21， ,第二歸并段B1：05，44， ,第三歸并段B2：10，12， ,第四歸并段B3：

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

10、. 多路平衡歸并的實(shí)現(xiàn),多路平衡歸并的實(shí)現(xiàn)，是反復(fù)調(diào)整敗者樹，并輸出Ls0的值，直到樹中葉結(jié)點(diǎn)都表示為 。,現(xiàn)以五路平衡歸并舉例說明。,【例10-1】假設(shè)有五個(gè)初始?xì)w并段為（其中 表示該段的結(jié)束）：,第一歸并段B0：17，21， ,第二歸并段B1：05，44， ,第三歸并段B2：10，12， ,第五歸并段B4：15，56， ,第四歸并段B3：29，32， ,試用“敗者樹”實(shí)現(xiàn)五路平衡歸并，并給出歸并的結(jié)果。,2020/7/7,14,解：先建立初始敗者樹，然后不斷的調(diào)整敗者樹，并輸出Ls0所對(duì)應(yīng)段的值，直到樹中葉結(jié)點(diǎn)都表示為 。,具體實(shí)現(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、利用敗者樹實(shí)現(xiàn)五路平衡歸并,2020/7/7,18,3.多路平衡歸并的算法實(shí)現(xiàn),#include #define MAXKEY 32767 /定義最大值 #define min 0 /定義最小值 #define k 5 /K路平衡歸并 int lsk; /敗者樹中非葉子結(jié)點(diǎn)的存儲(chǔ)空間 int bk+1;/敗者樹中葉子結(jié)點(diǎn)的存儲(chǔ)空間,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; /輸入葉子結(jié)點(diǎn)的值 createlosttree(ls); while(bls0!=MAXKEY) int q=ls0; coutbq; /輸入最小值所屬段的下一個(gè)值 adjust(ls,