數(shù)據(jù)結(jié)構(gòu)第十一章外部排序

1、 數(shù)據(jù)結(jié)構(gòu)課程本章內(nèi)容本章內(nèi)容中國科大數(shù)據(jù)結(jié)構(gòu)11-3 11.1 外存信息的存取中國科大數(shù)據(jù)結(jié)構(gòu)11-4 11.1 外存信息的存取記錄記錄 1記錄記錄 3記錄記錄 2中國科大數(shù)據(jù)結(jié)構(gòu)11-5 11.1 外存信息的存取中國科大數(shù)據(jù)結(jié)構(gòu)11-6 11.1 外存信息的存取中國科大數(shù)據(jù)結(jié)構(gòu)11-7 11.2 外部排序的方法中國科大數(shù)據(jù)結(jié)構(gòu)11-8 11.2 外部排序的方法R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R2 有序文件有序文件中國科大數(shù)據(jù)結(jié)構(gòu)11-9 11.2 外部排序的方法中國科大數(shù)據(jù)結(jié)構(gòu)11-10 11.2 外部排序

2、的方法中國科大數(shù)據(jù)結(jié)構(gòu)11-11 11.2 外部排序的方法R1 R2 R3 R4 R5R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R6 R7 R8 R9 R10 R1 R2R1 R2 有序文件有序文件中國科大數(shù)據(jù)結(jié)構(gòu)11-12 11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11-13 11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11-14 11.3 多路平衡歸并的實現(xiàn)729597654挑出冠軍挑出冠軍需要進行需要進行 k-1 次次比較比較, 此處需要此處需要比較比較 3 次次。9553205176543210559572995中國科大數(shù)據(jù)結(jié)構(gòu)11-15 11.3 多路平衡歸并的實

3、現(xiàn)7291697654挑出亞軍挑出亞軍需要進行需要進行 log2k 次比較次比較, 此處需此處需要比較要比較 2次次。97732071765432107791672997中國科大數(shù)據(jù)結(jié)構(gòu)11-16 11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11-17 11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11-18 11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11-19 11.3 多路平衡歸并的實現(xiàn)920ls0ls1ls3ls2ls4b0b1b2b4b361525123748101515918202022402130612104中國科大數(shù)據(jù)結(jié)構(gòu)11-20 11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)1

4、1-21 11.3 多路平衡歸并的實現(xiàn)920ls0ls1ls3ls2ls4b0b1b2b4b315251237481015159182020224020141512103中國科大數(shù)據(jù)結(jié)構(gòu)11-22 11.3 多路平衡歸并的實現(xiàn)typedef int LoserTreek; /敗者樹是完全二叉樹且不含葉子敗者樹是完全二叉樹且不含葉子, 可采用順序存儲結(jié)構(gòu)可采用順序存儲結(jié)構(gòu)typedef structKeyType key;ExNode, Externalk; /外結(jié)點外結(jié)點, 只存放待歸并記錄的關(guān)鍵碼只存放待歸并記錄的關(guān)鍵碼中國科大數(shù)據(jù)結(jié)構(gòu)11-23 11.3 多路平衡歸并的實現(xiàn)void K_M

5、erge(LoserTree *ls, External *b) /k-路歸并處理程序利用敗者樹路歸并處理程序利用敗者樹ls將編號從將編號從0到到k-1的的k個輸入歸并段中的記錄歸并到輸出歸并段個輸入歸并段中的記錄歸并到輸出歸并段b0/到到bk-1為敗者樹上的為敗者樹上的k個葉子結(jié)點個葉子結(jié)點, 分別存放分別存放k個輸入歸并段中當前記錄的關(guān)鍵碼個輸入歸并段中當前記錄的關(guān)鍵碼for(i=0;i0) if(bs.keyblst.key) slst; /s指示新的勝者指示新的勝者 t=t/2; ls0=s;void CreateLoserTree(LoserTree *ls)/建立敗者樹建立敗者樹/

6、已知已知b0到到bk-1為完全二叉樹為完全二叉樹ls的葉子結(jié)點存有的葉子結(jié)點存有k個關(guān)個關(guān)/鍵碼鍵碼,沿從葉子到根的沿從葉子到根的k條路徑將條路徑將ls調(diào)整為敗者樹調(diào)整為敗者樹 bk.key=MINKEY; /設(shè)設(shè)MINKEY為關(guān)鍵碼可能的最小值為關(guān)鍵碼可能的最小值 for(i=0;i0;i-) Adjust(ls, i); /依次從依次從bk-1, bk-2, , b0出發(fā)調(diào)整敗者出發(fā)調(diào)整敗者中國科大數(shù)據(jù)結(jié)構(gòu)11-25 11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11-26 11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11-27 11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11-28 11.4 置換-選

7、擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11-29 11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11-30 11.4 置換-選擇排序最小值最小值 最大值最大值值遞增值遞增記錄數(shù)記錄數(shù)記錄值分布按等概率記錄值分布按等概率當前最小值當前最小值段分界值段分界值展開的環(huán)路均均 勻勻 下下 雪雪W積雪(內(nèi)存容量)環(huán)路起、終點當前車位當前車位掃雪車在環(huán)形路上掃雪。將環(huán)路截斷展開，掃雪車在環(huán)形路上掃雪。將環(huán)路截斷展開，積雪截面為三角形如上圖積雪截面為三角形如上圖,其面積為其面積為W,則車走則車走一圈掃走的面積為一圈掃走的面積為2W.類比到置換類比到置換_選擇排序選擇排序如黃字所示。如黃字所示。中國科大數(shù)據(jù)結(jié)構(gòu)11-31 11.5 最佳歸并樹93012511831738262432121中國科大數(shù)據(jù)結(jié)構(gòu)11-32 11.5