數(shù)據(jù)結(jié)構 第9章 排序

數(shù)據(jù)結(jié)構C++實現(xiàn)

所謂排序(Sorting)就是對數(shù)據(jù)元素集合建立某種有序排列的過程。排序在計算機軟件系統(tǒng)設計中占有相當重要的地位，特別是在事務處理系統(tǒng)中，需要經(jīng)常對有關的數(shù)據(jù)排序，以便提高檢索等操作的效率。本章將介紹一些常用的排序算法，它們有：交換排序、插入排序、選擇排序、歸并排序和基數(shù)排序，并對有關的算法進行性能分析和對比?；A知識

1．排序：設含有n個數(shù)據(jù)元素的數(shù)據(jù)表為：{R[0]、R[1]、…、R[n-1]}，其相應的關鍵字序列為：{K[0]、K[1]、…、K[n—1]}。所謂排序，是確定0、1、…、n-1的一種排列p0、p1、…、pn-1，使各關鍵字滿足如下的遞增(或遞減)關系：K[p0]≤K[p1]≤…≤K[pn—1]或K[p0]≥K[p1]≥…≥K[pn—1]2．排序的穩(wěn)定性：如果在排序表中任意兩個數(shù)據(jù)元素R[i]和R[j]（i≠j），它們的關鍵字K[i]＝K[j]，且在排序之前，數(shù)據(jù)元素R[i]排在R[j]的前面，如果在排序之后，數(shù)據(jù)元素R[i]仍在數(shù)據(jù)元素R[j]的前面，即不改變關鍵字相同的數(shù)據(jù)元素在排序前、后的相對位置，則稱這種排序方法是穩(wěn)定的，否則稱這種排序方法是不穩(wěn)定的。

3．內(nèi)部排序與外部排序：根據(jù)在排序過程中數(shù)據(jù)元素是否全部在內(nèi)存中進行，排序可分為兩大類：內(nèi)排序和外排序。內(nèi)排序是指在排序過程中數(shù)據(jù)元素全部存放在內(nèi)存進行的排序；外排序是指由于數(shù)據(jù)元素太多，在排序期間全部數(shù)據(jù)元素不能同時存放在內(nèi)存中，必須在排序過程中，不斷地在內(nèi)存和外存之間交換數(shù)據(jù)元素的排序。

4．排序的效率：排序是經(jīng)常使用的一種運算，因此，排序效率的高低普為人們注意，排序算法的效率可以從時間復雜度和空間復雜度兩個方面來分析。排序算法的時間復雜度可用排序過程中的數(shù)據(jù)元素之關鍵字的比較次數(shù)與數(shù)據(jù)元素的移動次數(shù)來衡量。在本章下面各節(jié)討論算法的時間復雜度時一般都按平均時間復雜度進行估算；對于那些受排序表中數(shù)據(jù)元素的初始排列及數(shù)據(jù)元素數(shù)目影響較大的算法，按最好情況和最壞情況進行分別估算。而算法的空間復雜度為算法執(zhí)行時所需的附加存儲空間。下面給出用順序表表示的排序表的類定義:const

intMaxSize=100;template<classType>classsortlisttemplate<classType>classelement{//數(shù)據(jù)元素的類定義friend

classsortlist<Type>;private:Typekey;//數(shù)據(jù)元素的關鍵字

other;//其它信息public:element();//構造函數(shù)

TypegetKey(){returnkey;}//取數(shù)據(jù)元素關鍵字

voidsetKey(constTypek){key=k;}//修改數(shù)據(jù)元素關鍵字

element<Type>&operator=(element<Type>&x){this=x;}

intoperator==(Type&k){return!(key<k||k<key);}

intoperator!=(Type&k){return(key<k||k<key);}

intoperator<=(Type&k){return!(key>k);}

intoperator>=(Type&k){return!(key<k);}

intoperator<(Type&k){return(key<k);}

intoperator>(Type&k){return(key>k);}}template<classType>classsortlist{protected:element<Type>*Arr;//存儲數(shù)據(jù)元素的向量（排序表）

intCurrentSize;//數(shù)據(jù)表中數(shù)據(jù)元素的個數(shù)public:sortlist():CurrentSize(0){Arr=newelement<Type>[MaxSize];}//構造函數(shù)

sortlist(){deleteArr[]};//析構函數(shù)

voidswap(element<Type>&x,element<Type>&y){element<Type>temp=x;x=y;y=temp;}//數(shù)據(jù)元素x和y交換位置}下面給出用鏈表表示的排序表的類定義:const

intMaxSize=100;template<classType>classsortlinklisttemplate<classType>classnode{//數(shù)據(jù)元素的類定義friend

classsortlinklist<Type>;private:Typekey;//數(shù)據(jù)元素的關鍵字

intnext;//后繼指針

other;//其它信息public:node();//構造函數(shù)

TypegetKey(){returnkey;}//取數(shù)據(jù)元素關鍵字

voidsetKey(constTypek){key=k;}//修改數(shù)據(jù)元素關鍵字

intgetLink(){returnnext;}//取結(jié)點的后繼指針

voidsetKey(const

intp){next=p;}//修改結(jié)點的后繼指針

intoperator==(Type&k){return!(key<k||k<key);}

intoperator!=(Type&k){return(key<k||k<key);}

intoperator<=(Type&k){return!(key>k);}

intoperator>=(Type&k){return!(key<k);}

intoperator<(Type&k){return(key<k);}

intoperator>(Type&k){return(key>k);}}template<classType>classsortlinklist{protected:node<Type>*Arr;//存儲排序表結(jié)點的向量（靜態(tài)鏈表）

intCurrentSize;//排序表中的結(jié)點個數(shù)public:sortlinklist():CurrentSize(0){Arr=newnode<Type>[MaxSize];}//構造函數(shù)

sortlinklist(){deleteArr[]};//析構函數(shù)}

交換排序

交換排序的基本思想是對排序表中所有兩兩相鄰的數(shù)據(jù)元素的關鍵字進行比較，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則兩者交換位置，直到所有數(shù)據(jù)元素都排好序為止。在本節(jié)中，將介紹兩種交換排序的方法：冒泡排序和快速排序。冒泡排序

冒泡排序(BubbleSort)的算法思想是：設排序表中有n個數(shù)據(jù)元素，首先對排序表中第一、二個數(shù)據(jù)元素的關鍵字Arr[0].Key和Arr[1].Key進行比較，如果Arr[0].Key>Arr[1].Key，則交換Arr[0]和Arr[1];然后對第二、三個數(shù)據(jù)元素做同樣處理；重復此過程直到處理完最后兩個相鄰的數(shù)據(jù)元素。冒泡排序示例：冒泡排序的算法:template<classType>voidBubbleSort(sortlist<Type>&table){

inti=1;intfinish=0;

while(i<table.CurrentSize&&!finish){finish=1;//交換標志置為1,假定未交換

for(intj=0;j<.CurrentSize-i;j++)

if(table.Arr[j].GetKey()>table.Arr[j+1].GetKay()){Swap(table.Arr[j],table.Arr[j+1]);finish=0;}//交換標志置為0,表示有交換

i++;}}

在最壞情形下總的關鍵字比較次數(shù)和數(shù)據(jù)元素移動次數(shù)分別為：

因此在最壞情況下，冒泡排序的時間復雜度為O(n2）。冒泡排序需要一個附加存儲空間以實現(xiàn)數(shù)據(jù)元素的交換。顯然，冒泡排序算法是一種穩(wěn)定的排序方法。快速排序

快速排序（QuickSort）又被稱做分區(qū)交換排序，這是一種平均性能非常好的排序方法，其算法基本思想是：任取排序表中的某個數(shù)據(jù)元素(例如取第一個數(shù)據(jù)元素)作為基準，按照該數(shù)據(jù)元素的關鍵字大小，將整個排序表劃分為左右兩個子表：左側(cè)子表中所有數(shù)據(jù)元素的關鍵字都小于或等于基準數(shù)據(jù)元素的關鍵字，右側(cè)子表中所有數(shù)據(jù)元素的關鍵字都大于基準數(shù)據(jù)元素的關鍵字，基準數(shù)據(jù)元素則排在這兩個子表中間(這也是該數(shù)據(jù)元素最終應安放的位置)，然后分別對這兩個子表重復施行上述方法的快速排序，直到所有的子表長度為1，則排序結(jié)束。

快速排序過程示例：快速排序算法的描述如下：template<classType>voidQuickSort(sortlist<Type>&table,intlow,inthigh){//在待排序區(qū)間lowhigh上，遞歸地進行快速排序

inti=low,j=high;element<Type>temp=table.Vector[low];

while(i<j){

while(i<j&&temp.GetKey()<=table.Arr[j].GetKey())j--;

if(i<j){Table.Arr[i]=Table.Arr[j];i++;}

while(i<j&&temp.GetKey()>table.Arr[i].GetKey())i++;

if(i<j){Table.Arr[j]=Table.Arr[i];j--;}}Table.Arr[i]=temp//將基準元素就位

QuickSort(list,low,i-1);

//在左子區(qū)間遞歸進行快速排序

QuickSort(list,i+1,high);

//在右子區(qū)間遞歸進行快速排序}在n個元素的序列中，對一個數(shù)據(jù)元素定位所需時間為0(n)。若設T(n)是對n個元素的序列進行排序所需的時間，而且每次對一個數(shù)據(jù)元素正確定位后，正好把排序表劃分為長度相等的兩個子表，此時，總的計算時間為：T(n)≤cn+2T(n/2)其中，c是一個常數(shù)≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)≤2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)…≤cnlog2n+nT(1)=O(nlog2n)

在一般情況下，設選為基準的數(shù)據(jù)元素是關鍵字第k小的，且等概率地取1、2、…、n，則有：

就是快速排序的平均計算時間，可以用歸納法證明，這個時間數(shù)量級也為0(nlog2n)。由于快速排序是遞歸的，就需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)，其最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為log2(n+1)，因此，要求的存儲開銷為0(log2n)。快速排序是一種不穩(wěn)定的排序方法。插入排序

插入排序的基本思想是：每一次設法把一個數(shù)據(jù)元素插入到已經(jīng)排序的部分序列的合適位置，使得插入后的序列仍然是有序的。開始時建立一個初始的有序序列，它只包含一個數(shù)據(jù)元素。然后，從這個的初始序列開始不斷進行插入數(shù)據(jù)元素，直到最后一個數(shù)據(jù)元素插入到有序序列后，整個排序工作就完成了。直接插入排序

直接插入排序（InsertSort）的算法基本思想是：開始時把第一個數(shù)據(jù)元素作為初始的有序序列，然后依次從第二個數(shù)據(jù)元素開始把數(shù)據(jù)元素按關鍵字大小插入到已排序的部分排序表的適當位置。當插入第i(1<i≤n)個數(shù)據(jù)元素時，前面的i-1個數(shù)據(jù)元素已經(jīng)排好序，這時，用第i個數(shù)據(jù)元素的關鍵字與前面的i-1個數(shù)據(jù)元素的關鍵字順序進行比較，找到插入位置后就將第i個數(shù)據(jù)元素插入，原來位置及其以后的數(shù)據(jù)元素都向后順移一個位置。如此進行n-1次插入就完成了排序。

順序表上的直接插入排序

在順序表上進行直接插入排序過程：直接插入排序算法的C++描述：template<classType>voidInsertionSort(sortlist<Type>&table){element<Type>temp;

intj;

for(inti=1;i<table.CurrentSize;i++){temp=table.Arr[i];j=i;

while(j>0&&temp.getKey()<table.Arr[j-1].getKey()){table.Arr[j]=table.Arr[j-1];j--;}table.Arr[j]=temp;}}

在最好情況下，即在排序前數(shù)據(jù)元素已經(jīng)按關鍵字大小從小到大排好序了，每趟只需與前面的有序數(shù)據(jù)元素序列的最后一個數(shù)據(jù)元素的關鍵字比較1次，移動2次數(shù)據(jù)元素。所以，總的關鍵字比較次數(shù)為n-1，數(shù)據(jù)移動次數(shù)為2(n-1)，因此最好情況下的時間復雜度為O(n）；在最壞情況下，即第i趟插入時，第i+1個數(shù)據(jù)元素必須與前面i個數(shù)據(jù)元素都做關鍵字的比較，并且每做1次比較就要做1次數(shù)據(jù)元素移動，則總的關鍵字比較次數(shù)和數(shù)據(jù)移動次數(shù)分別為：

因此最壞情況下的時間復雜度為O(n2）。若排序表中出現(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均，可得在平均情況下的關鍵字比較次數(shù)和數(shù)據(jù)元素移動次數(shù)約為n2／4，因此，直接插入排序的平均時間復雜度為O(n2)。根據(jù)上述分析可以得知：初始數(shù)據(jù)表越接近有序，直接插入排序的效率越高。這個結(jié)論是后面討論希爾排序的基礎。顯然，在順序表上的直接插入排序是一種穩(wěn)定的排序方法。鏈表上的直接插入排序

右圖給出了在鏈表上實現(xiàn)直接插入排序的示例，例子中用靜態(tài)鏈表存儲排序表，并把Arr[0]作為鏈表的表頭結(jié)點。初始時，排序表中的數(shù)據(jù)元素結(jié)點形成一個單鏈表。在排序開始時，先把表頭結(jié)點Arr[0]的next設為-1，表示有序鏈表為空表，p指向排序表的第一個數(shù)據(jù)元素結(jié)點。在靜態(tài)鏈表上實現(xiàn)直接插入排序的算法：template<classType>intLinkInsertSort(sortlinklist<Type>&table){

intp,q,pre,r;p=table.Arr[0].getLink();//p指向第一個數(shù)據(jù)元素結(jié)點

table.Arr[0].setlink(-1);//形成初始鏈表

while(p!=-1){//當待排序序列中還存在數(shù)據(jù)元素結(jié)點時

q=table.Arr[0].getlink();pre=0;//前驅(qū)指針while(q!=-1){//找插入位置

if(table.Arr[q].getKey()<=table.Arr[p].getKey())pre=q;q=table.Arr[q].getLink();

else

break;}r=table.Arr[p].getLink();table.Arr[p].setlink(q);table.Arr[pre].setlink(p);//在pre與q之間插入p（即Arr[i]）

p=r;//準備插入下一個數(shù)據(jù)元素結(jié)點

}}

使用鏈表插入排序，無需移動數(shù)據(jù)元素的位置，代之以指針的修改共2n次。在插入第i個數(shù)據(jù)元素結(jié)點時，關鍵字比較次數(shù)最多為i次，關鍵字比較次數(shù)最少為1。因此，總的關鍵字比較次數(shù)最少為n-1，最多為：為了實現(xiàn)鏈表插入，在每個數(shù)據(jù)元素結(jié)點中增加了一個鏈域next，并使用了Arr[0]作為鏈表的表頭結(jié)點。所以，總共用了n個附加指針域和一個附加數(shù)據(jù)元素結(jié)點。鏈表插入排序方法是穩(wěn)定的。折半插入排序

折半插入排序算法與順序表上進行直接插入排序的算法類似，只是在插入Arr[i]時，利用折半查找方法尋找Arr[i]的插入位置。折半插入排序的算法可描述為：template<classType>voidBinaryInsertSort(sortlist<Type>&table){element<Type>temp；

intleft,right;

for(inti=1;i<table.CurrentSize;i++){left=0;right=i-1;temp=table.Arr[i];

while(left<=right){

intmid=(left+right)/2;

if(temp.getKey()<table.Arr[mid].getKey())right=mid-1;

elseleft=mid+1;}

for(intk=i-1;k>=left;k--)table.Arr[k+1]=table.Arr[k];table.Arr[left]=temp;}}

就平均性能而言，因為折半查找優(yōu)于順序查找，所以折半插入排序也優(yōu)于直接插入排序。折半插入排序的算法只能在順序表存儲結(jié)構下實現(xiàn)。

折半插入排序是一個穩(wěn)定的排序方法。希爾排序

希爾排序(ShellSort)又稱為縮小增量排序，它的算法基本思想是：設排序表中有n個數(shù)據(jù)元素，首先取一個整數(shù)d＜n作為間隔，將全部數(shù)據(jù)元素分為d個子表，所有相距為d的數(shù)據(jù)元素放在同一個子表中，在每一個子表中分別進行直接插入排序，然后縮小間隔d（例如取d=d/2），重復上述的子表劃分和排序工作。如此循環(huán)，直到最后d＝1，將所有數(shù)據(jù)元素放在同一個序列中進行直接插入排序。

右圖給出了有6個數(shù)據(jù)元素的排序表進行希爾排序的過程。第1趟取間隔d＝3，第2趟將間隔縮小為d＝d/2＝2，第3趟把間隔縮小為d＝d/2＝1，對整個序列進行直接插入排序，因為此時整個排序表已經(jīng)達到基本有序，所以排序的效率比較高。希爾排序算法的C++描述：template<classType>voidShellsort(sortlist<Type>&table){element<Type>temp

intd=table.CurrentSize/2;//d是子表間隔

while(d){//循環(huán)直到d為零

for(inti=d;i<table.CurrentSize;i++){temp=table.Arr[i];

for(j=i;j>=d;j-=d)

if(temp.GetKey()<table.Arr[j-d].GetKey())table.Arr[j]=table.Arr[j-d]

else

break;table.Arr[j]=temp;}d=(int)(d/2);//修改子表間隔}}

利用大量的實驗統(tǒng)計資料得出，當n很大時，關鍵字平均比較次數(shù)相數(shù)據(jù)元素平均移動次數(shù)大約在n1.25到1.6n1.25范圍內(nèi)，這是在利用直接插入排序作為子表排序方法的情況下得到的。在希爾排序中，由于數(shù)據(jù)元素的跳躍式移動，使得希爾排序不是穩(wěn)定的排序方法。選擇排序

選擇排序的基本思想是：第一趟在有n個數(shù)據(jù)元素的排序表中選出關鍵字最小的數(shù)據(jù)元素，然后在剩下n-1個數(shù)據(jù)元素中再選取關鍵字最?。ㄕ麄€數(shù)據(jù)表中次小）的數(shù)據(jù)元素，依次重復，每一趟(例如第i趟，i＝1，…，n-1)總是在當前剩下的n-i+1個待排序數(shù)據(jù)元素中選出關鍵字最小的數(shù)據(jù)元素，作為有序數(shù)據(jù)元素序列的第i個數(shù)據(jù)元素。等到第n-1趟選擇結(jié)束，待排序數(shù)據(jù)元素僅剩下1個時就不用再選了，按選出的先后次序所得到的數(shù)據(jù)元素序列即為有序序列，排序即告完成。直接選擇排序

1.順序表上的直接選擇排序在順序表存儲結(jié)構下（設n個數(shù)據(jù)元素存儲在向量Arr[0]Arr[n-1]中），直接選擇排序的算法基本思想是：(1)開始時設i的初始值為0。(2)如果i<n-1，在數(shù)據(jù)元素序列Arr[i]Arr[n-1]中，選出具有最小關鍵字的數(shù)據(jù)元素Arr[k]；否則算法結(jié)束。(3)若Arr[k]不是這組數(shù)據(jù)元素中的第一個數(shù)據(jù)元素（i≠K），則將Arr[k]與Arr[i]這兩數(shù)據(jù)元素的位置對調(diào)；(4)令i=i+1轉(zhuǎn)步驟（2）。在順序表上實現(xiàn)直接選擇排序的示例

5在順序表上直接選擇排序算法的C++描述如下：template<classType>voidSelectSort(sortlist<Type>&table){

intk;

for(inti=0;i<table.CurrentSize-1;i++){k=i;

for(intj=i+1;j<table.CurrentSize;j++)

if(table.Arr[j].getKey()<table.Arr[k].getKey())k=j;

if(k!=i)Swap(table.Arr[i],table.Arr[k]);}}在直接選擇排序中，關鍵字比較次數(shù)與數(shù)據(jù)元素的初始排列無關，總的關鍵字比較次數(shù)為:比較次數(shù)=(n-1)+(n-2)+…+1=n(n-1)/2數(shù)據(jù)元素的移動次數(shù)與排序表中數(shù)據(jù)元素的初始排列有關。當這組數(shù)據(jù)元素的初始狀態(tài)是按其關鍵字從小到大有序的時候，數(shù)據(jù)元素的移動次數(shù)為0，達到最小值；而最壞情況是每一趟選擇后都要進行交換，一趟交換需要移動數(shù)據(jù)元素3次。所以總的數(shù)據(jù)元素移動次數(shù)為3(n-1)?？梢娭苯舆x擇排序總的時間復雜度為O(n2）。由于在直接選擇排序過程中，交換數(shù)據(jù)元素一般不是在相鄰位置的數(shù)據(jù)元素之間進行，因此它不是一種穩(wěn)定的排序方法。2．鏈表上的直接選擇排序

在鏈表存儲結(jié)構下直接選擇排序的算法基本思想是：(1)開始時設h指向排序表的第一個數(shù)據(jù)元素結(jié)點；Arr[0].next設為-1，表示有序鏈表為空表；(2)設置搜索指針p指向h，如果p!=-1，表示排序表中還有數(shù)據(jù)元素沒有被選出，繼續(xù)步驟（3）；否則排序表中所有數(shù)據(jù)元素已經(jīng)都有被選出，并插入到有序鏈表中，所以算法結(jié)束；(3)在排序表中選出具有最大關鍵字的數(shù)據(jù)元素結(jié)點，由q指向，pq指向q的前驅(qū)結(jié)點（如果存在）。(4)將q所指接點]插入到有序鏈表的第一個數(shù)據(jù)元素結(jié)點之前；(5)令p=h轉(zhuǎn)步驟（2），準備下一次選擇。在靜態(tài)鏈表上實現(xiàn)直接選擇排序的示例

在鏈表上進行直接選擇排序算法的C++描述如下：template<classType>voidLinkSelectSort(sorlinktlist<Type>&table){

intp,q,pp,pq,h;h=p=table.Arr[0].getLink();table.Arr[0].setlink(-1);//形成初始有序鏈表

while(p!=-1){q=pq=pp=p;設置初始搜索指針

p=table.Arr[p].getLink();while(p!=-1){

if(table.Arr[p].getKey()>=table.Arr[q].getKey()){q=p;pq=pp;}pp=p;p=table.Arr[p].getLink();}

if(h=q){h=table.Arr[q].getLink();table.Arr[q].setLink(table.Arr[0].getLink());table.Arr[0].setLink(q);}

else

{table.Arr[pq].setLink(table.Arr[q].getLink());table.Arr[q].setLink(table.Arr[0].getLink());table.Arr[0].setLink(q);}p=h;//準備下一次選擇

}}與在順序表上的直接選擇排序一樣。在鏈表上進行直接選擇排序，關鍵字比較次數(shù)與數(shù)據(jù)元素的初始排列無關，總的關鍵字比較次數(shù)為:比較次數(shù)=(n-1)+(n-2)+…+1=n(n-1)/2

在鏈表上進行直接選擇排序不需要進行數(shù)據(jù)元素的移動，每一趟選出數(shù)據(jù)元素后只需將其插入到有序表的第一個數(shù)據(jù)元素之前。可見在鏈表上進行直接選擇排序總的時間復雜度也為O(n2）。鏈表上的直接選擇排序也是一種穩(wěn)定的排序方法。錦標賽排序

錦標賽排序的算法思想與體育比賽類似。首先將n個數(shù)據(jù)元素兩兩分組，分別按關鍵字進行比較，得到n／2個比較的優(yōu)勝者(關鍵字小者)，作為第一步比較的結(jié)果保留下來，然后對這n／2個數(shù)據(jù)元素再兩兩分組，分別按關鍵字進行比較，…，如此重復，直到選出一個關鍵字最小的數(shù)據(jù)元素為止。

錦標賽排序示例：

錦標賽排序構成的樹是完全二叉樹，其高度為Log2n+1，其中n為排序表中數(shù)據(jù)元素個數(shù)。因此，除第一次選出具有最小關鍵字的數(shù)據(jù)元素需要進行n-1次關鍵字比較外，重構優(yōu)勝者樹，選出具有次小、再次小、…關鍵字的數(shù)據(jù)元素所需的關鍵字比較次數(shù)均為0(Log2n)。所以，總的關鍵字比較次數(shù)為0(nLog2n)。數(shù)據(jù)元素的移動次數(shù)與關鍵字的比較次數(shù)相當，所以錦標賽排序總的時間復雜度為0(nlog2n)。錦標賽排序也是一種不穩(wěn)定的排序方法。堆排序

堆排序的算法基本思想是：（1）對排序表中的數(shù)據(jù)元素，利用堆的調(diào)整算法形成初始堆。（2）輸出堆頂元素。（3）對剩余元素重新調(diào)整形成堆。（4）重復執(zhí)行第（2)、(3)步，直到所有數(shù)據(jù)元素被輸出。堆排序的示例

建立最大堆的調(diào)整算法：template<classType>voidMinHeap<Type>::FilterDown(const

intstart,

const

intEndOfHeap){//向下調(diào)整使從start開始到EndOfHeap為止的子表成為最大堆

inti=start,j=2*i+1;//j為i的左孩子

Typetemp=heapArr[i];

while(j<=EndOfHeap){

if(j<EndOfHeap&&table.Arr[j].getkey()<table.Arr[j+1].getkey())j++;//在兩個孩子中選關鍵字較小者

if(temp.getkey()>=table.Arr[j].getkey())

break;

else{table.Arr[i]=table.Arr[j];i=j;j=2*j+1;}}table.Arr[i]=temp;}堆排序算法的C++描述如下：template<classType>void

HeapSort(sortlist<Type>&table){

for(inti=(table.CurrentSize-2)/2;i>=0;i--)FilterDown(i,table.CurrentSize-1);//初始建堆

for(i=table.CurrentSize-1;i>=1;i--){Swap(table.Arr[0],table.Arr[i]);FilterDown(0,i-1);//重建最大堆

}}

堆排序算法的時間復雜性可用關鍵字的比較次數(shù)來測度。若設堆中有n個結(jié)點，且2k-1n2k，則對應的完全二叉樹有k層。在第一個形成初始堆的for循環(huán)中對每一個非葉結(jié)點調(diào)用了一次堆調(diào)整算法FilterDown()，一個數(shù)據(jù)元素每下調(diào)一層需要進行2次關鍵字的比較，最多下調(diào)到最底層，因此該循環(huán)所用的計算時間為：其中，i是層序號，2i-1是第i層的最大結(jié)點數(shù)，(k-i-1)是第i層結(jié)點下調(diào)到最底層（第k層）所需的調(diào)整次數(shù)。

在第二個for循環(huán)中，調(diào)用了n-1次FilterDown()算法，每次調(diào)用總是將位于根上的數(shù)據(jù)元素最多下調(diào)到當前堆的最底層。所以該循環(huán)的計算時間為O(nlog2n)。因此，堆排序的時間復雜性為O(nlog2n)。該算法的空間復雜性為O(1)。堆排序是一種不穩(wěn)定的排序方法。歸并排序

所謂歸并，就是將兩個或兩個以上的有序表合并成一個新的有序表。如下圖所示，有兩個已經(jīng)排好序的有序表A[1]A[n]和B[1]B[m]（在圖中只給出了它們的關鍵字），通過歸并把它們合成一個有序表C[1]C[m+n]。兩路歸并算法的C++描述：template<classType>voidmerge(sortlist<Type>&sourceTable,sortlist<Type>&mergedTable,

const

intleft,const

intmid,const

intright){

inti=left,j=mid+1,k=left;//指針初始化

while(i<=mid&&j<=right)

if(sourceTable.Arr[i].getKey()<=sourceTable.Arr[j].getKey()){mergedTable.Arr[k]=sourceTable.Arr[i];i++;k++;}

else{mergedTable.Arr[k]=sourceTable.Arr[j];j++;k++;}

if(i<=mid)

for(intp=k,q=i;q<=mid;p++,q++)mergedTable.Arr[p]=sourceTable.Arr[q];

else

for(intp=k,q=j;q<=right;p++,q++)mergedTable.Arr[q]=sourceTable.Arr[p];}兩路歸并排序

兩路歸并排序就是利用兩路歸并算法進行排序。其算法基本思想是：假設初始排序表有n個數(shù)據(jù)元素，首先把它看成是長度為1的首尾相接的n個有序子表(以后稱它們?yōu)闅w并項)，先做兩兩歸并，得n/2個長度為2的歸并項(如果n為奇數(shù)，則最后一個歸并項的長度為1)；再做兩兩歸并，……，如此重復，最后得到一個長度為n的有序序列。兩路歸并排序的示例：一趟歸并的算法描述如下：template<classType>voidMergePass(sortlist<Type>&sourceTable,sortlist<Type>&mergedTable,const

intlen){

inti=0;

while(i+2*len<=CurrentSize-1){merge(sourceTable,mergedTable,i,i+len-1,i+2*len-1);i+=2*len;}

if(i+len<=CurrentSize-1)merge(sourceTable,mergedTable,i,i+len-1,CurrentSize-1);

else

for(intj=i;j<=CurrentSize-1;j++)mergedTable.Arr[j]=sorceTable.Arr[j];}兩路歸并排序算法描述如下：template<classType>voidMergeSort(sortlist<Type>&table){sortlist<Type>&tempTable;

intlen=1;

while(len<table.CurrentSize){MergePass(table,tempTable,len);len*=2;MergePass(tempTable,list,len);len*=2;}delete[]tempTable;}

在兩路歸并排序算法中，函數(shù)MergePass()做一趟歸并，要調(diào)用merge()函數(shù)n/(2*len)

O(n/len)次，而每次merge()要執(zhí)行比較次數(shù)不超過2*len-1，為O(len)，函數(shù)MergeSort()調(diào)用MergePass()正好log2n

次，所以兩路歸并排序算法總的時間復雜度為O(nlog2n)。兩路歸并排序占用附加存儲較多，需要另外一個與原待排序數(shù)據(jù)元素數(shù)組同樣大小的輔助數(shù)組，所以其空間復雜度為O(n）。兩路歸并排序是一個穩(wěn)定的排序方法。遞歸的歸并排序

在遞歸的歸并排序方法中，首先要把整個排序表劃分為長度大致相等的左右兩個部分，分別稱之為左子表和右子表，對這兩個子表分別進行歸并排序（遞歸），然后再把已排好序的這兩個子表進行兩路歸并，得到一個有序表。

遞歸的歸并排序示例：

在遞歸的歸并排序過程中，如果使用前面給出的兩路歸并算法，需要進行數(shù)組元素的傳遞，這非常影響歸并的效率。如果排序表采用鏈表的存儲表示，可以得到一種有效的歸并排序算法。在此排序表以靜態(tài)鏈表存儲，設待排序的數(shù)據(jù)元素存放在類型為的靜態(tài)鏈表table中。table.Arr[0]用于表示結(jié)果鏈表的頭結(jié)點。函數(shù)linkListMerge()是將兩個有序的單鏈表歸并成一個有序單鏈表的算法。靜態(tài)鏈表上的遞歸歸并排序示例：在靜態(tài)鏈表上實現(xiàn)兩路歸并的算法描述如下：template<classType>intlinkListMerge(sortlinklist<Type>&table,

const

intp,const

intq){

intk=0,i=p,j=q;//初始化指針,其中k為結(jié)果鏈表的尾結(jié)點指針,i、j為搜索指針

while(i!=-1&&j!=-1)

if(table.Arr[i].getKey()<=table.Arr[j].getKey()){table.Arr[k].setLink(i);k=i;i=table.Arr[i].getLink();}

else{table.Arr[k].setLink(j);k=j;j=table.Arr[j].getLink();}

if(j!=-1)table.Arr[k].setlink(j);

elsetable.Arr[k].setLink(i);

returntable.Arr[0].getLink();}遞歸歸并排序算法：template<classType>intlinkListMergeSort(sortlinklist<Type>&table,

const

intlow,const

inthigh){

if(low>=high)returnlow;

intmid=(low+high)/2;

returnlinkListMerge(table,linkListMergeSort(table,low,mid),linkListMergeSort(table,mid+1,right));}

在靜態(tài)鏈表上實現(xiàn)的遞歸歸并排序算法，通過鏈接指針的修改以實現(xiàn)數(shù)據(jù)元素接點的邏輯有序鏈接，因此不需要數(shù)據(jù)元素移動。計算時間可以用數(shù)據(jù)元素關鍵字的比較次數(shù)來測量。算法的遞歸深度為O(log2n)，所以總的時間復雜度為0(nlog2n)。它也是一種穩(wěn)定的排序方法。

基數(shù)排序

基數(shù)排序又被稱為桶排序。與前面介紹的幾種排序方法相比較，基數(shù)排序和它們有明顯的不同。前面所介紹的排序方法都是建立在對數(shù)據(jù)元素關鍵字進行比較的基礎上，所以可以稱為基于比較的排序；而基數(shù)排序首先將待排序數(shù)據(jù)元素依次“分配”到不同的桶里，然后再把各桶中的數(shù)據(jù)元素“收集”到一起。通過使用對多關鍵字進行排序的這種“分配”和“收集”的方法，基數(shù)排序?qū)崿F(xiàn)了對多關鍵字進行排序。多關鍵字排序

每張撲克牌有兩個“關鍵字”：花色和面值。其大小順序為：花色：＜＜＜面值：2＜3＜……＜K＜A撲克牌的大小先根據(jù)花色比較，花色大的牌比花色小的牌大；花色一樣的牌再根據(jù)面值比較大小。所以，將撲克牌按從小到大的次序排列，可得到以下序列：

2，…，A，2，…，A，2，…，A，2，…，A

這種排序相當于有兩個關鍵字的排序，一般有兩種方法實現(xiàn)。其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值從小到大的次序排序，最后把已排好序的四堆牌按花色從小到大次序疊放在一起就得到排序的結(jié)果。其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后將這十三堆牌按面值從小到大的順序疊放在一起，再把整副牌按順序根據(jù)花色再分成四堆（每一堆牌已按面值從小到大的順序有序），最后將這四堆牌按花色從小到大合在一起就得到排序的結(jié)果。

假定排序表中有n個數(shù)據(jù)元素（Arr[0]、Arr[1]、…、Arr[n-1]）。其中，每個數(shù)據(jù)元素Arr[i]（0≤i≤n-1）含有d個關鍵字(ki1，ki2，…，kid)。如果對于序列中任意兩個數(shù)據(jù)元素Arr[j]和Arr[i](0≤j<i≤n-1)都滿足：

(kj1，kj2，…，kjd)<(ki1，ki2，…，kid)

則稱數(shù)據(jù)元素序列以關鍵字(k1，k2，…，kd)有序。在次，k1稱為最高位關鍵字，kd稱為最低位關鍵字。

實現(xiàn)多關鍵字排序有兩種常用的方法，一種方法被稱為最高位優(yōu)先法MSD(MostSignificantDigitfirst)，另一種方法被稱為最低位優(yōu)先法LSD(LastSignificantDigitfirst)。最高位優(yōu)先法通常是一個遞歸的過程：首先根據(jù)最高位關鍵字k1進行排序，按k1值的不同，將整個排序表分成若干個子表，每個子表中的數(shù)據(jù)元素具有相同的關鍵字k1。然后分別對每一個每個子表中的數(shù)據(jù)元素根據(jù)關鍵字（k2，…，kd）用最高位優(yōu)先法進行排序。如此遞歸，直到對關鍵字kd完成排序為止。

最低位優(yōu)先法是首先依據(jù)最低位關鍵字kd對排序表中所有數(shù)據(jù)元素進行一趟排序，然后依據(jù)次低位關鍵字kd-1對上一趟排序的結(jié)果再排序，依次重復，直到按關鍵字k1最后一趟排序完成，就可以得到排序的結(jié)果。使用這種排序方法時，每一趟排序都是對整個排序表操作，且需采用穩(wěn)定的排序方法。鏈式基數(shù)排序

基數(shù)排序是一種典型的LSD排序方法，它利用“分配”和“收集”這兩種運算對單關鍵字進行排序。在這種方法中，把關鍵字k看成是一個d元組：

(k1，k2，…，kd)

其中的每一個分量也可以看成是一個關鍵字，假設分量kj(1≤j≤d)有radix種取值，則稱radix為基數(shù)?；鶖?shù)排序的算法思想：對d元組中的每一個分量kj，把排序表中的所有數(shù)據(jù)元素，按kj的取值，先“分配”到radix個隊列（桶）中去，然后再按各隊列的順序，依次把數(shù)據(jù)元素從隊列中“收集”起來，這樣所有數(shù)據(jù)元素按kj取值排序完成。如果對排序表中所有數(shù)據(jù)元素按關鍵字（k1，k2，…，kd），依次對各分量kj（j＝d，d-1