數(shù)據(jù)結構演示文稿

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

在數(shù)據(jù)結構中，數(shù)據(jù)元素之間的次序是一種重要的關系。

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

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

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

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

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

{returnkey;};//取記錄的關鍵字值

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

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

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

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個記錄可以通過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對i=j–1=0,1,…,n–2調用insert，其最壞情況時間復雜性是 O()=O(n2)插入排序的實際時間與輸入表的相對無序狀態(tài)有關。記錄Ri是左出序的當且僅當Ki<?，F(xiàn)在是9頁\一共有134頁\編輯于星期五插入步驟中的循環(huán)只對左出序記錄迭代。設k是左出序記錄個數(shù)，則插入排序的時間是O((k+1)n)。當k=0，插入排序的時間為O(n)。這說明，當輸入表中左出序記錄很少時，插入排序的實際性能十分理想?，F(xiàn)在是10頁\一共有134頁\編輯于星期五例7.1設n=5，輸入關鍵字為5,4,3,2,1，則每次插入后表中記錄的排列如下：這時插入排序的性能達到最壞情況。

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

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

希爾排序又稱為減少增量排序。以插入排序為基礎，并利用插入排序在最好情況下的性能，改善整個排序的性能。觀察輸入序列8,7,6,5,1,2,3,4，其中左出序記錄有7個。在插入排序中，首次交換8和7，只能減少1個左出序記錄。如果首次交換8和1，則可減少2個左出序記錄?，F(xiàn)在是14頁\一共有134頁\編輯于星期五根據(jù)以上觀察，可以跨越式地交換記錄：將整個記錄表劃分為若干個子表，其相鄰記錄相隔incr個位置，incr稱為增量。利用插入排序對每個子表排序，以快速減少整個表中的左出序記錄。每完成一次上述過程，增量減少，繼續(xù)利用插入排序對按新增量劃分的每個子表排序。最后一次增量必須為1，這等同于普通的插入排序，但由于前面的預處理，整個記錄表已基本有序，此次插入排序有望快速完成?，F(xiàn)在是15頁\一共有134頁\編輯于星期五例7.3設n=8，輸入序列為8,7,6,5,1,2,3,4，取incr=4,2,1。處理過程如下所示：現(xiàn)在是16頁\一共有134頁\編輯于星期五增量的一個較有效的選擇是從incr=n/3+1開始，按incr=incr/3+1減少增量。由于跨越式交換，希爾排序是不穩(wěn)定的。為了反映增量，對InsertionSort及其調用的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表示子表開始下標

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

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

template<classKeyType>voidShellSort(Element<KeyType>

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

//排序各子表

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

現(xiàn)在是19頁\一共有134頁\編輯于星期五大規(guī)模實驗研究表明：當記錄個數(shù)n很大時，希爾排序對記錄的移動次數(shù)在n1.25到1.6n1.25的范圍之內。這比插入排序有實質性的改進?，F(xiàn)在是20頁\一共有134頁\編輯于星期五7.4快速排序

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

劃分記錄表：從左到右掃描，找到關鍵字大于等于Kleft的記錄Ri；從右到左掃描，找到關鍵字小于等于Kleft的記錄Rj；交換Ri和Rj；繼續(xù)上述過程，直到i，j錯位。現(xiàn)在是23頁\一共有134頁\編輯于星期五算法QuickSort給出了實現(xiàn)細節(jié)：template<classKeyType>voidQuickSort(Element<KeyType>*list,constintleft,constintright){//排序list[left],…,list[right]，任選list[left]為基準記 //錄，假設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]。調用QuickSort(list,0,n–1)可對表list的第0到第n–1個記錄排序。為了簡化邊界判斷，假設記錄list[n]的關鍵字不小于其余關鍵字。現(xiàn)在是25頁\一共有134頁\編輯于星期五

例7.4設輸入表記錄的關鍵字為(26,5,37,1,61,11,59,15,48,19)，每次調用QuickSort時記錄表的狀態(tài)如下：現(xiàn)在是26頁\一共有134頁\編輯于星期五分析：用于劃分記錄表的時間是O(n)，設下面的c都是常數(shù)。（1）用Tworst(n)表示快速排序的最壞時間復雜性。在最壞情況下，兩個子表的長度分別為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)表示快速排序的最佳時間復雜性。在最佳情況下，兩個子表的長度相同，每個子表的長度最多是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，快速排序的平均時間復雜性也是O(nlogn)。而且，實驗結果表明，快速排序的平均性能最好。

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

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

Tavg(n)≤cn+

=cn+，n≥2 (7.1)設Tavg(0)≤b和Tavg(1)≤b，b為常數(shù)，k=2(b+c)。對n應用歸納法可證，Tavg(n)≤knlogen（n≥2）?，F(xiàn)在是30頁\一共有134頁\編輯于星期五當n=2，由(7.1)式可得：Tavg(2)≤2c+2b≤2kloge2。假設對于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頁\編輯于星期五當m≥2，cm+≤0，所以Tavg(m)≤kmlogem現(xiàn)在是33頁\一共有134頁\編輯于星期五

對基本快速排序算法的改進：基準記錄的選擇：選當前記錄表的第一、中間和最后一個記錄中關鍵字為中間值的記錄。用排序小記錄表較快的方法如插入排序代替快速排序。當需要排序的記錄表小于一定長度時，快速排序已使整個表接近于排好序，這時對整個記錄表調用一次插入排序可使所有記錄就序?，F(xiàn)在是34頁\一共有134頁\編輯于星期五快速排序的最大遞歸深度是n。遞歸排序兩個子表中較小的，再用循環(huán)代替第二個遞歸，可使遞歸深度最多是O(logn)，如函數(shù)ImpQuickSort所示：template<classKeyType>voidImpQuickSort(Element<KeyType>*list,constintleft,constintright){//排序list[left],…,list[right]，任選list[left]為//基準記錄，設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頁\編輯于星期五設S(n)為ImpQuickSort所需的?？臻g，每層遞歸調用需要?？臻g為c，則S(n)≤c+S(n/2)≤2c+S(n/4)…≤clog2n+S(1)=O(logn)。不難看出，快速排序是不穩(wěn)定排序。現(xiàn)在是37頁\一共有134頁\編輯于星期五7.5歸并排序

7.5.1迭代歸并排序歸并排序的基礎是歸并，即將兩個已排序的表歸并為一個已排序的表。在迭代歸并排序中，需要歸并的兩個表：(initListl,…,initListm)(initListm+1,…,initListn)生成的結果表是(mergedListl,…,mergedListn)。現(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];}

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

迭代歸并排序的基本思想：將有n個記錄的輸入表解釋為n個已排序表，每個表的長度為1。成對歸并這些表，得到n/2個已排序表，每個表的長度為2（如果n是奇數(shù)，則最后一個表的長度為1）。再歸并這n/2個表，如此繼續(xù)直到只剩下一個已排序的表?，F(xiàn)在是41頁\一共有134頁\編輯于星期五例7.5對輸入表(26,5,77,61,11,59,15,48,19)，的每一遍掃描中歸并子表的過程：現(xiàn)在是42頁\一共有134頁\編輯于星期五可見，需要對輸入表進行多次歸并掃描。設掃描時輸入表中已排序子表的長度為len（最后一個子表的長度可能小于len），則經過一次歸并掃描后已排序子表的長度變?yōu)?len，如下所示：現(xiàn)在是43頁\一共有134頁\編輯于星期五用i作為掃描指針，指向需歸并的兩個子表的前一個的第一記錄，并隨著歸并的完成向右移動。如果i≤n–2len，則至少還有兩個長度都是len的子表需要歸并，否則需要作特殊邊界處理?，F(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) //歸并最后兩個長短不一的子表merge(initList,resultList,i,i+len–1,n–1);

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

Element<KeyType>*tempList=newElement<KeyType>

[n];

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

}

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

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

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

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

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

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

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

intiResult,iStart,i1,i2;

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

}現(xiàn)在是52頁\一共有134頁\編輯于星期五else{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實現(xiàn)遞歸歸并排序，并返回已排好序鏈表的首記錄指針：template<classKeyType>intrMergeSort(Element<KeyType>*list,constintleft,constintright){ //將list[left],…,list[right]按key排序。返回已 //排序鏈表的首記錄下標。

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

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

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

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

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

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

for(inti=n/2;i>=1;i--) //將list轉化為最大堆adjust(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對(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頁\編輯于星期五

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

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

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

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

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

intf[radix],e[radix];//radix個隊列的首、尾指針

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

list[n–1].link=-1;intcurrent=0; //鏈接成一個以current開 //頭的鏈表，用-1表示空指針現(xiàn)在是71頁\一共有134頁\編輯于星期五for(i=d–1;i>=0;i--){ //對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++); //找到第一個非空隊列current=f[j];intlast=e[j];

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

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

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

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

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

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

//找到應放到位置i的記錄。由于位置0,1,…,i-1的記錄已//就位，該記錄下標一定≥i

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

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

if(first!=i){ //交換list[i]和list[first]，并將list[i].link //設置為原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對(26,5,77,1,61,11,59,15,48,19)進行鏈表排序后，所得鏈表如下所示：現(xiàn)在是81頁\一共有134頁\編輯于星期五list的for循環(huán)每次迭代后記錄表的狀態(tài)如下，變化用粗體字表示，虛擬結點的link字段用帶下劃線的字體表示：現(xiàn)在是82頁\一共有134頁\編輯于星期五現(xiàn)在是83頁\一共有134頁\編輯于星期五現(xiàn)在是84頁\一共有134頁\編輯于星期五現(xiàn)在是85頁\一共有134頁\編輯于星期五現(xiàn)在是86頁\一共有134頁\編輯于星期五

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

函數(shù)table首先沿著包含R0的環(huán)路將記錄移到其正確位置。接著，如果包含R1的環(huán)路未被移動過，則沿著該環(huán)路將記錄移到其正確位置。由此繼續(xù)移動包含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]，使其對應序列l(wèi)ist[t[0]],…,//list[t[n-1]],n≥1

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

if(t[i]!=i){ //存在一個開始于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中的記錄應該移到位置jt[j]=j;}}現(xiàn)在是91頁\一共有134頁\編輯于星期五例7.10一個根據(jù)映射表t對記錄順序化的例子：現(xiàn)在是92頁\一共有134頁\編輯于星期五

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

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

等待時間：本磁道中所需塊旋轉到讀寫頭下所用時間。

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

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

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

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

敗者樹是組織這些記錄的有效結構：每個非葉結點i有一個字段l[i]（1≤i<k），表示在結點i比賽的敗者。rn[i]表示r[i]所屬的歸并段號（0≤i<k）。l[0]和q都存放整個比賽的勝者記錄下標。rc存放當前歸并段號。rq存放r[q]所屬的歸并段號?，F(xiàn)在是109頁\一共有134頁\編輯于星期五rmax存放將生成的實際歸并段總數(shù)。LastKey存放當前最后一個輸出記錄的關鍵字值。當輸入記錄表已讀空時，我們可以構造歸并段號為rmax+1的虛擬記錄，以將敗者樹中的實際記錄“頂”出?，F(xiàn)在是110頁\一共有134頁\編輯于星期五函數(shù)runs實現(xiàn)了上述采用敗者樹動態(tài)流動生成初始歸并段的方法：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]; //整個比賽的勝者10intrq=1;intrc=1;intrmax=1;KeyTypeLastKey;現(xiàn)在是111頁\一共有134頁\編輯于星期五11while(1){ //輸出歸并段12if(rq!=rc){ //當前段結束13輸出歸并段結束標記;14if(rq>rmax)break;//遇到虛擬記錄，說明實際 //記錄已輸出完，跳出循環(huán)15elserc=rq;16}17WriteRecord(r[q]);LastKey=r[q].key;18//輸入新記錄19if(輸入結束)rn[q]=rmax+1;//生成虛擬記錄，以把實 //際記錄“頂”出敗者樹20else{ReadRecord(r[q]);22 if(r[q].key<LastKey)rn[q]=rmax=rq+1;

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

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