外部排序課件

1、外存信息的存取

2、外部排序的方法

3、多路平衡歸并的實(shí)現(xiàn)

4、置換-選擇排序

5、最佳歸并樹(shù)

外部排序1、外存信息的存取1、外部排序： 待排序的記錄數(shù)量巨大，無(wú)法一次調(diào)入內(nèi)存，只能駐留在外存上（磁帶、磁盤、CD-ROM）上。不能使用內(nèi)部排序的方法進(jìn)行排序。否則將引起頻繁訪問(wèn)外存。外部排序主要的時(shí)間開(kāi)銷用在信息的內(nèi)、外存交換上，所以減少I/O時(shí)間成為要解決的主要問(wèn)題。2、常用外存：磁帶：由磁帶介質(zhì)、讀、寫磁頭、驅(qū)動(dòng)器、接收盤和原始盤組成。便宜、可反復(fù)使用、是一種順序存取設(shè)備。查找費(fèi)時(shí)、速度慢（尤其是查找末端記錄時(shí)）..磁帶機(jī)走向讀出頭寫入頭原始盤接收盤記錄1記錄3記錄2IRG（InterRecordGap）記錄間隙vt可靠讀寫區(qū)1、外存信息的存取磁帶信息的表示：一種磁化方向、代表1另一種磁化方向，代表001001001101011111、外存信息的存取磁帶文件的組織：記錄1記錄3記錄2IRG（InterRecordGap）記錄間隙

IRG：0.5~0.75inch，帶來(lái)的問(wèn)題是什么？

磁帶的利用率下降。例如：

密度1600byteperinch的帶。設(shè)每個(gè)記錄有80byte，如果IRG＝0.75inch;帶的利用率？讀寫頭記錄所用：(80/1600)＝0.005

inchIRG所用：0.75inch利用率＝0.005/(1+0.75)=1/16

必須改進(jìn)磁帶的利用率!1、外存信息的存取磁帶文件的組織的改進(jìn)：塊1塊3塊2IBG（InterBlockGap）塊間間隙

IBG：.5~.75inch，帶來(lái)的好處是磁帶的利用率上升如上例：設(shè)每一塊包含20個(gè)記錄每一塊所占20×80/1600＝1inch

利用率＝1/1+0.75=57%磁帶文件的讀寫時(shí)間：Ti/o=ta+n×tw ta

延遲時(shí)間：讀寫頭到達(dá)相應(yīng)的物理塊的起始位置的時(shí)間。

tw

讀/寫一個(gè)字符的時(shí)間；n字符數(shù)。由于磁帶是順序存取設(shè)備，在讀一個(gè)記錄時(shí)，必須先順序檢索，直到所需信息通過(guò)讀寫頭時(shí)才能得到。因此檢索速度很慢。磁帶主要用于存儲(chǔ)順序存取的大量數(shù)據(jù)。1、外存信息的存取1、外存信息的存取2）磁盤：結(jié)構(gòu)：由磁盤驅(qū)動(dòng)器、讀、寫磁頭、活動(dòng)臂、盤片（磁道、扇區(qū)）、旋轉(zhuǎn)主軸構(gòu)成。速度快、容量大、直接存取設(shè)備。柱面：各盤面的直徑相同的磁道的總和。物理位置：柱面號(hào)、磁道號(hào)、塊（扇區(qū)號(hào)）盤文件的讀寫時(shí)間：Ti/o=tseck+tla+n×twmtseck

(0.1秒)：找道時(shí)間；

tla

(<25豪秒)：等待時(shí)間twm(105個(gè)字符/秒)：傳輸時(shí)間/字符，n字符數(shù)。種類：固定頭磁盤、活動(dòng)頭磁盤固定頭磁盤：每個(gè)磁道都有一個(gè)磁頭（速度快）活動(dòng)頭磁盤：每個(gè)盤面共用一個(gè)磁頭，增加了找道的時(shí)間，應(yīng)用廣泛。2）磁盤：外部排序的基本過(guò)程2外部排序的方法１．按可用內(nèi)存大小,利用內(nèi)部排序方法，構(gòu)造若干個(gè)記錄的有序子序列寫入外存，通常稱這些記錄的有序子序列為“歸并段”;由相對(duì)獨(dú)立的兩個(gè)步驟組成：２．通過(guò)“歸并”，逐步擴(kuò)大(記錄的)有序子序列的長(zhǎng)度，直至外存中整個(gè)記錄序列按關(guān)鍵字有序?yàn)橹?。例如：假設(shè)有一個(gè)含10,000個(gè)記錄的磁盤文件，而當(dāng)前所用的計(jì)算機(jī)一次只能對(duì)1,000個(gè)記錄進(jìn)行內(nèi)部排序，則首先利用內(nèi)部排序的方法得到10個(gè)初始?xì)w并段，然后進(jìn)行逐趟歸并。假設(shè)進(jìn)行2路歸并(即兩兩歸并)，則第一趟由10個(gè)歸并段得到5個(gè)歸并段;最后一趟歸并得到整個(gè)記錄的有序序列。第三趟由3個(gè)歸并段得到2個(gè)歸并段;第二趟由5個(gè)歸并段得到3個(gè)歸并段;2外部排序的方法假設(shè)“數(shù)據(jù)塊”的大小為200，即每一次訪問(wèn)外存可以讀/寫200個(gè)記錄。則對(duì)于10,000個(gè)記錄，處理一遍需訪問(wèn)外存100次(讀和寫各50次)。分析上述外排過(guò)程中訪問(wèn)外存(對(duì)外存進(jìn)行讀/寫)的次數(shù)：1)求得10個(gè)初始?xì)w并段需訪問(wèn)外存100次;2)每進(jìn)行一趟歸并需訪問(wèn)外存100次;3)總計(jì)訪問(wèn)外存100+4100=500次2外部排序的方法外排總的時(shí)間還應(yīng)包括內(nèi)部排序所需時(shí)間和逐趟歸并時(shí)進(jìn)行內(nèi)部歸并的時(shí)間2外部排序的方法tIO值取決于外存，遠(yuǎn)遠(yuǎn)大于tIS和tmg。外部排序的時(shí)間取決于讀寫外存的次數(shù)d。外部排序總時(shí)間=產(chǎn)生初始?xì)w并段的時(shí)間m*tIS

+外存信息讀寫時(shí)間d*tIO+內(nèi)部歸并所需時(shí)間s*utmg例如:若對(duì)上述例子采用2路歸并,則只需進(jìn)行4趟歸并，外排所需總的時(shí)間：

10*tIS+500*tIO+4*1000*tmg若對(duì)上述例子采用5路歸并,則只需進(jìn)行2趟歸并，總的訪問(wèn)外存的次數(shù)為100+2100=300次2外部排序的方法一般情況下，假設(shè)待排記錄序列含m

個(gè)初始?xì)w并段，外排時(shí)采用k路歸并，則歸并趟數(shù)s=logkm，顯然，隨著k的增大或m的減小，歸并的趟數(shù)將減少，因此對(duì)外排而言，通常采用多路歸并。k的大小可選，但需綜合考慮各種因素。3多路平衡歸并的實(shí)現(xiàn)分析:

m個(gè)初始?xì)w并段，外排時(shí)采用k路歸并，則歸并趟數(shù)為logkm,K大，趟數(shù)減少，讀寫記錄的總數(shù)將減少。但K大，會(huì)使內(nèi)部歸并時(shí)間tmg增大?。一、多路平衡歸并的性質(zhì)：設(shè)從k個(gè)元素中挑選一個(gè)最小的元素需(k-1)次比較。每次比較耗費(fèi)的時(shí)間代價(jià)為

tmg，在進(jìn)行k路平衡歸并時(shí),要得到m個(gè)初始?xì)w并段,則內(nèi)部歸并過(guò)程中進(jìn)行的比較的總的次數(shù)為:

logkm×(k-1)×(n-1)×tmg=log2m×(k-1)/log2k×(n-1)×tmg

改進(jìn)：采用勝者樹(shù)或者敗者樹(shù)，從K個(gè)元素中挑選一個(gè)最小的元素僅需log2k

次比較，這時(shí)總的時(shí)間耗費(fèi)將下降為：

log2m×(n-1)×tmg

3多路平衡歸并的實(shí)現(xiàn)3多路平衡歸并的實(shí)現(xiàn)二、勝者樹(shù)及其使用195729595765432輸入緩沖區(qū)7654321559572995164952787122584912938576671922474859輸出緩沖區(qū)54路平衡歸并973多路平衡歸并的實(shí)現(xiàn)729169751649527871225849129385766719224748597654321輸入緩沖區(qū)輸出緩沖區(qū)779167299765432157二、勝者樹(shù)及其使用4路平衡歸并9123多路平衡歸并的實(shí)現(xiàn)1229169951649527871225849129385766719224748597654321輸入緩沖區(qū)輸出緩沖區(qū)9129161229976543215794路平衡歸并二、勝者樹(shù)及其使用3多路平衡歸并的實(shí)現(xiàn)改進(jìn)：采用勝者樹(shù)，從K個(gè)元素中選取最小元素之后，從根結(jié)點(diǎn)到它的相應(yīng)的葉子結(jié)點(diǎn)路徑上的結(jié)點(diǎn)都需要進(jìn)行修改，為了加快程序運(yùn)行的速度產(chǎn)生了敗者樹(shù)。采用勝者樹(shù)，從K個(gè)元素中挑選一個(gè)最小的元素僅需

log2m×(n-1)×tmg即內(nèi)部歸并時(shí)間與k無(wú)關(guān),K增大，歸并趟數(shù)logkm減少，讀寫外存次數(shù)減少，外排總時(shí)間減少。213多路平衡歸并的實(shí)現(xiàn)三、敗者樹(shù)及其使用7295935164952787122584912938576671922474859b[0]ls[1]輸入緩沖區(qū)輸出緩沖區(qū)97295729976543215注意：挑出冠軍需要進(jìn)行k-1次比較，此處需要比較3次。0ls[0]05ls[2]ls[3]b[1]b[2]b[3]4路平衡歸并203多路平衡歸并的實(shí)現(xiàn)三、敗者樹(shù)及其使用72916935164952787122584912938576671922474859b[0]ls[1]輸入緩沖區(qū)輸出緩沖區(qū)972957299765432157注意：挑出冠軍需要進(jìn)行k-1次比較，此處需要比較3次。1ls[0]05ls[2]ls[3]b[1]b[2]b[3]4路平衡歸并203多路平衡歸并的實(shí)現(xiàn)三、敗者樹(shù)及其使用122916915164952787122584912938576671922474859b[0]ls[1]輸入緩沖區(qū)輸出緩沖區(qū)9729572997654321579…注意：挑出冠軍需要進(jìn)行k-1次比較，此處需要比較3次。3ls[0]05ls[2]ls[3]b[1]b[2]b[3]4路平衡歸并

typedefintLoserTree[k]; typedefstruct{KeyTypekey; }Exnode,External[k+1];VoidK_Merge(LoserTree&ls，External&b){for(i=0;i<k;++i)input(b[i].key);

CreateLoserTree(ls);{while(b[ls[0]].key!=MAXKEY){q=ls[0];output(q);input(b[q].key);Adjust(ls,q);}output(ls[0]);}}//K_Merge四、利用敗者樹(shù)進(jìn)行k-路歸并算法的描述:voidAdjust(LoserTree&ls，ints)//從葉結(jié)點(diǎn)b[s]到根結(jié)點(diǎn)ls[0]的路徑調(diào)整敗者樹(shù){t=(s+k)/2;//ls[t]是b[s]的雙親結(jié)點(diǎn)while(t>0){if(b[s].key>b[ls[t].key)s<->ls[t];t=t/2;}ls[0]=s;}//Adjust四、調(diào)整敗者樹(shù)的算法描述如下:voidCreateLoserTree(LoserTree&ls)//已知b[0]到b[k-1]為完全二叉樹(shù)ls的葉子結(jié)點(diǎn)存有k個(gè)關(guān)鍵字,沿從葉結(jié)點(diǎn)到根的k條路徑將ls調(diào)整為敗者樹(shù).{b[k].key=MINKEY;//設(shè)MINKEY為關(guān)鍵字最小值.for(i=0;i<k;++i)ls[i]=k;//設(shè)置ls中“敗者”的初值.for(i=k-1;k>=0;--i)Adjust(ls,i);//依次從b[k-1],b[k-2],…,b[0]出發(fā)調(diào)整敗者.}//CreateLoserTree四、建立敗者樹(shù)的算法描述如下:4置換-選擇排序一、問(wèn)題的提出

m個(gè)初始?xì)w并段做k路平衡歸并排序時(shí)歸并的趟數(shù)為logkm.為了減少歸并趟數(shù)，也可以減小m的值。如何減小初始?xì)w并段的個(gè)數(shù)（也就是增加歸并段的長(zhǎng)度）?解決：在內(nèi)存長(zhǎng)度一定時(shí)，假設(shè)容納M條記錄，按照通常的排序方法，初始?xì)w并段的長(zhǎng)度可以是M一種更好的方法是使用置換選擇(replaceselection)算法，平均情況下可以產(chǎn)生可以生成兩倍內(nèi)存長(zhǎng)度的初始?xì)w并段。4、置換-選擇排序2.置換選擇排序置換選擇排序是堆排序的變體。輸入文件FI內(nèi)存工作區(qū)WA輸出文件Fo內(nèi)存工作區(qū)可容納w個(gè)記錄輸出緩沖輸入緩沖(1)從FI輸入W個(gè)記錄到WA；(2)從WA中選擇關(guān)鍵字最小的記錄，記為MINIMAX(3)將MINIMAX輸出到FO中；(4)若FI不空，從FI輸入下一個(gè)記錄到WA；(5)從WA中所有關(guān)鍵字比MINIMAX的關(guān)鍵字大的記錄中選出最小關(guān)鍵字記錄，作為新的MINIMAX記錄。(6)重復(fù)（3）-（5）直至WA中選不出新的MINIMAX。到此得到一個(gè)初始?xì)w并段（7）重復(fù)（2）-（6），直至WA為空。置換選擇排序的操作過(guò)程：實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI514939463829WAFO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI5149394638

14WA29FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI51494639

1461WA2938FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI514946

146115WA293839FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI514914611530WA29383946FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI51

146115301WA2938394649FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FA293839464951#FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FA29383946495161FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FA29383946495161#FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FA29383946495161#1FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI141530485263WA29383946495161#13FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI153048526327WA29383946495161#1314FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI153048526327WA29383946495161#1314FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI30485263274WA29383946495161#131415

FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI30485263413WA29383946495161#131415

27FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI48526341389WA29383946495161#131415

2730FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI52634138924WA29383946495161#131415

273048FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI63413892446WA29383946495161#131415

27304852FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI41389244658WA29383946495161#131415

2730485263FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI41324465833WA29383946495161#131415

273048526389#FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI132446583376WA29383946495161#131415

273048526389#4FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI2446583376WA29383946495161#131415

273048526389#413FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI46583376WA29383946495161#131415

273048526389#41324FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI465876WA29383946495161#131415

273048526389#4132433FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI5876WA29383946495161#131415

273048526389#413243346FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FI76WA29383946495161#131415

273048526389#41324334658FO實(shí)例：輸入文件FI中記錄關(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，假定使用的內(nèi)存可容納6個(gè)記錄，利用置換-選擇分類法產(chǎn)生初始合并段。514939463829146115301485236327413892446583376FIWA29383946495161#131415

273048526389#4132433465876#FO4、置換-選擇排序

3、長(zhǎng)度分析：設(shè)內(nèi)存可以存放m個(gè)記錄，則首先從文件讀入m記錄到內(nèi)存。這m個(gè)記錄肯定可以歸入本初始合并段內(nèi)。這樣，必須從文件中讀入m個(gè)記錄。這m個(gè)記錄中平均有一半可以歸入本合并段，一半歸入下一合并段。因此，合并段的平均長(zhǎng)度為：

m+m/2+m/4+…………=2m

所以，在平均情況下，合并段的平均長(zhǎng)度為2m。該結(jié)論由：E·F·Moore在1961年從置換－選擇排序同掃雪機(jī)的類比中得到的。 1)存儲(chǔ)結(jié)構(gòu)定義 可以用敗者樹(shù)的辦法加以實(shí)現(xiàn)。typedefstruct{RcdTyperec;//記錄KeyTypekey;//關(guān)鍵字intrnum;//所屬歸并段的段號(hào)}RcdNode,WorkArea[w];4、實(shí)現(xiàn)：2)模塊結(jié)構(gòu)圖Replace_selectionGet_run置換-選擇算法得到一個(gè)初始?xì)w并段Construct_LoserSelect_MiniMax選擇每個(gè)段中最小值voidReplace_Selection(LoserTree&ls,WorkArea&wa,FILE*fi,FILE*fo){Construct_Loser(ls,wa);rc=rmax=1;//rc為當(dāng)前生成段號(hào)，rmax為最大段的段號(hào)while(rc<=rmax){get_run(ls,wa);fwrite(RUNEND_SYMBLE,sizeof(structRcdType),1,fo);

rc=wa[ls[0]].rnum;}}//Replace_Selection3)模塊實(shí)現(xiàn)voidget_run(LoserTree&ls,WorkArea&wa){while(wa[ls[0]].rnum==rc){q=ls[0];minimax=wa[q].key;fwrite(&wa[q].rec,sizeof(structRcdType),1,fo);If(feof(fi){wa[q].rnum=rmax+1;wa[q].key=MAXKEY;}else{fread(&wa[q].rec,sizeof(structRcdType),1,fi);wa[q].key=wa[q].rec.key;If(wa[q].key<minimax){rmax=rc+1;wa[q].rnum=rmax;}elsewa[q].rnum=rc;}

select_MiniMax(ls,wa,q);}//while}//get_runvoidSelect_MiniMax(LoserTree&ls,WorkAreawa,intq){for(t=(w+q)/2,p=ls[t];t>0;t=t/2,p=ls[t])

if(wa[p].rnum<wa[q].rnum||wa[p].rnum==wa[q].rnum&&wa[p].key<wa[q].key)qls[t];ls[0]=q;}voidConstruct_Loser(LoserTree&ls,WorkArea&wa){for(i=0;i<w;++i)wa[i].rnum=wa[i].key=ls[i]=0;

for(i=w-1;i>=0;--i){fread(&wa[i].rec,sizeof(structRcdType),1,fi);wa[i].key=wa[i].rec.key;wa[i].rnum=1;

Select_MiniMa