數(shù)據(jù)結(jié)構(gòu)演示文稿

數(shù)據(jù)結(jié)構(gòu)演示文稿1*現(xiàn)在是1頁\一共有134頁\編輯于星期五數(shù)據(jù)結(jié)構(gòu)2*現(xiàn)在是2頁\一共有134頁\編輯于星期五7.1引言

在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的次序是一種重要的關(guān)系。

排序的應(yīng)用：查詢結(jié)果需要按用戶指定的屬性排序。在已排序的數(shù)組中查找記錄可最多用O(log2n)時(shí)間。核對(duì)兩個(gè)已按學(xué)號(hào)排序的學(xué)生記錄表可用O(m+n)時(shí)間完成?，F(xiàn)在是3頁\一共有134頁\編輯于星期五

記錄—表示數(shù)據(jù)元素，具有一個(gè)或多個(gè)數(shù)據(jù)字段。

關(guān)鍵字—用于區(qū)分記錄的字段。

表—記錄的有限集合。給定一個(gè)記錄表（R0,R1,…,Rn-1），設(shè)記錄Ri的關(guān)鍵字值為Ki。關(guān)鍵字上存在一種次序關(guān)系<和一種相等關(guān)系=，使得對(duì)于任意兩個(gè)關(guān)鍵字值x和y，x=y，或x<y，或y<x。關(guān)系<滿足傳遞性。用x≤y表示x=y或x<y?，F(xiàn)在是4頁\一共有134頁\編輯于星期五

排序—確定一種置換p，使得記錄表（Rp(0),Rp(1),…,Rp(n-1)）的關(guān)鍵字滿足性質(zhì)Kp(0)≤Kp(1)≤…≤Kp(n-1)。簡(jiǎn)單而言，排序就是按關(guān)鍵字非遞減次序排列記錄。如果在輸入記錄表中Ki=Kj（i<j），且在排序后Ri在Rj之前，則稱相應(yīng)的排序方法是穩(wěn)定的。否則就是不穩(wěn)定的。根據(jù)整個(gè)排序過程能否在內(nèi)存中完成，可將排序方法分為內(nèi)排序和外排序?，F(xiàn)在是5頁\一共有134頁\編輯于星期五記錄的類定義：template<classKeyType>classElement{public:KeyTypegetKey()const

{returnkey;};//取記錄的關(guān)鍵字值

voidsetKey(KeyTypek){key=k;};//修改記錄的關(guān)鍵字//其它操作private:KeyTypekey; //關(guān)鍵字//其它字段…};假設(shè)在KeyType被實(shí)例化時(shí)，相應(yīng)實(shí)參類型的<、>、<=、>=和==等已定義。現(xiàn)在是6頁\一共有134頁\編輯于星期五7.2插入排序

插入排序的基本步驟：將記錄R插入一個(gè)已排好序的記錄序列R0,R1,…,Ri（K0≤K1≤…≤Ki）中，使得新的有i+2個(gè)記錄的序列也是排好序的。函數(shù)Insert實(shí)現(xiàn)了此步驟：template<classKeyType>voidinsert(constElement<KeyType>e,Element<KeyType>*list,

inti){//將e插入已排好序的list[0],…,list[i]中，//使結(jié)果序列也排好序。list至少可容納i+2個(gè)記錄。

while((i>=0)&&(e.getKey()<list[i].getKey())){//穩(wěn)定list[i+1]=list[i];i--; //list[i+1]總是可用于存放記錄

}list[i+1]=e;}現(xiàn)在是7頁\一共有134頁\編輯于星期五插入排序從序列R0開始，連續(xù)插入記錄R1,R2,…,Rn-1。n個(gè)記錄可以通過n–1次插入排序，如函數(shù)InsertionSort所示：template<classKeyType>voidInsertionSort(Element<KeyType>*list,

constintn){

for(intj=1;j<n;j++)insert(list[j],list,j–1);}

現(xiàn)在是8頁\一共有134頁\編輯于星期五分析：在最壞情況下，insert(e,list,i)在插入前要作i+1次比較。InsertionSort對(duì)i=j–1=0,1,…,n–2調(diào)用insert，其最壞情況時(shí)間復(fù)雜性是 O()=O(n2)插入排序的實(shí)際時(shí)間與輸入表的相對(duì)無序狀態(tài)有關(guān)。記錄Ri是左出序的當(dāng)且僅當(dāng)Ki<。現(xiàn)在是9頁\一共有134頁\編輯于星期五插入步驟中的循環(huán)只對(duì)左出序記錄迭代。設(shè)k是左出序記錄個(gè)數(shù)，則插入排序的時(shí)間是O((k+1)n)。當(dāng)k=0，插入排序的時(shí)間為O(n)。這說明，當(dāng)輸入表中左出序記錄很少時(shí)，插入排序的實(shí)際性能十分理想?，F(xiàn)在是10頁\一共有134頁\編輯于星期五例7.1設(shè)n=5，輸入關(guān)鍵字為5,4,3,2,1，則每次插入后表中記錄的排列如下：這時(shí)插入排序的性能達(dá)到最壞情況。

現(xiàn)在是11頁\一共有134頁\編輯于星期五例7.2設(shè)n=5，輸入關(guān)鍵字為2,3,4,5,1，則每次插入后表中記錄的排列如下：這時(shí)只有R4是左出序的。對(duì)于j=1,2,3，每次插入的時(shí)間只需O(1)；而對(duì)于j=4，插入時(shí)間為O(n)。

現(xiàn)在是12頁\一共有134頁\編輯于星期五插入排序是穩(wěn)定的。由于算法簡(jiǎn)單，對(duì)于較小的n（例如n≤20），插入排序幾乎是最快的。插入排序的改進(jìn)：1二分插入排序2鏈表插入排序現(xiàn)在是13頁\一共有134頁\編輯于星期五7.3希爾排序

希爾排序又稱為減少增量排序。以插入排序?yàn)榛A(chǔ)，并利用插入排序在最好情況下的性能，改善整個(gè)排序的性能。觀察輸入序列8,7,6,5,1,2,3,4，其中左出序記錄有7個(gè)。在插入排序中，首次交換8和7，只能減少1個(gè)左出序記錄。如果首次交換8和1，則可減少2個(gè)左出序記錄。現(xiàn)在是14頁\一共有134頁\編輯于星期五根據(jù)以上觀察，可以跨越式地交換記錄：將整個(gè)記錄表劃分為若干個(gè)子表，其相鄰記錄相隔incr個(gè)位置，incr稱為增量。利用插入排序?qū)γ總€(gè)子表排序，以快速減少整個(gè)表中的左出序記錄。每完成一次上述過程，增量減少，繼續(xù)利用插入排序?qū)Π葱略隽縿澐值拿總€(gè)子表排序。最后一次增量必須為1，這等同于普通的插入排序，但由于前面的預(yù)處理，整個(gè)記錄表已基本有序，此次插入排序有望快速完成?，F(xiàn)在是15頁\一共有134頁\編輯于星期五例7.3設(shè)n=8，輸入序列為8,7,6,5,1,2,3,4，取incr=4,2,1。處理過程如下所示：現(xiàn)在是16頁\一共有134頁\編輯于星期五增量的一個(gè)較有效的選擇是從incr=n/3+1開始，按incr=incr/3+1減少增量。由于跨越式交換，希爾排序是不穩(wěn)定的。為了反映增量，對(duì)InsertionSort及其調(diào)用的insert作少量修改，得到用于希爾排序的InsertionSort2以及insert2?，F(xiàn)在是17頁\一共有134頁\編輯于星期五template<classKeyType>voidinsert2(constElement<KeyType>e,Element<KeyType>*list,

inti,

intincr){

while((i>=0)&&(e.getKey()<list[i].getKey())){list[i+incr]=list[i];i-=incr; //list[i+incr]總可以存放記錄

}list[i+incr]=e;}

template<classKeyType>voidInsertionSort2(Element<KeyType>*list,constintn, intincr,intstart){//start表示子表開始下標(biāo)

for(intj=start;j<n;j+=incr)insert2(list[j+incr],list,j,incr);}

現(xiàn)在是18頁\一共有134頁\編輯于星期五進(jìn)一步可得希爾排序函數(shù)ShellSort：

template<classKeyType>voidShellSort(Element<KeyType>

*list,intn){intincr=n;do{ //對(duì)每個(gè)增量incr=incr/3+1;for(intstart=0;start<incr;start++)

//排序各子表

InsertionSort2(list,n,incr,start);}while(incr>1);}

現(xiàn)在是19頁\一共有134頁\編輯于星期五大規(guī)模實(shí)驗(yàn)研究表明：當(dāng)記錄個(gè)數(shù)n很大時(shí)，希爾排序?qū)τ涗浀囊苿?dòng)次數(shù)在n1.25到1.6n1.25的范圍之內(nèi)。這比插入排序有實(shí)質(zhì)性的改進(jìn)?，F(xiàn)在是20頁\一共有134頁\編輯于星期五7.4快速排序

插入排序?qū)⒖刂飘?dāng)前插入的基準(zhǔn)記錄Ri插入相對(duì)于已排好序的子表(R0,…,Ri–1)的正確位置，而快速排序?qū)⒒鶞?zhǔn)記錄Ri放在相對(duì)于整個(gè)記錄表的正確位置。設(shè)輸入表為(Rleft,…,Rright)，如果Ri放在位置s(i)，則有Kj≤Ks(i)（j<s(i)）和Kj≥Ks(i)（j>s(i)）?，F(xiàn)在是21頁\一共有134頁\編輯于星期五因此，根據(jù)Ri的關(guān)鍵字大小，整個(gè)記錄表被劃分為左子表(Rleft,…,Rs(i)–1)和右子表(Rs(i)+1,…,Rright)，如下圖所示：由于左、右子表的記錄分別在位置s(i)的左、右邊，可獨(dú)立地對(duì)這兩個(gè)子表排序。現(xiàn)在是22頁\一共有134頁\編輯于星期五基準(zhǔn)記錄可任意選取，在此選第一個(gè)記錄Rleft。

劃分記錄表：從左到右掃描，找到關(guān)鍵字大于等于Kleft的記錄Ri；從右到左掃描，找到關(guān)鍵字小于等于Kleft的記錄Rj；交換Ri和Rj；繼續(xù)上述過程，直到i，j錯(cuò)位?，F(xiàn)在是23頁\一共有134頁\編輯于星期五算法QuickSort給出了實(shí)現(xiàn)細(xì)節(jié)：template<classKeyType>voidQuickSort(Element<KeyType>*list,constintleft,constintright){//排序list[left],…,list[right]，任選list[left]為基準(zhǔn)記 //錄，假設(shè)list[left].key≤list[right+1].key。

if(left<right){

inti=left,j=right+1,pivot=list[left].getKey();

do{

doi++;while(list[i].getKey()<pivot);

doj--;while(list[j].getKey()>pivot);

if(i<j)InterChange(list,i,j);}while(i<j);現(xiàn)在是24頁\一共有134頁\編輯于星期五InterChange(list,left,j);QuickSort(list,left,j–1); //排序左子表QuickSort(list,j+1,right); //排序右子表}}

其中函數(shù)InterChange(list,a,b)交換記錄list[a]和list[b]。調(diào)用QuickSort(list,0,n–1)可對(duì)表list的第0到第n–1個(gè)記錄排序。為了簡(jiǎn)化邊界判斷，假設(shè)記錄list[n]的關(guān)鍵字不小于其余關(guān)鍵字?，F(xiàn)在是25頁\一共有134頁\編輯于星期五

例7.4設(shè)輸入表記錄的關(guān)鍵字為(26,5,37,1,61,11,59,15,48,19)，每次調(diào)用QuickSort時(shí)記錄表的狀態(tài)如下：現(xiàn)在是26頁\一共有134頁\編輯于星期五分析：用于劃分記錄表的時(shí)間是O(n)，設(shè)下面的c都是常數(shù)。（1）用Tworst(n)表示快速排序的最壞時(shí)間復(fù)雜性。在最壞情況下，兩個(gè)子表的長(zhǎng)度分別為n–1和0，因此Tworst(n)≤cn+Tworst(n–1) ≤cn+c(n–1)+Tworst(n–2) …≤c=cn(n+1)/2=O(n2)現(xiàn)在是27頁\一共有134頁\編輯于星期五（2）用Topt(n)表示快速排序的最佳時(shí)間復(fù)雜性。在最佳情況下，兩個(gè)子表的長(zhǎng)度相同，每個(gè)子表的長(zhǎng)度最多是n/2，因此Topt(n)≤cn+2Topt(n/2) ≤cn+2(cn/2+2Topt(n/4) ≤2cn+4Topt(n/4) … ≤cnlog2n+nTopt(1)=O(nlogn)現(xiàn)在是28頁\一共有134頁\編輯于星期五（3）根據(jù)下面的引理7.1，快速排序的平均時(shí)間復(fù)雜性也是O(nlogn)。而且，實(shí)驗(yàn)結(jié)果表明，快速排序的平均性能最好。

引理7.1：設(shè)Tavg(n)為快速排序的平均時(shí)間復(fù)雜性，則存在常數(shù)k，使得對(duì)于n≥2，Tavg(n)≤knlogen成立。

證明：在調(diào)用QuickSort(list,0,n–1)中，K0被放在位置j。兩個(gè)子表的長(zhǎng)度為j和n–1–j，相應(yīng)的平均時(shí)間是Tavg(j)+Tavg(n–1–j)。由于j可按同等概率取值0到n–1，因此現(xiàn)在是29頁\一共有134頁\編輯于星期五

Tavg(n)≤cn+

=cn+，n≥2 (7.1)設(shè)Tavg(0)≤b和Tavg(1)≤b，b為常數(shù)，k=2(b+c)。對(duì)n應(yīng)用歸納法可證，Tavg(n)≤knlogen（n≥2）?，F(xiàn)在是30頁\一共有134頁\編輯于星期五當(dāng)n=2，由(7.1)式可得：Tavg(2)≤2c+2b≤2kloge2。假設(shè)對(duì)于2≤n<m，Tavg(n)≤knlogen。則Tavg(m)≤cm+

=cm+

≤cm+ (7.2)現(xiàn)在是31頁\一共有134頁\編輯于星期五由于jlogej是j的遞增函數(shù)，由(7.2)式可得Tavg(m)≤cm+=cm+ =cm+=kmlogem+(cm+)現(xiàn)在是32頁\一共有134頁\編輯于星期五當(dāng)m≥2，cm+≤0，所以Tavg(m)≤kmlogem現(xiàn)在是33頁\一共有134頁\編輯于星期五

對(duì)基本快速排序算法的改進(jìn)：基準(zhǔn)記錄的選擇：選當(dāng)前記錄表的第一、中間和最后一個(gè)記錄中關(guān)鍵字為中間值的記錄。用排序小記錄表較快的方法如插入排序代替快速排序。當(dāng)需要排序的記錄表小于一定長(zhǎng)度時(shí)，快速排序已使整個(gè)表接近于排好序，這時(shí)對(duì)整個(gè)記錄表調(diào)用一次插入排序可使所有記錄就序?，F(xiàn)在是34頁\一共有134頁\編輯于星期五快速排序的最大遞歸深度是n。遞歸排序兩個(gè)子表中較小的，再用循環(huán)代替第二個(gè)遞歸，可使遞歸深度最多是O(logn)，如函數(shù)ImpQuickSort所示：template<classKeyType>voidImpQuickSort(Element<KeyType>*list,constintleft,constintright){//排序list[left],…,list[right]，任選list[left]為//基準(zhǔn)記錄，設(shè)list[left].keylist[right+1].key

while(left<right){

inti=left,j=right+1,pivot=list[left].getKey();

do{

doi++;while(list[i].getKey()<pivot);

doj--;while(list[j].getKey()>pivot);

if(i<j)InterChange(list,i,j);

}while(i<j);現(xiàn)在是35頁\一共有134頁\編輯于星期五InterChange(list,left,j);

if(right–j>=j–left){ //左子表較小ImpQuickSort(list,left,j–1);

left=j+1;}

else{ //右子表較小ImpQuickSort(list,j+1,right);

right=j–1;}

}}現(xiàn)在是36頁\一共有134頁\編輯于星期五設(shè)S(n)為ImpQuickSort所需的?？臻g，每層遞歸調(diào)用需要棧空間為c，則S(n)≤c+S(n/2)≤2c+S(n/4)…≤clog2n+S(1)=O(logn)。不難看出，快速排序是不穩(wěn)定排序?，F(xiàn)在是37頁\一共有134頁\編輯于星期五7.5歸并排序

7.5.1迭代歸并排序歸并排序的基礎(chǔ)是歸并，即將兩個(gè)已排序的表歸并為一個(gè)已排序的表。在迭代歸并排序中，需要?dú)w并的兩個(gè)表：(initListl,…,initListm)(initListm+1,…,initListn)生成的結(jié)果表是(mergedListl,…,mergedListn)?，F(xiàn)在是38頁\一共有134頁\編輯于星期五函數(shù)merge：template<classKeyType>voidmerge(Element<KeyType>*initList,Element<KeyType>*mergedList,constintl,constintm,constintn){

for(inti1=l,iResult=l,i2=m+1;i1<=m&&i2<=n;

iResult++)

if(initList[i1].getKey()<=initList[i2].getKey()){mergedList[iResult]=initList[i1];//穩(wěn)定i1++;

}

else{mergedList[iResult]=initList[i2];i2++;

}現(xiàn)在是39頁\一共有134頁\編輯于星期五if(i1>m)

for(intt=i2;t<=n;t++)mergedList[iResult+t-i2]=initList[t];

else

for(intt=i1;t<=m;t++)mergedList[iResult+t-i1]=initList[t];}

對(duì)merge的分析：for循環(huán)最多迭代n–l+1次。循環(huán)之外的if語句總共最多移動(dòng)n–l+1個(gè)記錄。因此，總時(shí)間是O(n–l+1)。所需的輔助空間是O(n–l+1)?，F(xiàn)在是40頁\一共有134頁\編輯于星期五

迭代歸并排序的基本思想：將有n個(gè)記錄的輸入表解釋為n個(gè)已排序表，每個(gè)表的長(zhǎng)度為1。成對(duì)歸并這些表，得到n/2個(gè)已排序表，每個(gè)表的長(zhǎng)度為2（如果n是奇數(shù)，則最后一個(gè)表的長(zhǎng)度為1）。再歸并這n/2個(gè)表，如此繼續(xù)直到只剩下一個(gè)已排序的表?，F(xiàn)在是41頁\一共有134頁\編輯于星期五例7.5對(duì)輸入表(26,5,77,61,11,59,15,48,19)，的每一遍掃描中歸并子表的過程：現(xiàn)在是42頁\一共有134頁\編輯于星期五可見，需要對(duì)輸入表進(jìn)行多次歸并掃描。設(shè)掃描時(shí)輸入表中已排序子表的長(zhǎng)度為len（最后一個(gè)子表的長(zhǎng)度可能小于len），則經(jīng)過一次歸并掃描后已排序子表的長(zhǎng)度變?yōu)?len，如下所示：現(xiàn)在是43頁\一共有134頁\編輯于星期五用i作為掃描指針，指向需歸并的兩個(gè)子表的前一個(gè)的第一記錄，并隨著歸并的完成向右移動(dòng)。如果i≤n–2len，則至少還有兩個(gè)長(zhǎng)度都是len的子表需要?dú)w并，否則需要作特殊邊界處理。現(xiàn)在是44頁\一共有134頁\編輯于星期五函數(shù)MergePass：template<classKeyType>voidMergePass(Element<KeyType>*initList,Element<KeyType>*resultList,constintn,constintlen){//一遍歸并掃描。將表initList的相鄰子表歸并到表resultList

for(inti=0;i<=n–2len;i+=2len)merge(initList,resultList,i,i+len–1,i+2len–1);//剩下的記錄數(shù)<2len

if(i+len–1<n–1) //歸并最后兩個(gè)長(zhǎng)短不一的子表merge(initList,resultList,i,i+len–1,n–1);

elsefor(intt=i;t<=n–1;t++)resultList[t]=initList[t]; //復(fù)制最后一個(gè)子表}現(xiàn)在是45頁\一共有134頁\編輯于星期五函數(shù)MergeSort反復(fù)調(diào)用MergePass完成排序：template<classKeyType>voidMergeSort(Element<KeyType>*list,constintn){

Element<KeyType>*tempList=newElement<KeyType>

[n];

for(intl=1;l<n;l*=2){//l是當(dāng)前被歸并子表的長(zhǎng)度MergePass(list,tempList,n,l);l*=2;MergePass(tempList,list,n,l);//最后一遍可能只是復(fù)制

}

delete[]tempList;}現(xiàn)在是46頁\一共有134頁\編輯于星期五

對(duì)MergeSort的分析：對(duì)輸入表進(jìn)行多次掃描。第1遍歸并長(zhǎng)度為1的表，第2遍歸并長(zhǎng)度為2的表。第i遍掃描歸并長(zhǎng)度為2i-1的表?？偣残枰猯og2n次掃描。每遍掃描的時(shí)間為O(n)。歸并排序的總時(shí)間為O(nlogn)。不難看出，歸并排序是穩(wěn)定排序?，F(xiàn)在是47頁\一共有134頁\編輯于星期五7.5.2遞歸歸并排序

遞歸歸并排序的基本思想：將記錄表劃分成大致等長(zhǎng)的左、右子表。遞歸排序這些子表。再歸并已排序的子表，從而使整個(gè)記錄表就序?，F(xiàn)在是48頁\一共有134頁\編輯于星期五

例7.6對(duì)輸入表(26,5,77,61,11,59,15,48,19)進(jìn)行遞歸歸并排序過程中的子表劃分：現(xiàn)在是49頁\一共有134頁\編輯于星期五將子表從一個(gè)數(shù)組歸并到另一個(gè)數(shù)組需要復(fù)制數(shù)據(jù)。采用鏈表表示可避免數(shù)據(jù)復(fù)制。假設(shè)每個(gè)元素至少有兩個(gè)字段：link和key，其結(jié)構(gòu)定義如下：template<classKeyType>classElement{private:KeyTypekey; //關(guān)鍵字

intlink;//其它字段public:Element(){link=-1;}; //-1表示空指針};

現(xiàn)在是50頁\一共有134頁\編輯于星期五

假設(shè)：所有訪問Element私有數(shù)據(jù)成員的的函數(shù)已聲明為Element的友元。list[i].key和list[i].link分別是記錄i的key和link字段的值（0≤i≤n–1）。初始時(shí)list[i].link=–1（0≤i≤n–1），即每個(gè)記錄構(gòu)成一個(gè)只含其本身的鏈表?，F(xiàn)在是51頁\一共有134頁\編輯于星期五函數(shù)ListMerge(list,start1,start2)將兩個(gè)由start1和start2指向的按關(guān)鍵字非遞減次序鏈接的鏈表歸并為一個(gè)按關(guān)鍵字非遞減次序鏈接的鏈表，并返回首記錄指針：template<classKeyType>intListMerge(Element<KeyType>*list,constintstart1,constintstart2){//將分別由start1和start2指向的已排序鏈表歸并為 //一個(gè)已排序鏈表，并返回其首記錄的下標(biāo)。記錄 //之間通過整型下標(biāo)鏈接。

intiResult,iStart,i1,i2;

if(list[start1].key<=list[start2].key){//定位結(jié)果表的首記錄iStart=iResult=start1;i1=list[start1].link;i2=start2;

}現(xiàn)在是52頁\一共有134頁\編輯于星期五e(cuò)lse{iStart=iResult=start2;i2=list[start2].link;i1=start1;

}while(i1<>-1&&i2<>-1) //歸并

if(list[i1].key<=list[i2].key){list[iResult].link=i1;iResult=i1;i1=list[i1].link;

}else{list[iResult].link=i2;iResult=i2;i2=list[i2].link;

}

if(i1==-1)list[iResult].link=i2; //鏈接剩余部分

elselist[iResult].link=i1;

returniStart;}現(xiàn)在是53頁\一共有134頁\編輯于星期五函數(shù)rMergeSort利用ListMerge實(shí)現(xiàn)遞歸歸并排序，并返回已排好序鏈表的首記錄指針：template<classKeyType>intrMergeSort(Element<KeyType>*list,constintleft,constintright){ //將list[left],…,list[right]按key排序。返回已 //排序鏈表的首記錄下標(biāo)。

if(left>=right)returnleft; //最多只含一個(gè)記錄

intmid=(left+right)/2;//分別排序左、右半部分，并歸并所得的兩個(gè)已排序鏈表

returnListMerge(list,rMergeSort(list,left,mid),rMergeSort(list,mid+1,right));}當(dāng)需要對(duì)list[0],…,list[n–1]排序時(shí)，可調(diào)用rMergeSort(list,0,n–1)。此排序也是穩(wěn)定的?，F(xiàn)在是54頁\一共有134頁\編輯于星期五7.6堆排序

堆排序只需要O(1)的輔助空間，同時(shí)其最壞和平均時(shí)間復(fù)雜性也都是O(nlogn)。堆排序通過最大堆的插入和刪除操作實(shí)現(xiàn)排序：首先將n個(gè)記錄插入一個(gè)初始為空的堆，接著逐個(gè)從堆中取出記錄。然而，還可以通過函數(shù)adjust更快地構(gòu)建具有n個(gè)記錄的堆。給定一棵二叉樹T，其左、右子樹都滿足最大堆的性質(zhì)，但其根結(jié)點(diǎn)卻不一定滿足，函數(shù)adjust調(diào)整T使得整個(gè)二叉樹都滿足最大堆性質(zhì)?，F(xiàn)在是55頁\一共有134頁\編輯于星期五template<classKeyType>voidadjust(Element<KeyType>*tree,constintroot,constintn){ //結(jié)點(diǎn)下標(biāo)不大于nElement<KeyType>e=tree[root];

intk=e.getKey();

for(intj=2*root;j<=n;j*=2){

if(j<n)//j一定有右兄弟

if(tree[j].getKey()<tree[j+1].getKey())j++; //較大者

if(k>=tree[j].getKey())break;//如果k不小于左、右子女 //中的較大者，則e可放在j的雙親處tree[j/2]=tree[j];//將第j個(gè)記錄上移

}tree[j/2]=e;}設(shè)以root為根的樹深為d，其計(jì)算時(shí)間為O(d)?，F(xiàn)在是56頁\一共有134頁\編輯于星期五算法HeapSort首先利用函數(shù)adjust構(gòu)建最大堆，如下圖所示：現(xiàn)在是57頁\一共有134頁\編輯于星期五接著對(duì)記錄表list作n–1遍處理，每次將當(dāng)前最大堆的第一個(gè)記錄與最后一個(gè)交換，并將當(dāng)前最大堆記錄數(shù)減少1，重新調(diào)整。由于第一個(gè)記錄的關(guān)鍵字總是堆中最大的，經(jīng)過交換該記錄一定是就序的。調(diào)用HeapSort(list,n)即可對(duì)list[1],…,list[n]排序。

現(xiàn)在是58頁\一共有134頁\編輯于星期五template<classKeyType>voidHeapSort(Element<KeyType>*list,constintn){//按關(guān) //鍵字非遞減次序排序list[1],…,list[n]

for(inti=n/2;i>=1;i--) //將list轉(zhuǎn)化為最大堆a(bǔ)djust(list,i,n);

for(i=n–1;i>=1;i--){ //排序listElement<KeyType>t=list[i+1];list[i+1]=list[1];

list[1]=t; //交換list[1]和list[i+1]adjust(list,1,i); //重建堆

}}

現(xiàn)在是59頁\一共有134頁\編輯于星期五

例7.7用HeapSort對(duì)(26,5,77,1,61,11,59,15,48,19)的排序過程：現(xiàn)在是60頁\一共有134頁\編輯于星期五現(xiàn)在是61頁\一共有134頁\編輯于星期五現(xiàn)在是62頁\一共有134頁\編輯于星期五現(xiàn)在是63頁\一共有134頁\編輯于星期五現(xiàn)在是64頁\一共有134頁\編輯于星期五

分析：設(shè)2k–1≤n<2k，則與記錄表對(duì)應(yīng)的完全二叉樹有k層，第i層的結(jié)點(diǎn)數(shù)≤2i–1。第一個(gè)for循環(huán)對(duì)每個(gè)有子女的結(jié)點(diǎn)調(diào)用adjust一次。該循環(huán)的時(shí)間不大于各層結(jié)點(diǎn)數(shù)與該層結(jié)點(diǎn)可移動(dòng)的最大距離的積之和，即第二個(gè)for循環(huán)調(diào)用adjust共n–1次，最大深度為log2(n+1)。因此，堆排序的總計(jì)算時(shí)間是O(nlogn)。而且，只需要O(1)輔助空間?，F(xiàn)在是65頁\一共有134頁\編輯于星期五7.7基數(shù)排序

當(dāng)n個(gè)記錄的關(guān)鍵字list[i].key（0≤i<n）的取值是0到n–1范圍內(nèi)的整數(shù)時(shí)，可以用下列代碼對(duì)其排序：for(inti=0;i<n;i++)result[list[i].key]=list[i];這里用關(guān)鍵字值來確定記錄在最終就序數(shù)組中的位置。這就是最基本的箱排序。其中，我們?yōu)閚個(gè)關(guān)鍵字值安排n個(gè)箱子，并根據(jù)關(guān)鍵字值將記錄分配到對(duì)應(yīng)的箱中。此方法效率極高，無論記錄關(guān)鍵字的初始順序如何，只需要O(n)時(shí)間即可完成排序?，F(xiàn)在是66頁\一共有134頁\編輯于星期五在實(shí)際應(yīng)用中，一個(gè)箱子可以存放多個(gè)記錄，同時(shí)關(guān)鍵字的取值范圍不必與n直接關(guān)聯(lián)。為了有效地利用箱排序的思想，可以將關(guān)鍵字解釋為多個(gè)子關(guān)鍵字：K0,…,Kd–1（K0是最高位，Kd–1是最低位）。如果記錄表R0,…,Rn-1中的任意兩個(gè)記錄Ri和Rj（0≤i<j<n）都滿足則稱該記錄表相對(duì)于關(guān)鍵字(K0,…,Kd–1)已排好序。

現(xiàn)在是67頁\一共有134頁\編輯于星期五例如，排序100張關(guān)鍵字值為0到99的卡片可看成對(duì)兩個(gè)子關(guān)鍵字K0和K1的排序，其中K0對(duì)應(yīng)十位，K1對(duì)應(yīng)個(gè)位。我們按最低位優(yōu)先（簡(jiǎn)稱LSD）策略應(yīng)用箱排序解決此問題：首先根據(jù)K1將卡片逐張分配到0號(hào)箱到9號(hào)箱中。接著，將8號(hào)箱的卡片放在9號(hào)箱的之前，…，將0號(hào)箱的卡片放在1號(hào)箱的之前。再根據(jù)K0按照穩(wěn)定排序的要求將卡片逐張分配到0號(hào)箱到9號(hào)箱中，按照從0到9的箱號(hào)順序收集即得到已排序的卡片。現(xiàn)在是68頁\一共有134頁\編輯于星期五可見，如果關(guān)鍵字是十進(jìn)制數(shù)，可將其中的每個(gè)十進(jìn)制位看成一個(gè)子關(guān)鍵字，并按LSD策略用10個(gè)箱子對(duì)每個(gè)子關(guān)鍵字進(jìn)行箱排序。一般地，在基數(shù)排序中，用基數(shù)r分解關(guān)鍵字。當(dāng)r=10，則得到上述十進(jìn)制分解。如果關(guān)鍵字是長(zhǎng)度為d的小寫英文標(biāo)識(shí)符，則可分解為d個(gè)子關(guān)鍵字(K0,…,Kd–1)，其中，Ki

{‘a(chǎn)’,‘b’,…,‘z’}（0≤i<d），r=26。基數(shù)r排序需要r個(gè)箱子?，F(xiàn)在是69頁\一共有134頁\編輯于星期五假設(shè)記錄表是R0,…,Rn-1。關(guān)鍵字用基數(shù)r分解，每個(gè)分解為d位，每位的取值是0到r–1，則需要r個(gè)箱子。記錄元素的類定義如下：classElement{public:…private:intkey[d]; //關(guān)鍵字?jǐn)?shù)組，d是常數(shù)

//其它字段…intlink;};現(xiàn)在是70頁\一共有134頁\編輯于星期五每個(gè)箱子中的記錄鏈接成隊(duì)列，f[i]和e[i]（0≤i<r）分別指向第i個(gè)箱子的首、尾記錄。函數(shù)RadixSort給出了用LSD策略實(shí)現(xiàn)基數(shù)r排序的細(xì)節(jié)：intRadixSort(Element*list,constintd,constintn){ //按關(guān)鍵字key[0],…key[d-1]排序(list[0],…,list[n-1])， //0≤key[i]<radix，radix是常數(shù)

intf[radix],e[radix];//radix個(gè)隊(duì)列的首、尾指針

for(inti=0;i<n–1;i++)list[i].link=i+1;

list[n–1].link=-1;intcurrent=0; //鏈接成一個(gè)以current開 //頭的鏈表，用-1表示空指針現(xiàn)在是71頁\一共有134頁\編輯于星期五for(i=d–1;i>=0;i--){ //對(duì)key[i]排序

for(intj=0;j<r;j++)f[j]=-1;//初始化所有箱子

for(;current<>-1;current=list[current].link){//分配記錄

intk=list[current].key[i];

if(f[k]==-1)f[k]=current;elselist[e[k]].link=current;e[k]=current;

}

for(j=0;f[j]==-1;j++); //找到第一個(gè)非空隊(duì)列current=f[j];intlast=e[j];

for(intk=j+1;k<r;k++) //拼接剩余隊(duì)列

if(f[k]<>-1){list[last].link=f[k];last=e[k];}list[last].link=-1;}//for(i=d-1;i>=0;i--)結(jié)束

returnf[0]; //返回已就序鏈表的第一個(gè)記錄下標(biāo)}現(xiàn)在是72頁\一共有134頁\編輯于星期五分析：RadixSort對(duì)數(shù)據(jù)作d遍掃描，每遍掃描用O(n+r)時(shí)間，總計(jì)算時(shí)間是O(d(n+r))。

例7.8設(shè)需要排序的10個(gè)數(shù)的取值范圍是[0,999]。數(shù)的每一位作為一個(gè)子關(guān)鍵字，d=3，r=10。排序過程如后面兩頁所示?，F(xiàn)在是73頁\一共有134頁\編輯于星期五現(xiàn)在是74頁\一共有134頁\編輯于星期五現(xiàn)在是75頁\一共有134頁\編輯于星期五現(xiàn)在是76頁\一共有134頁\編輯于星期五7.8基于鏈表和映射表排序結(jié)果的順序化

對(duì)于基于鏈表的排序結(jié)果，有時(shí)需要按次序就地重新排列，使它們?cè)谖锢砩弦彩琼樞虻摹ＴO(shè)記錄表R0,…,Rn-1經(jīng)排序后的結(jié)果是一個(gè)按關(guān)鍵字非遞減次序鏈接的鏈表，且first是鏈表的首記錄指針。將記錄R0和Rfirst交換。如果first0，則表中應(yīng)有一個(gè)記錄Rx，其link字段值為0。如果能夠修改Rx的link字段，使其指向原位于R0的記錄的新位置first，則剩余記錄R1,…,Rn-1也是按關(guān)鍵字非遞減次序鏈接的?，F(xiàn)在是77頁\一共有134頁\編輯于星期五但在單鏈表中，我們無法快速確定結(jié)點(diǎn)R0的前驅(qū)Rx。于是可將R0的link字段設(shè)置為first，表示原位于R0的記錄已移到Rfirst。這樣，R0還作為R1,…,Rn-1鏈表中的虛擬結(jié)點(diǎn)。借助此虛擬結(jié)點(diǎn)，我們可找到剩余記錄鏈表的首結(jié)點(diǎn)。重復(fù)上述過程n–1次即可完成重新排列。一般地，設(shè)記錄表R0,…,Ri-1已在物理上按序排列，Rfirst是剩余記錄Ri,…,Rn-1鏈表的首記錄，記錄Ri和Rfirst交換后，將新Ri記錄的link字段設(shè)置為first，表示原位于Ri的記錄已移到Rfirst?，F(xiàn)在是78頁\一共有134頁\編輯于星期五同時(shí)，注意到作為剩余記錄Ri,…,Rn-1鏈表的首記錄下標(biāo)的first總是大于或等于i，我們可以經(jīng)過虛擬結(jié)點(diǎn)，找到剩余記錄鏈表的首記錄下標(biāo)。函數(shù)list實(shí)現(xiàn)了上述方法：template<classKeyType>voidlist(Element<KeyType>*list,constintn,intfirst){//重新排序由first指向的鏈表中的記錄，使list[0],…,list[n-1]//中的關(guān)鍵字按非遞減次序排列

for(inti=0;i<n–1;i++){

//找到應(yīng)放到位置i的記錄。由于位置0,1,…,i-1的記錄已//就位，該記錄下標(biāo)一定≥i

while(first<i)first=list[first].link; //經(jīng)過虛擬結(jié)點(diǎn)現(xiàn)在是79頁\一共有134頁\編輯于星期五

intq=list[first].link; //listq是按非遞減次序的下一個(gè) //記錄，可能是虛擬記錄

if(first!=i){ //交換list[i]和list[first]，并將list[i].link //設(shè)置為原list[i]的新位置Element<KeyType>t=list[i];list[i]=list[first];

list[first]=t;list[i].link=first;

}first=q;}}

現(xiàn)在是80頁\一共有134頁\編輯于星期五例7.9對(duì)(26,5,77,1,61,11,59,15,48,19)進(jìn)行鏈表排序后，所得鏈表如下所示：現(xiàn)在是81頁\一共有134頁\編輯于星期五list的for循環(huán)每次迭代后記錄表的狀態(tài)如下，變化用粗體字表示，虛擬結(jié)點(diǎn)的link字段用帶下劃線的字體表示：現(xiàn)在是82頁\一共有134頁\編輯于星期五現(xiàn)在是83頁\一共有134頁\編輯于星期五現(xiàn)在是84頁\一共有134頁\編輯于星期五現(xiàn)在是85頁\一共有134頁\編輯于星期五現(xiàn)在是86頁\一共有134頁\編輯于星期五

對(duì)list的分析：設(shè)有n個(gè)記錄，for循環(huán)迭代n–1次。每次最多交換2個(gè)記錄，需要3次記錄移動(dòng)。如果每個(gè)記錄的長(zhǎng)度為m，則每次交換的代價(jià)是3m。所以，最壞情況下記錄移動(dòng)的總代價(jià)是O(mn)。在while循環(huán)中，任何結(jié)點(diǎn)最多被檢查一次，所以while循環(huán)的總時(shí)間是O(n)。顯然，list所需的輔助空間是O(1)?，F(xiàn)在是87頁\一共有134頁\編輯于星期五鏈表排序不適用于希爾排序、快速排序和堆排序，因?yàn)橛涗洷淼捻樞虮硎臼沁@些方法的基礎(chǔ)。對(duì)于這些方法可以采用映射表t，表的每一個(gè)單元對(duì)應(yīng)一個(gè)記錄。映射表單元起著對(duì)記錄間接尋址的作用。排序開始時(shí)，t[i]=i，0≤i≤n–1。如果要求交換Ri和Rj，則只需交換表單元t[i]和t[j]。排序結(jié)束時(shí)，關(guān)鍵字最小的記錄是Rt[0]，最大的記錄是Rt[n-1]，所要求的記錄排列是Rt[0],Rt[1],…,Rt[n-1]，如下一頁所示。現(xiàn)在是88頁\一共有134頁\編輯于星期五現(xiàn)在是89頁\一共有134頁\編輯于星期五有時(shí)為了避免間接尋址，還需要根據(jù)映射表t確定的置換在物理上重新排列記錄。整個(gè)置換由不相交的環(huán)路組成。含記錄i的環(huán)路由i,t[i],t2[i],…,tk[i]構(gòu)成，且tk[i]=i。例如，上一頁的置換由兩個(gè)環(huán)路組成，第一個(gè)包含記錄R0和R4，第二個(gè)包含記錄R1，R3和R2。

函數(shù)table首先沿著包含R0的環(huán)路將記錄移到其正確位置。接著，如果包含R1的環(huán)路未被移動(dòng)過，則沿著該環(huán)路將記錄移到其正確位置。由此繼續(xù)移動(dòng)包含R2,R3,…,Rn-2的環(huán)路，最終得到物理上就序的記錄表?，F(xiàn)在是90頁\一共有134頁\編輯于星期五template<classKeyType>voidtable(Element<KeyType>*list,constintn,int*t){//重新排列l(wèi)ist[0],…,list[n-1]，使其對(duì)應(yīng)序列l(wèi)ist[t[0]],…,//list[t[n-1]],n≥1

for(inti=0;i<n–1;i++)

if(t[i]!=i){ //存在一個(gè)開始于i的非平凡環(huán)路Element<KeyType>p=list[i];intj=i;

do{

intk=t[j];list[j]=list[k];t[j]=j;j=k;

}while(t[j]!=i);list[j]=p;//p中的記錄應(yīng)該移到位置jt[j]=j;}}現(xiàn)在是91頁\一共有134頁\編輯于星期五例7.10一個(gè)根據(jù)映射表t對(duì)記錄順序化的例子：現(xiàn)在是92頁\一共有134頁\編輯于星期五

對(duì)table的分析：設(shè)每個(gè)記錄占用m個(gè)存儲(chǔ)單元，則所需輔助空間為O(m)個(gè)存儲(chǔ)單元。for循環(huán)執(zhí)行了n–1次。如果對(duì)于某些i的取值，t[i]i，則存在一個(gè)包含k>1個(gè)不同記錄Ri,Rt[i],…,Rtk-1[i]的環(huán)路。重新排列這些記錄需要k+1次移動(dòng)。設(shè)kj是在for循環(huán)中i=j時(shí)以Rj開頭的非平凡環(huán)路的記錄個(gè)數(shù)。對(duì)于平凡環(huán)路，則令kj=0。記錄移動(dòng)的總次數(shù)是現(xiàn)在是93頁\一共有134頁\編輯于星期五當(dāng)=n且存在n/2個(gè)非平凡環(huán)路時(shí)，記錄移動(dòng)的總次數(shù)達(dá)到最大值—3n/2。移動(dòng)一個(gè)記錄的代價(jià)是O(m)，總的計(jì)算時(shí)間是O(mn)?，F(xiàn)在是94頁\一共有134頁\編輯于星期五7.9外排序7.9.1概述需要排序的記錄表大到計(jì)算機(jī)內(nèi)存不能容納時(shí)，內(nèi)排序已不足以解決問題。假設(shè)需要排序的記錄表存放在磁盤上。由于計(jì)算機(jī)訪問內(nèi)存的速度比訪問磁盤的速度快得多，影響外排序性能的主要是訪問磁盤的次數(shù)。磁盤的讀、寫以IO塊為單位。一個(gè)IO塊通常可包含多個(gè)記錄?，F(xiàn)在是95頁\一共有134頁\編輯于星期五影響磁盤讀寫時(shí)間的有以下三個(gè)因素：

尋找時(shí)間：將讀寫頭定位于正確的柱面所用時(shí)間。

等待時(shí)間：本磁道中所需塊旋轉(zhuǎn)到讀寫頭下所用時(shí)間。

傳輸時(shí)間：將塊中數(shù)據(jù)讀入內(nèi)存或?qū)懙酱疟P所用時(shí)間。其中，就數(shù)據(jù)傳輸而言，尋找和等待都是輔助性的，但其時(shí)間卻較長(zhǎng)。為了提高傳輸效率，IO塊的容量一般都較大，通?？砂瑪?shù)千字節(jié)?，F(xiàn)在是96頁\一共有134頁\編輯于星期五外排序的最基本方法是歸并，包括兩個(gè)階段：（1）根據(jù)內(nèi)存容量將輸入記錄表分為若干段，并利用某種內(nèi)排序方法逐個(gè)對(duì)這些段排序。這些已排序的段又稱為歸并段（runs）。（2）歸并第一階段生成的歸并段，直到最終只剩一個(gè)歸并段。由于歸并算法只要求同一時(shí)刻兩個(gè)歸并段的前端記錄在內(nèi)存，因此經(jīng)過歸并，可以生成比內(nèi)存大的歸并段?，F(xiàn)在是97頁\一共有134頁\編輯于星期五

例7.11設(shè)記錄表有4500個(gè)記錄，可用于排序的計(jì)算機(jī)內(nèi)存容量是750個(gè)記錄，IO塊長(zhǎng)度是250個(gè)記錄。按上述方法，排序步驟如下：現(xiàn)在是98頁\一共有134頁\編輯于星期五現(xiàn)在是99頁\一共有134頁\編輯于星期五分析用符號(hào)：tseek=最長(zhǎng)尋找時(shí)間tlatency=最長(zhǎng)等待時(shí)間trw=讀寫一個(gè)IO塊（250個(gè)記錄）所需時(shí)間tIO=tseek+tlatency+trwtIS=內(nèi)排序750個(gè)記錄所需時(shí)間ntm=將n個(gè)記錄從輸入緩沖區(qū)歸并到輸出緩沖區(qū)所需時(shí)間現(xiàn)在是100頁\一共有134頁\編輯于星期五例7.11中排序4500個(gè)記錄的操作時(shí)間：現(xiàn)在是101頁\一共有134頁\編輯于星期五由于tIO>>tIS，tIO>>tm，影響計(jì)算時(shí)間的主要因素是輸入輸出操作的次數(shù)，而后者又主要依賴于對(duì)數(shù)據(jù)掃描的遍數(shù)。例7.11中，生成初始?xì)w并段需要1遍數(shù)據(jù)掃描，歸并需要遍數(shù)據(jù)掃描。一遍掃描需要輸入輸出218個(gè)IO塊，總的輸入輸出時(shí)間是(+1)218tIO=132tIO。歸并時(shí)間是4500tm=12000tm?，F(xiàn)在是102頁\一共有134頁\編輯于星期五顯然，k路歸并（k>>2）可以減少數(shù)據(jù)掃描遍數(shù)。例如，如果在上例中采用6-路歸并，則只需對(duì)數(shù)據(jù)掃描一遍即可完成排序。此外，初始?xì)w并段應(yīng)盡可能長(zhǎng)，從而減少初始?xì)w并段個(gè)數(shù)。在內(nèi)存容量給定的情況下，可以利用動(dòng)態(tài)流動(dòng)的思想，生成平均長(zhǎng)度幾乎是通常方法所得的兩倍的歸并段。但這些歸并段長(zhǎng)短不一，對(duì)它們歸并的次序也會(huì)影響計(jì)算時(shí)間。下面將分別討論這些問題。現(xiàn)在是103頁\一共有134頁\編輯于星期五7.9.2k路歸并

按2-路歸并，給定m個(gè)歸并段，相應(yīng)的歸并樹有l(wèi)og2m+1層，需要對(duì)數(shù)據(jù)掃描log2m遍。采用k路歸并可減少數(shù)據(jù)掃描遍數(shù)。如下圖對(duì)16個(gè)歸并段進(jìn)行4-路歸并只需掃描數(shù)據(jù)2遍：現(xiàn)在是104頁\一共有134頁\編輯于星期五一般地，采用k路歸并需要對(duì)數(shù)據(jù)掃描logkm遍。因此，當(dāng)k>>2時(shí)，采用k路歸并可有效減少輸入輸出時(shí)間。但k路歸并要求從k個(gè)歸并段的前端記錄中選擇關(guān)鍵字最小的輸出?？梢圆捎镁哂衚個(gè)葉結(jié)點(diǎn)的敗者樹來選擇關(guān)鍵字最小的記錄。從敗者樹中每選一個(gè)最小記錄并重新調(diào)整需要O(log2k)時(shí)間，所以對(duì)n個(gè)記錄歸并一遍需要的時(shí)間是O(nlog2k)。歸并logkm遍的CPU處理時(shí)間是O(nlog2klogkm)=O(nlog2m)，即與k無關(guān)。現(xiàn)在是105頁\一共有134頁\編輯于星期五還應(yīng)該看到，當(dāng)k超過一定范圍時(shí)，輸入輸出時(shí)間并不隨著k的增大而減少。因?yàn)椋簁路歸并所需的緩沖區(qū)個(gè)數(shù)隨著k的增大而增加；在內(nèi)存容量給定情況下，緩沖區(qū)容量隨著k的增大而減??；這又導(dǎo)致IO塊的有效容量減小，從而使一遍數(shù)據(jù)掃描需要更多的IO塊操作。因此，當(dāng)k超過一定值時(shí)，輸入輸出時(shí)間反而會(huì)隨著k的增大而增加。k值的最佳選擇與磁盤參數(shù)和可用于緩沖區(qū)的內(nèi)存容量有關(guān)?，F(xiàn)在是106頁\一共有134頁\編輯于星期五7.9.3生成初始?xì)w并段

用傳統(tǒng)的內(nèi)排序方法生成初始?xì)w并段，需要將內(nèi)存容納的所有記錄都排序好后再全部輸出到磁盤。從在排序過程中沒有內(nèi)外存數(shù)據(jù)交換的意義上看，這屬于靜態(tài)方法，由此生成的歸并段最多與內(nèi)存容納的記錄數(shù)同樣大。如果采用動(dòng)態(tài)流動(dòng)的方法，即在生成歸并段的過程中不斷將記錄寫到磁盤，同時(shí)從磁盤讀入新的記錄到內(nèi)存，則可能生成比內(nèi)存容量大的歸并段?，F(xiàn)在是107頁\一共有134頁\編輯于星期五設(shè)內(nèi)存可容納k個(gè)記錄，用r[0],r[1],…,r[k–1]表示，記錄的輸入和輸出通過IO緩沖實(shí)現(xiàn)。輸入k個(gè)記錄后，這些記錄都屬于當(dāng)前歸并段。從屬于當(dāng)前歸并段的內(nèi)存記錄中選關(guān)鍵字最小的記錄r[q]（0≤q<k）輸出到當(dāng)前歸并段。從輸入表讀入下一個(gè)記錄到r[q]，如果此記錄的關(guān)鍵字不小于當(dāng)前歸并段的最后一個(gè)記錄的關(guān)鍵字，則該記錄也屬于當(dāng)前歸并段，否則屬于下一個(gè)將生成的歸并段?，F(xiàn)在是108頁\一共有134頁\編輯于星期五將內(nèi)存記錄所屬的歸并段號(hào)作為第一子關(guān)鍵字，記錄原來的關(guān)鍵字作為第二子關(guān)鍵字，下一個(gè)要輸出的記錄是k個(gè)記錄中關(guān)鍵字最小的。

敗者樹是組織這些記錄的有效結(jié)構(gòu)：每個(gè)非葉結(jié)點(diǎn)i有一個(gè)字段l[i]（1≤i<k），表示在結(jié)點(diǎn)i比賽的敗者。rn[i]表示r[i]所屬的歸并段號(hào)（0≤i<k）。l[0]和q都存放整個(gè)比賽的勝者記錄下標(biāo)。rc存放當(dāng)前歸并段號(hào)。rq存放r[q]所屬的歸并段號(hào)。現(xiàn)在是109頁\一共有134頁\編輯于星期五rmax存放將生成的實(shí)際歸并段總數(shù)。LastKey存放當(dāng)前最后一個(gè)輸出記錄的關(guān)鍵字值。當(dāng)輸入記錄表已讀空時(shí)，我們可以構(gòu)造歸并段號(hào)為rmax+1的虛擬記錄，以將敗者樹中的實(shí)際記錄“頂”出。現(xiàn)在是110頁\一共有134頁\編輯于星期五函數(shù)runs實(shí)現(xiàn)了上述采用敗者樹動(dòng)態(tài)流動(dòng)生成初始?xì)w并段的方法：1template<classKeyType>2voidruns(constintk){3Element<KeyType>*r=newElement[k];4int*rn=newint[k];int*l=newint[k];5for(inti=0;i<k;i++){ //輸入記錄6ReadRecord(r[i]);rn[i]=1;7}8InitializeLoserTree(r,l,rn,k); //初始化敗者樹，可用類 //似第4.6.2小節(jié)的方法9intq=l[0]; //整個(gè)比賽的勝者10intrq=1;intrc=1;intrmax=1;KeyTypeLastKey;現(xiàn)在是111頁\一共有134頁\編輯于星期五11while(1){ //輸出歸并段12if(rq!=rc){ //當(dāng)前段結(jié)束13輸出歸并段結(jié)束標(biāo)記;14if(rq>rmax)break;//遇到虛擬記錄，說明實(shí)際 //記錄已輸出完，跳出循環(huán)15elserc=rq;16}17WriteRecord(r[q]);LastKey=r[q].key;18//輸入新記錄19if(輸入結(jié)束)rn[q]=rmax+1;//生成虛擬記錄，以把實(shí) //際記錄“頂”出敗者樹20else{ReadRecord(r[q]);22 if(r[q].key<LastKey)rn[q]=rmax=rq+1;

//新記錄 //屬于下一個(gè)歸并段現(xiàn)在是112頁\一共有134頁\編輯于星期五23 elsern[q]=rc; //新記錄仍然屬于當(dāng)前歸并段

}25rq=rn[q];26//重新調(diào)整敗者樹27for(intt=(k+q)/2;t;t/=2) //t初始化為r[q]的父結(jié)點(diǎn)28if((rn[l[t]]<rq)||(rn[l[t]]==rq&&r[l[t]].ke