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

2023年11月28日1第10章外排序本章學習內(nèi)容

10.1外排序的基本概念10.2多路平衡歸并的實現(xiàn)2023年11月28日210.1外排序的基本概念內(nèi)排序是直接在計算機內(nèi)存中進行的。若要排序的數(shù)據(jù)一次可以裝入計算機內(nèi)存，則對這批數(shù)據(jù)的排序可以直接在內(nèi)存中完成，因而，利用前面的內(nèi)排序就可以了。若要排序的數(shù)據(jù)量很大，內(nèi)存中一次裝不下，要將數(shù)據(jù)放入外存（磁帶、磁盤），這時，用內(nèi)排序達不到我們的要求，必須用到本章介紹的外排序。而外排序是利用內(nèi)存、外存來共同完成的。外排序可以看成由兩個獨立的階段組成。首先，按可用內(nèi)存的大小，將外存上含n個記錄的文件分成若干長度為m的子文件或段，依次讀入內(nèi)存并用上一章的內(nèi)排序方法（一般用堆排序?qū)崿F(xiàn)）完成每段的排序，再保存到外存；然后，對這些段進行歸并，使歸并段逐漸由小到大，直到得到整個文件有序為止。第一階段就是上一章介紹的內(nèi)排序方法，因此，本章主要討論第二階段的歸并實現(xiàn)。第二階段的歸并有二路平衡歸并和多路平衡歸并。下面先給出例子來說明，具體實現(xiàn)方法見下一節(jié)。2023年11月28日3假設(shè)有一個含10000個記錄的文件，內(nèi)存一次只能裝入1000個記錄，則可以將文件分成10段，每段含1000個記錄。首先通過10次內(nèi)部排序得到10個初始歸并段R1~R10，其中每一段都含有1000個記錄（已經(jīng)有序），再保存到外存中，然后可以利用二路平衡歸并使整個文件有序。二路平衡歸并見圖10-1。圖10-1二路平衡歸并過程2023年11月28日4若對剛才的文件，首先通過10次內(nèi)部排序得到10個初始歸并段R1~R10，其中每一段都含有1000個記錄，再保存到外存中，然后也可以利用五路平衡歸并使整個文件有序，五路平衡歸并見圖10-2。圖10-2五路平衡歸并過程2023年11月28日5一般情況下，外排序所需總的時間=內(nèi)排序所需時間（生成初始歸并段）m*tIS+外存信息讀寫的時間d*tIO+平衡歸并所需的時間s*utmg。m為初始歸并段的個數(shù)，tIS是得到一個初始歸并段進行內(nèi)排序所需的時間均值；d為總的讀寫次數(shù)，tIO是進行一次外存讀寫時間的均值；s為歸并的趟數(shù)，utmg是對u個記錄進行內(nèi)部歸并所需時間。對同一文件而言，假設(shè)有m個初始歸并段，進行k路平衡歸并，歸并的趟數(shù)可以表示為s=

logkm

。若增加k或減少m則可以減少s，外排序所需總的時間就可以減少。2023年11月28日610.2多路平衡歸并的實現(xiàn)10.2.1初始歸并段的生成假設(shè)初始待排文件為輸入文件FI，初始歸并段文件為輸出文件FO，內(nèi)存工作區(qū)為WA，F(xiàn)O和WA的初始狀態(tài)為空，并假設(shè)內(nèi)存工作區(qū)WA的容量為W個記錄，則生成初始歸并段的操作過程為：(1)從FI輸入W個記錄到工作區(qū)WA。(2)從WA中選關(guān)鍵字最小的記錄，記為MINKEY。(3)將MINKEY記錄輸出到FO中。(4)若FI不空，則從FI輸入下一個記錄到WA中。(5)從WA中選比MINKEY大的所有關(guān)鍵字中選最小的關(guān)鍵字，作為新的MINKEY。(6)重復（3）~（5），直到WA中選不出新的MINKEY為止，由此得到一個初始歸并段。(7)重復（2）~（6）直到WA為空。則得到全部初始歸并段。例如，給定初始文件含有24個記錄，對應的關(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。利用上面的方法生成初始歸并段過程如下表（假設(shè)內(nèi)存工作區(qū)WA的容量為6個記錄）。2023年11月28日7FOWAFI51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76第一歸并段51,49,39,46,38,2914,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,762951,49,39,46,38,1461,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,7629,3851,49,39,46,61,1415,30,1,48,52,3,63,27,4,13,89,24,46,58,33,7629,38,3951,49,15,46,61,1430,1,48,52,3,63,27,4,13,89,24,46,58,33,7629,38,39,4651,49,15,30,61,141,48,52,3,63,27,4,13,89,24,46,58,33,7629,38,39,46,4951,1,15,30,61,1448,52,3,63,27,4,13,89,24,46,58,33,7629,38,39,46,49,5148,1,15,30,61,1452,3,63,27,4,13,89,24,46,58,33,7629,38,39,46,49,51,6148,1,15,30,52,143,63,27,4,13,89,24,46,58,33,76表10-1生成初始歸并段2023年11月28日8第二歸并段148,3,15,30,52,1463,27,4,13,89,24,46,58,33,761,348,63,15,30,52,1427,4,13,89,24,46,58,33,761,3,1448,63,15,30,52,274,13,89,24,46,58,33,761,3,14,1548,63,4,30,52,2713,89,24,46,58,33,761,3,14,15,2748,63,4,30,52,1389,24,46,58,33,761,3,14,15,27,3048,63,4,89,52,1324,46,58,33,761,3,14,15,27,30,4824,63,4,89,52,1346,58,33,761,3,14,15,27,30,48,5224,63,4,89,46,1358,33,761,3,14,15,27,30,48,52,6324,58,4,89,46,1333,761,3,14,15,27,30,48,52,63,8924,58,4,33,46,1376表10-1生成初始歸并段(續(xù))2023年11月28日9第三歸并段424,58,76,33,46,134,1324,58,76,33,464,13,2458,76,33,464,13,24,3358,76,464,13,24,33,4658,764,13,24,33,46,58764,13,24,33,46,58,76表10-1生成初始歸并段(續(xù))2023年11月28日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上面的三個初始歸并段都是有序序列，故可以用二路平衡歸并進行排序或用三路平衡歸并進行排序。若用二路平衡歸并，可以得到如下結(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,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,46,46,48,49,51,52,58,61,63,76,89]2023年11月28日1110.2.2多路平衡歸并的實現(xiàn)1.多路平衡歸并的敗者樹將9.4.2節(jié)中樹形選擇排序得到的樹稱為勝者樹（每次選最小的關(guān)鍵字），因為每個非終端結(jié)點均表示其左、右孩子結(jié)點中的“勝者”。反之，若在雙親結(jié)點中記下剛進行比賽的“敗者”，而讓勝者去參加更高一層的比賽，則可以得到一棵“敗者樹”?，F(xiàn)以五路平衡歸并為例來建立“敗者樹”，假設(shè)已經(jīng)用前面的方法得到五個初始歸并段為（其中表示該段的結(jié)束）：第一歸并段B0：[17，21，]第二歸并段B1：[05，44，]第三歸并段B2：[10，12，]第四歸并段B3：[29，32，]第五歸并段B4：[15，56，]2023年11月28日12在建立“敗者樹”中，按完全二叉樹形式，從每個初始歸并段取一個關(guān)鍵字（第一個），作為“敗者樹”的葉子結(jié)點，用B[0]~B[4]表示，而非葉子結(jié)點用Ls[1]~Ls[4]表示，表示兩者比較的敗者，Ls[0]表示整個比較的勝者。B[3]和B[4]比較，B[3]為敗者，將它的段號存入Ls[4]中，B[3]和B[4]的勝者再與B[0]比較，敗者為B[0]，將它的段號存入Ls[2]中，B[1]與B[2]比較，敗者的段號存入Ls[3]中，B[0]、B[1]、B[2]、B[3]、B[4]比較的敗者段號存入Ls[1]中，勝者的段號存入Ls[0]中，得到的敗者樹見圖10-3。圖10-3五路歸并建立的初始敗者樹2023年11月28日132.多路平衡歸并的實現(xiàn)多路平衡歸并的實現(xiàn)，是反復調(diào)整敗者樹，并輸出Ls[0]的值，直到樹中葉結(jié)點都表示為?，F(xiàn)以五路平衡歸并舉例說明。【例10-1】假設(shè)有五個初始歸并段為（其中表示該段的結(jié)束）：第一歸并段B0：[17，21，]第二歸并段B1：[05，44，]第三歸并段B2：[10，12，]第五歸并段B4：[15，56，]第四歸并段B3：[29，32，]試用“敗者樹”實現(xiàn)五路平衡歸并，并給出歸并的結(jié)果。2023年11月28日14解：先建立初始敗者樹，然后不斷的調(diào)整敗者樹，并輸出Ls[0]所對應段的值，直到樹中葉結(jié)點都表示為。具體實現(xiàn)過程見圖10-4各步驟。（a）生成的初始敗者樹(b)輸出05后的敗者樹2023年11月28日15（c）輸出05,10后的敗者樹(d)輸出05,10,12后的敗者樹（e）輸出05,10,12,15后的敗者樹(f)輸出05,10,12,15,17后的敗者樹2023年11月28日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后敗者樹2023年11月28日17(k)輸出05,10,12,15,17,21,29,32,44,56后敗者樹圖10-4利用敗者樹實現(xiàn)五路平衡歸并2023年11月28日183.多路平衡歸并的算法實現(xiàn)#include<iostream.h>#defineMAXKEY32767//定義最大值#definemin0//定義最小值#definek5//K路平衡歸并intls[k];//敗者樹中非葉子結(jié)點的存儲空間intb[k+1];//敗者樹中葉子結(jié)點的存儲空間voidadjust(intls[k],ints){intt=(s+k)/2;inttemp;while(t>0){if(b[s]>b[ls[t]]){temp=s;s=ls[t];ls[t]=temp;}t=t/2;}ls[0]=s;}2023年11月28日19voidcreatelostt