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

1、 數(shù)據(jù)結(jié)構(gòu)課程本章內(nèi)容本章內(nèi)容11.1 11.1 外存信息的存取外存信息的存取11.2 11.2 外部排序的方法外部排序的方法11.3 11.3 多路平衡歸并的實現(xiàn)多路平衡歸并的實現(xiàn)11.4 11.4 置換置換- -選擇排序選擇排序11.5 11.5 最正確歸并樹最正確歸并樹中國科大數(shù)據(jù)結(jié)構(gòu)11.1 外存信息的存取中國科大數(shù)據(jù)結(jié)構(gòu)11.1 外存信息的存取記錄記錄 1記錄記錄 3記錄記錄 2中國科大數(shù)據(jù)結(jié)構(gòu)11.1 外存信息的存取中國科大數(shù)據(jù)結(jié)構(gòu)11.1 外存信息的存取中國科大數(shù)據(jù)結(jié)構(gòu)11.2 外部排序的方法中國科大數(shù)據(jù)結(jié)構(gòu)11.2 外部排序的方法中國科大數(shù)據(jù)結(jié)構(gòu)11.2 外部排序的方法中國科大

2、數(shù)據(jù)結(jié)構(gòu)11.2 外部排序的方法中國科大數(shù)據(jù)結(jié)構(gòu)11.2 外部排序的方法中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)729597654挑出冠軍挑出冠軍需求進(jìn)展需求進(jìn)展 k-1 次次比較比較, 此處需求此處需求比較比較 3 次。次。9553205176543210559572995中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)7291697654挑出亞軍挑出亞軍需求進(jìn)展需求進(jìn)展 log2k 次比較次比較, 此處需此處需求比較求比較 2次。次。97732071765432107791672997中國科大數(shù)據(jù)結(jié)構(gòu)1

3、1.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)920ls0ls1ls3ls2ls4b0b1b2b4b361525123748101515918202022402130612104中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)920ls0ls1ls3ls2ls4b0b1b2b4b315251237481015159182020224020141512103中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)typedef int LoserTreek;

4、 /敗者樹是完全二叉樹且不含葉子敗者樹是完全二叉樹且不含葉子, 可采用順序存儲可采用順序存儲構(gòu)造構(gòu)造typedef structKeyType key;ExNode, Externalk; /外結(jié)點外結(jié)點, 只存放待歸并記錄的關(guān)鍵碼只存放待歸并記錄的關(guān)鍵碼中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.3 多路平衡歸并的實現(xiàn)中國科大數(shù)據(jù)結(jié)構(gòu)11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11.4 置換-選擇排序中國科大數(shù)據(jù)結(jié)構(gòu)11.4 置換-選擇排序最小值最小值 最大值最大值值遞增值遞增記錄數(shù)記錄數(shù)記錄值分布按等概率記錄值分布按等概率當(dāng)前最小值當(dāng)前最小值段分界值段分界值展開的環(huán)路均均 勻勻 下下 雪雪W積雪(內(nèi)存容量)環(huán)路起、終點當(dāng)前車位當(dāng)前車位掃雪車在環(huán)形路上掃雪。將環(huán)路截斷展開，掃雪車在環(huán)形路上掃雪。將環(huán)路截斷展開，積雪截面為三角形如上圖積雪截面為三角形如上圖,其面積為其面積為W,那么車那么車走一圈掃走的面積為走一圈掃走的面積為2W.類比到置換類比到置換_選擇排選擇排序如黃字所示。序如黃字所示。中國科大數(shù)據(jù)結(jié)構(gòu)11.5 最正確歸并樹93012511831738262432121中國科大數(shù)據(jù)結(jié)構(gòu)11.5 最正確歸并樹236113091718