140-1概述插入排序交換排序選擇排序歸并排序基數排序第九章排序140-2概述排序：將一組雜亂無章的數據按一定的規律順次排列起來。

數據表(datalist):它是待排序數據元素的有限集合。排序碼(key):通常數據元素有多個屬性域,即多個數據成員組成,其中有一個屬性域可用來區分元素,作為排序依據。該域即為排序碼。每個數據表用哪個屬性域作為排序碼，要視具體的應用需要而定。140-3排序算法的穩定性:如果在元素序列中有兩個元素r[i]和r[j],它們的排序碼k[i]

==k[j]

,且在排序之前,元素r[i]排在r[j]前面。如果在排序之后,元素r[i]仍在元素r[j]的前面,則稱這個排序方法是穩定的,否則稱這個排序方法是不穩定的。內排序與外排序:內排序是指在排序期間數據元素全部存放在內存的排序；外排序是指在排序期間全部元素個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。140-4排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執行中的數據比較次數與數據移動次數來衡量。算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受元素排序碼序列初始排列及元素個數影響較大的，需要按最好情況和最壞情況進行估算。算法執行時所需的附加存儲:評價算法好壞的另一標準。140-5待排序數據表的類定義#include<iostream.h>constintDefaultSize=100;template<classT>classElement{ //數據表元素定義public:

Tkey; //排序碼

fieldotherdata; //其他數據成員

Element<T>&operator=(Element<T>&x){

key=x.key;otherdata=x.otherdata;returnthis;}140-6booloperator==(Element<T>&x)

{returnkey==x.key;} //判*this與x相等

booloperator<=(Element<T>&x)

{returnkey<=x.key;} //判*this小于或等于xbooloperator>=(Element<T>&x)

{returnkey>=x.key;} //判*this大于或等于xbooloperator>(Element<T>&x)

{returnkey>x.key;} //判*this大于xbooloperator<(Element<T>&x)

{returnkey<x.key;} //判*this小于x};140-7template<classT>classdataList{ //數據表類定義private:

Element<T>*Vector; //存儲排序元素的向量

intmaxSize; //向量中最大元素個數

intcurrentSize; //當前元素個數public:

datalist(intmaxSz=DefaultSize)://構造函數

maxSize(maxSz),currentSize(0)

{Vector=newElement<T>[maxSize];}intLength(){returncurrentSize;} //取表長度140-8

voidSwap(Element<T>&x,Element<T>&y){Element<T>temp=x;x=y;y=temp;}Element<T>&operator[](inti)

//取第i個元素

{returnVector[i];} intPartition(constintlow,constinthigh);

//快速排序劃分};140-9插入排序(InsertSorting)基本方法是：每步將一個待排序的元素，按其排序碼大小，插入到前面已經排好序的一組元素的適當位置上,直到元素全部插入為止。基本思想是:當插入第i(i≥1)個元素時，前面的V[0],V[1],…,V[i-1]已經排好序。這時，用V[i]的排序碼與V[i-1],V[i-2],…的排序碼順序進行比較，插入位置即將V[i]插入，原來位置上的元素向后順移。直接插入排序(InsertSort)140-10各趟排序結果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=2140-11012345i=4i=5i=3012345temp21254925*16081621254925*160825*012345temp21254925*160808140-1221254925*1608012345i=4時的排序過程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=3i=4j=2140-132516012345temp214925*08162525*1621254925*0801234516i=4j=1i=4j=0i=4j=-1012345temp21254925*08162116140-14直接插入排序的算法#include"dataList.h"template<classT>voidInsertSort(dataList<T>&L,intleft,intright){//依次將元素L.Vector[i]按其排序碼插入到有序表//L.Vector[left],…,L.Vector[i-1]中,使得//L.Vector[left]到L.Vector[i]有序。

Element<T>temp;inti,j;for(i=left+1;i<=right;i++)if(L[i]<L[i-1]){

temp=L[i];j=i-1; 140-15do{

L[j+1]=L[j];j--;}while(j>=left&&temp<L[j]);

L[j+1]=temp;}}; 算法分析設待排序元素個數為currentSize=n,則該算法的主程序執行n-1趟。排序碼比較次數和元素移動次數與元素排序碼的初始排列有關。140-16最好情況下，排序前元素已按排序碼從小到大有序，每趟只需與前面有序元素序列的最后一個元素比較1次，總的排序碼比較次數為n-1,元素移動次數為0。最壞情況下,第i趟時第i個元素必須與前面i個元素都做排序碼比較,并且每做1次比較就要做1次數據移動。則總排序碼比較次數KCN和元素移動次數RMN分別為140-17平均情況下排序的時間復雜度為o(n2)。直接插入排序是一種穩定的排序方法。基本思想是:設在順序表中有一個元素序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經排好序的元素。在插入V[i]時,利用折半搜索法尋找V[i]的插入位置。折半插入排序的算法#include"dataList.h"

折半插入排序(BinaryInsertsort)140-18template<classT>voidBinaryInsertSort(dataList<T>&L,constintleft,constintright){//利用折半搜索,在L.Vector[left]到L.Vector[i-1]中//查找L.Vector[i]應插入的位置,再進行插入。

Element<T>temp;inti,low,high,middle,k;for(i=left+1;i<=right;i++){

temp=L[i];low=left;high=i-1;while(low<=high){ //折半搜索插入位置

middle=(low+high)/2;

//取中點140-19if(temp<L[middle])

//插入值小于中點值

high=middle-1; //向左縮小區間

elselow=middle+1; //否則,向右縮小區間

}for(k=i-1;k>=low;k--)

L[k+1]=L[k];

//成塊移動,空出插入位置

L[low]=temp; //插入

}};算法分析折半搜索比順序搜索快,所以折半插入排序就140-20

平均性能來說比直接插入排序要快。它所需的排序碼比較次數與待排序元素序列的初始排列無關，僅依賴于元素個數。在插入第i個元素時，需要經過log2i+1

次排序碼比較,才能確定它應插入的位置。因此，將n個元素(為推導方便,設為n=2k)用折半插入排序所進行的排序碼比較次數為：折半插入排序是一個穩定的排序方法。

140-21當n較大時，總排序碼比較次數比直接插入排序的最壞情況要好得多，但比其最好情況要差。在元素的初始排列已經按排序碼排好序或接近有序時，直接插入排序比折半插入排序執行的排序碼比較次數要少。折半插入排序的元素移動次數與直接插入排序相同，依賴于元素的初始排列。140-22鏈表插入排序基本思想是：在每個元素的結點中增加一個鏈接指針數據成員link。對于數組中的一組元素V[1],…,V[n],若V[1],… …,V[i-1]已經通過指針link,按其排序碼從小到大鏈接起來。現要插入V[i],i=2,3,…,n,則必須在前面i-1個鏈接起來的元素當中，循鏈檢測比較，找到V[i]應插入的位置，把V[i]鏈入，并修改相應鏈接指針。從而得到V[1],…,V[i]的一個通過指針排好的鏈表。如此重復執行，直到把V[n]也插入到鏈表中排好序為止。140-23i=2i=3254925*1608012345621初始currentpreicurrentpre

i

precurrentii=4140-24i=5i=6254925*1608012345621

precurrenti結果precurrenti140-25用于鏈表排序的靜態鏈表的類定義constintDefaultSize=10; //在staticList.h文件中

template<classT>structElement{ //靜態鏈表元素類定義

Tkey; //排序碼，其它信息略

intlink; //結點的鏈接指針

Element():link(0){} //構造函數

Element(Tx,intnext=0):key(x),link(next){}

//構造函數

}template<classT>140-26classstaticLinkedList{ //靜態鏈表的類定義public:

staticLinkedList(intsz=DefaultSize){

maxSize=sz;n=0;

Vector=newElement<T>[sz];}

Element<T>&operator[](inti){returnVector[i];}private:

Element<T>*Vector; //存儲元素的向量

intmaxSize; //最大元素個數

intn; //當前元素個數};140-27鏈表插入排序的算法#include"staticList.h"constTmaxData; //排序碼集合中的最大值template<classT>intinsertSort(staticLinkedList<T>&L){//對L.Vector[1],...,L.Vector[n]按其排序碼key排序,//L.Vector[0]做為排序后各個元素所構成的有序循//環鏈表的附加頭結點使用

L[0].key=maxData;L[0].link=1;L[1].link=0;

//形成只有一個元素的循環鏈表140-28inti,pre,p;for(i=2;i<=n;i++){

//每趟向有序鏈表中插入一個結點

p=L[0].link; //p是鏈表檢測指針

pre=0; //pre指向p的前驅

while(L[p].key<=L[i].key)//循鏈找插入位置

{pre=p;p=L[p].link;}

L[i].link=p;L[pre].link=i;//結點i鏈入

}};140-29算法分析使用鏈表插入排序,每插入一個元素,最大排序碼比較次數等于鏈表中已排好序的元素個數,最小排序碼比較次數為1。故總的排序碼比較次數最小為n-1，最大為用鏈表插入排序時，元素移動次數為0。但為了實現鏈表插入，在每個元素中增加了一個鏈域link，并使用了Vector[0]作為鏈表的表頭結點,用了n個附加域和一個附加元素。140-30算法在Vector[pre].key==Vector[i].key時，將Vector[i]插在Vector[pre]的后面，所以，鏈表插入排序方法是穩定的。希爾排序方法又稱為縮小增量排序。該方法的基本思想是:設待排序元素序列有n個元素,首先取一個整數gap<n作為間隔，將全部元素分為gap個子序列，所有距離為gap的元素放在同一個子序列中，在每一個子序列中分別希爾排序(ShellSort)140-31

施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復上述的子序列劃分和排序工作。直到最后取gap==1，將所有元素放在同一個序列中排序為止。開始時

gap

的值較大，子序列中的元素較少，排序速度較快;隨著排序進展，gap值逐漸變小,子序列中元素個數逐漸變多，由于前面工作的基礎，大多數元素已基本有序，所以排序速度仍然很快。140-3221254925*16080123452125*i

=10849Gap=32516492516084925*0821252125*16140-3321254925*160801234521i=20849Gap=22516491625*0821254925*08162125*25140-3421254925*160801234521i

=308Gap=125164925*#include"dataList.h"template<classT>

希爾排序的算法140-35voidShellsort(dataList<T>&L,constintleft,constintright){inti,j,gap=right-left+1; //增量的初始值

Element<T>temp;do{

gap=gap/3+1; //求下一增量值

for(i=left+gap;i<=right;i++)if(L[i]<L[i-gap]){ //逆序

temp=L[i];j=i-gap;do{

L[j+gap]=L[j];j=j-gap;}while(j>=

left&&temp<L[j]);140-36

L[j+gap]=temp; //將vector[i]回送

}}while(gap>1);};算法分析Gap的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。knuth提出取gap=gap/3+1。還有人提出都取奇數為好，也有人提出各gap互質為好。對特定的待排序元素序列，可以準確地估算排序碼的比較次數和元素移動次數。140-37想要弄清排序碼比較次數和元素移動次數與增量選擇之間的依賴關系，并給出完整的數學分析，還沒有人能夠做到。Knuth利用大量實驗統計資料得出:當n很大時，排序碼平均比較次數和元素平均移動次數大約在n1.25到1.6n1.25的范圍內。這是在利用直接插入排序作為子序列排序方法的情況下得到的。希爾排序是一種不穩定的排序方法。140-38交換排序(ExchangeSort)基本思想是兩兩比較待排序元素的排序碼，如果發生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有元素都排好序為止。基本方法是：設待排序元素序列中的元素個數為n。最多作n-1趟，i=1,2,,n-1。在第i

趟中從后向前，j=n-1,n-2,,i，順次兩兩比較V[j-1].key和V[j].key。如果發生逆序，則交換V[j-1]和V[j]。起泡排序(BubbleSort)140-3921254925*16080123452125*i=149251625160849Exchang=10825*4921Exchang=1i=2i=30816Exchang=125*2521140-4025*012345i=44916Exchang=0082521起泡排序的算法template<classT>voidBubbleSort(dataList<T>&L,constintleft,

constintright){

intpass=left+1,exchange=1;

while(pass<=right&&exchange){exchange=0; //標志為0假定未交換

for(intj=right;j>=pass;j--)140-41if(L[j-1]>L[j]){ //逆序

Swap(L[j-1],L[j]); //交換

exchange=1;

//標志置為1,有交換

}pass++;

}};算法分析第i趟對待排序元素序列V[i-1],V[i],,V[right]進行排序，結果將該序列中排序碼最小的元素交換到序列的第一個位置(i-1)。140-42最多做n-1趟起泡就能把所有元素排好序。在元素的初始排列已經按排序碼從小到大排好序時，此算法只執行一趟起泡，做n-1次排序碼比較，不移動元素。這是最好的情形。最壞的情形是算法執行n-1趟起泡,第i趟(1≤

in)做n-i次排序碼比較,執行n-i次元素交換。在最壞情形下總的排序碼比較次數KCN和元素移動次數RMN為：140-43起泡排序需要一個附加元素以實現元素值的對換。起泡排序是一個穩定的排序方法。基本思想是任取待排序元素序列中的某個元素(例如取第一個元素)作為基準，按照該元素的排序碼大小，將整個元素序列劃分為左右兩個子序列：左側子序列中所有元素的排序碼都小于或等于基準元素的排序碼快速排序(QuickSort)140-44右側子序列中所有元素的排序碼都大于基準元素的排序碼基準元素則排在這兩個子序列中間(這也是該元素最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的元素都排在相應位置上為止。140-45QuickSort(List){if(List的長度大于1){

將序列List劃分為兩個子序列

LeftList和

RightList;QuickSort(LeftList);QuickSort(RightList);

將兩個子序列

LeftList和

RightList

合并為一個序列List;}}算法描述140-4621254925*16080123452125*i=14925*1625160849pivot08254921i=2i=308162525*21pivotpivotpivot140-4721254925*160801234525*i=1劃分251625160849pivotpos0825*49081625*2521pivotpos21比較4次交換25,16iipivotpos21比較1次交換49,0849lowpivotpos交換21,08140-48快速排序的算法#include"dataList.h"template<classT>voidQuickSort(dataList<T>&L,constintleft,constintright){//對元素Vector[left],...,Vector[right]進行排序,//pivot=L.Vector[left]是基準元素,排序結束后它的//位置在pivotPos,把參加排序的序列分成兩部分,

//左邊元素的排序碼都小于或等于它,右邊都大于它

if(left<right){ //元素序列長度大于1時

intpivotpos=L.Partition(left,right);//劃分

QuickSort(L,left,pivotpos-1);140-49

QuickSort(L,pivotpos+1,right); }};template<classT>intdataList<T>::Partition(constintlow,constinthigh){//數據表類的共有函數

intpivotpos=low;

Element<T>pivot=Vector[low]; //基準元素

for(inti=low+1;i<=high;i++)

//檢測整個序列,進行劃分140-50if(Vector[i]<pivot){

pivotpos++;if(pivotpos!=i)

Swap(Vector[pivotpos],Vector[i]);} //小于基準的交換到左側去

Vector[low]=Vector[pivotpos];

Vector[pivotpos]=pivot; //將基準元素就位

returnpivotpos; //返回基準元素位置};算法分析140-51

算法quicksort是一個遞歸的算法,其遞歸樹如圖所示。算法partition利用序列第一個元素作為基準，將整個序列劃分為左右兩個子序列。算法中執行了一個循環，只要是排序碼小于基準元素排序碼的元素都移到序列左側，最后基準元素安2125*25490816140-52

到位,函數返回其位置。從快速排序算法的遞歸樹可知，快速排序的趟數取決于遞歸樹的高度。如果每次劃分對一個元素定位后，該元素的左側子序列與右側子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。在n個元素的序列中，對一個元素定位所需時間為O(n)。若設t(n)是對n個元素的序列進行排序所需的時間，且每次對一個元素正確定位后，正好把序列分為長度相等的兩個子序列，140-53此時,總的計算時間為：

T(n)

cn+2T(n/2)//c是一個常數

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)可以證明，函數quicksort的平均計算時間也是O(nlog2n)。實驗結果表明:就平均計算時間而言，快速排序是內排序方法中最好的一個。快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數。140-54最大遞歸調用層次數與遞歸樹高度一致，理想情況為log2(n+1)。存儲開銷為O(log2n)。在最壞的情況，即待排序元素序列已經按其排序碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個元素的子序列。必須經過n-1趟才能把所有元素定位，而且第i

趟需要經過n-i

次排序碼比較才能找到第i

個元素的安放位置，總的排序碼比較次數將達到140-55用第一個元素作為基準元素

快速排序退化的例子

08

16212525*4908012345pivot初始

16212525*49

0816

212525*4921

081625

2525*49

081621

25*4925*

0816212549

0816212525*i=1i=2i=3i=4i=5140-56用居中排序碼元素作為基準元素

08

16212525*49012345pivot21初始

08

16

21

2525*490825*

0816

21

25

25*49i=1i=2其排序速度退化到簡單排序的水平,比直接插入排序還慢。占用附加存儲(棧)將達到O(n)。改進辦法:取每個待排序元素序列的第一個元素、最后一個元素和位置接近正中的3個元素，取其排序碼居中者作為基準元素。140-57快速排序是一種不穩定的排序方法。對于n較大的平均情況而言,快速排序是“快速”的,但是當n很小時,這種排序方法往往比其它簡單排序方法還要慢。因此，當n很小時可以用直接插入排序方法。140-58選擇排序基本思想是:每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i個待排序元素中選出排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟作完，待排序元素只剩下1個,就不用再選了。140-59直接選擇排序(SelectSort)直接選擇排序的基本步驟是：在一組元素V[i]～V[n-1]中選擇具有最小排序碼的元素；若它不是這組元素中的第一個元素,則將它與這組元素中的第一個元素對調;在這組元素中剔除這個具有最小排序碼的元素。在剩下的元素V[i+1]～

V[n-1]中重復執行第①、②步,直到剩余元素只有一個為止。140-6021254925*16080123452125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者

08交換21,08最小者

16交換25,16最小者

21交換49,21140-614925*01234525*i=42516084925*4921結果i=308162521最小者

25*無交換最小者

25無交換25211608各趟排序后的結果140-62直接選擇排序的算法#include"dataList.h"template<classT>voidSelectSort(dataList<T>&L,constintleft,constintright){for(inti=left;i<right;i++){intk=i;//在L[i]到L[n-1]找最小排序碼元素

for(intj=i+1;j<=right;j++)

if(L[j]<L[k])k=j;if(k!=i)Swap(L[i],L[k]); //交換

}};140-63i=1時選擇排序的過程012345160825*492125ikj492549250825*1621ikj25*25140-64490825*211625ikj16<2549250825*1621012345ikj2116k

指示當前序列中最小者140-65直接選擇排序的排序碼比較次數KCN與元素的初始排列無關。設整個待排序元素序列有n個元素，則第i趟選擇具有最小排序碼元素所需的比較次數總是n-i-1次。總的排序碼比較次數為元素移動次數與元素序列初始排列有關。當這組元素初始狀態是按其排序碼從小到大有序的時候,元素的移動次數達到最少RMN=0，。140-66最壞情況是每一趟都要進行交換，總的元素移動次數為RMN=3(n-1)。直接選擇排序是一種不穩定的排序方法。若待排序的數據元素順序存放于單鏈表中，每一趟排序先在鏈表中選擇關鍵碼值最大的元素，將它從鏈中摘下，再插入一個初始為空的新鏈表的首部。當所有元素都從原鏈表中摘下并插入到新鏈表中，則新鏈表中元素已經有序鏈接起來。鏈表直接選擇排序140-67鏈表直接選擇排序的算法#include"staticList.h"template<classT>intselectSort(staticLinkedList<T>&L){//L.Vector[0]作為表頭結點使用，L.Vector[1].data//到L.Vector[n].data存放數據

intf=L[0].link,p,q,r,s;

L[0].link=0;

while(f!=0){ //原始鏈表未掃描完

p=s=f;q=r=0; //s指示當前最大元素

while(p!=0){140-68if(L[p].data>L[s].data){s=p;r=q;}

//記憶當前找到的排序碼最大結點

q=p;p=L[p].link;}if(s==f)f=L[f].link;

//結點s從鏈中摘下

elseL[r].link=L[s].link;L[s].link=L[0].link;

L[0].link=s;

//結點s插入到結果鏈表的前端

}};140-69它的思想與體育比賽時的淘汰賽類似。首先取得n個元素的排序碼，進行兩兩比較，得到n/2

個比較的優勝者(排序碼小者)，作為第一步比較的結果保留下來。然后對這n/2

個元素再進行排序碼的兩兩比較,…,如此重復，直到選出一個排序碼最小的元素為止。由于每次兩兩比較的結果是把排序碼小者作為優勝者上升到雙親結點，所以稱這種比賽樹為勝者樹。錦標賽排序(TournamentTreeSort)140-70在圖例中，最下面是元素排列的初始狀態，相當于一棵完全二叉樹的葉結點，它存放的是所有參加排序的元素的排序碼。08Winner

21080825*2121254925*160863e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]140-71在勝者樹中，位于最底層的葉結點叫做勝者樹的外結點，非葉結點稱為勝者樹的內結點。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小排序碼的元素。外結點的個數為n時，內結點的個數為n-1。定義根到最遠層內結點的路徑長度s為從根到該內結點路徑上的分支條數，則有

s=log2(n-1)這樣，最遠層最左端的內結點的編號為2s，最遠層的內結點個數為n-2s，而最遠層外結點個數等于最遠層內結點個數的2倍。140-72上例中，外結點數n=7，s=log26=2，最遠層最左端的內結點編號為2s=4，該層的內結點數共有m=

n-2s=7-4=3，最遠層的外結點數為lowExt=2m=6，次遠層最左端的外部結點編號為lowExt+1=7。

0821080825*2121254925*160863e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]140-73若已知某外結點的編號為i，則其雙親結點（內結點）的編號為k，則：其中offset=2s+1-1，指最遠層最左端外結點之前結點（包括所有內結點和次遠層外結點）個數。i≤lowExt

即最遠層外結點，i>lowExt

即次遠層外結點。140-74勝者樹的類定義

template<classT>classWinnerTree{private: intmaxSize; //允許的最大選手數

intn; //當前大小(外部結點數) intlowExt; //最遠層外部結點數

intoffset; //偏移(加1即為第1個外結點) int*t; //勝者樹數組

T*e; //選手數組

voidPlay(intk,intlc,intrc,int(*Winner)(inta,intb));140-75public:constTmaxValue=……; //序列中不可能的大值

WinnerTree(intTreeSize=20)

//構造函數

:maxSize(TreeSize),n(0)

{t=newint[TreeSize];}

～WinnerTree(){delete[]t;} //析構函數

boolInitial(Ta[],intsize,int(*Winner)(inta,intb));boolrePlay(inti,int(*Winner)(inta,intb));

//重構

voidUpdate(){e[t[1]]=maxValue;} //修改

intWinner()const{return(n!=0)?t[1]:0;} //取最終勝者140-76 intWinner(inti)const{return(i<n)?t[i]:0;} //取第i個勝者

intWinner(inta,intb){return(e[a]<=e[b])?

e[a]:e[b];} //取兩外結點勝者};template<classT>boolWinnerTree<T>::Initial(Ta[],intsize,int(*Winner)(inta,intb)){//a[]是勝者樹選手數組,size是選手數，函數Winner//用于得到兩選手a,b比賽的勝者初始化勝者樹的算法140-77if(size>maxSize||size<2)returnfalse;

n=size;e=a;inti,s;for(s=1;2*s<=n-1;s+=s);//計算s=2^log2(n-1)

lowExt=2*(n-s);offset=2*s-1;for(i=2;i<=lowExt;i+=2)

//最遠層外結點比賽

Play((offset+i)/2,i-1,i,Winner);

//選手i-1和i比賽,勝者升入雙親(offset+i)/2if(n%2==0)i=lowExt+2；//次遠層外結點比賽

else{//當n為奇數時,內結點要與外結點比賽

Play(n/2,t[n-1],lowExt+1,Winner);140-78

i=lowExt+3; //i再進到次遠層其他外結點

} for(;i<=n;i+=2)

//其他次遠層外結點比賽

Play((i-lowExt+n-1)/2,i-1,i,Winner);returntrue;};通過初始化操作，形成勝者樹，最后勝者進入樹的根結點。此操作調用n/2次Play算法，而Play算法逐層向上比較，次數不超過log2n。140-79template<classT>voidWinnerTree<T>::Play(intk,intlc,intrc,int(*Winner)(inta,intb)){//通過比賽對樹初始化。在t[k]處開始比賽,lc和rc是//t[k]的左子女和右子女。

t[k]=Winner(lc,rc); //在e[lc]和e[rc]間選出勝者

while(k>1&&k%2!=0){

//從右子女向上比賽,直到根

t[k/2]=Winner(t[k-1],t[k]);

k/=2; //到雙親結點

}};140-80重新比賽,重構勝者樹的算法一旦選手i最后勝者，就將其值改為“∞”，使得以后不再參選。此時，需要重新進行外結點e[i]到根t[1]路徑上的比賽。重新執行從勝者對應的外結點到根的路徑上的比賽次數等于e[i]到根t[1]的路徑上的分支數。template<classT>boolWinnerTree<T>::rePlay(inti,int(*Winner(inta,intb)){//針對元素i值的改變，重新組織勝者樹。140-81if(i<=0||i>n)returnfalse;intk,lc,rc; //比賽結點及其左右子女

if(i<=lowExt){ //最遠層外結點

k=(offset+i)/2; //計算

i的雙親

lc=2*k-offset;rc=lc+1;//計算左右子女

}else{ //次遠層外結點

k=(i-lowExt+n-1)/2;if(2*k==n-1){lc=t[2*k];rc=i;}else{lc=2*k-n+1+lowExt;rc=lc+1;}}140-82

t[k]=Winner(lc,rc);

k/=2;for(;k>=1;k/=2)

//逐層向上比賽直到根

t[k]=Winner(t[2*k],t[2*k+1]);};template<classT>voidTournamentSort(Ta[],constintleft,constintright){//建立樹的順序存儲數組tree,將數組a[]中的元素復錦標賽排序的算法

140-83//復制到勝者樹中,對它們進行排序,并把結果返送//回數組中,left和right是排序元素的起點和終點。

size=right-left+1; //待排序元素個數

WinnerTree<T>WT(size); //勝者樹對象

Tdata[size+1]; //存儲輸入數據

inti; for(i=1;i<=size;i++)cin>>data[i];

WT.Initial(data,size,Winner);//構造初始勝者樹

for(i=0;i<size;i++){

a[i]=WT.Winner(); //輸出勝者

WT.Update(); //修改勝者的值

140-84WT.rePlay(t[1],Winner); //重構勝者樹

if(WT.Winner()==maxValue)break; }};勝者樹是完全二叉樹,其高度為log2n,其中n

為待排序元素個數。除第一次選擇具有最小排序碼的元素需要進行n-1次排序碼比較外,重構勝者樹選擇次小、再次小排序碼所需的比較次數均為O(log2n)。總排序碼比較次數為O(nlog2n)。140-850821080825*2121254925*160863e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]

形成初始勝者樹（最小排序碼上升到根）排序碼比較次數

:6

Winner

(勝者)e[6]=08VS.

VS.

VS.

VS.

VS.

VS.

140-861621161625*2121254925*16∞63e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]排序碼比較次數

:3

Winner

(勝者)e[5]=16VS.

VS.

輸出冠軍e[6]=08并調整勝者樹后樹的狀態VS.

140-87212163∞25*2121254925*∞∞63e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]排序碼比較次數

:3

Winner

(勝者)e[1]=21VS.

VS.

輸出冠軍e[5]=16并調整勝者樹后樹的狀態VS.

140-88252563∞25*25∞254925*∞∞63e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]排序碼比較次數

:3

Winner

(勝者)e[2]=25VS.

VS.

輸出冠軍e[1]=21并調整勝者樹后樹的狀態VS.

140-8925*25*63∞25*∞∞∞4925*∞∞63e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]排序碼比較次數

:3

Winner

(勝者)e[4]=25*VS.

VS.

輸出冠軍e[2]=25并調整勝者樹后樹的狀態VS.

140-90494963∞49∞∞∞49∞∞∞63e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]排序碼比較次數

:3

Winner

(勝者)e[3]=49VS.

VS.

輸出冠軍e[4]=25*并調整勝者樹后樹的狀態VS.

140-9163∞63∞∞∞∞∞∞∞∞∞63e[1]e[2]e[3]e[4]e[5]e[6]e[7]t[1]t[2]t[3]t[4]t[5]t[6]排序碼比較次數

:3

Winner

(勝者)e[7]=63VS.

VS.

輸出冠軍e[3]=49并調整勝者樹后樹的狀態VS.

140-92這種排序方法雖然減少了許多排序時間,但是使用了較多的附加存儲。如果有n個元素，必須使用至少2n-1個結點來存放勝者樹。錦標賽排序是一個穩定的排序方法。140-93堆排序(HeapSort)利用堆及其運算,可以很容易地實現選擇排序的思路。堆排序分為兩個步驟根據初始輸入數據，利用堆的調整算法siftDown()形成初始堆;通過一系列的元素交換和重新調整堆進行排序。為了實現元素按排序碼從小到大排序，要求建立最大堆。

140-94建立初始的最大堆212525*491608012345i212525*164908025431i21254925*1608初始排序碼集合21254925*1608i=2時的局部調整140-95212525*491608012345i492525*16210802543121254925*160849252125*1608i=0時的局部調整形成最大堆i=1時的局部調整140-96最大堆的向下調整算法template<classT>siftDown(dataList<T>&L,

constintstart,constintm){//私有函數:從結點start開始到m自上向下比較,//如果子女的值大于雙親的值,則相互交換,將一//個集合局部調整為最大堆。

inti=start;intj=2*i+1; //j是i的左子女

Element<T>temp=L[i]; //暫存子樹根結點

while(j<=m){ //逐層比較

if(j<m&&L[j]<L[j+1])j++;

//讓j指向兩子女中的大者

if(temp>=L[j])break; //temp排序碼大不調整140-97else{ //否則子女中的大者上移

L[i]=L[j];

i=j;j=2*j+1; //i下降到子女位置

}}

L[i]=temp; //temp放到合適位置};最大堆堆頂L.Vector[0]具有最大的排序碼，將L.Vector[0]與L.Vector[n-1]對調,把具有最大基于初始堆進行堆排序140-98

排序碼的元素交換到最后，再對前面的n-1個元素,使用堆的調整算法siftDown(L,0,n-2)，重新建立最大堆，具有次最大排序碼的元素又上浮到L.Vector[0]位置。再對調L.Vector[0]和L.Vector[n-2]，再調用