概述插入排序交換排序選擇排序歸并排序基數(shù)排序外排序小結(jié)第九章排序概述排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

數(shù)據(jù)表(datalist):

它是待排序數(shù)據(jù)對象的有限集合。關(guān)鍵碼(key):

通常數(shù)據(jù)對象有多個屬性域，即多個數(shù)據(jù)成員組成，其中有一個屬性域可用來區(qū)分對象，作為排序依據(jù)。該域即為關(guān)鍵碼。每個數(shù)據(jù)表用哪個屬性域作為關(guān)鍵碼，要視具體的應(yīng)用需要而定。即使是同一個表，在解決不同問題的場合也可能取不同的域做關(guān)鍵碼。主關(guān)鍵碼:如果在數(shù)據(jù)表中各個對象的關(guān)鍵碼互不相同，這種關(guān)鍵碼即主關(guān)鍵碼。按照主關(guān)鍵碼進(jìn)行排序，排序的結(jié)果是唯一的。次關(guān)鍵碼:數(shù)據(jù)表中有些對象的關(guān)鍵碼可能相同，這種關(guān)鍵碼稱為次關(guān)鍵碼。按照次關(guān)鍵碼進(jìn)行排序，排序的結(jié)果可能不唯一。排序算法的穩(wěn)定性:如果在對象序列中有兩個對象r[i]和r[j]，它們的關(guān)鍵碼k[i]==k[j]，且在排序之前，對象r[i]排在r[j]前面。如果在排序之后，對象r[i]仍在對象r[j]的前面，則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。內(nèi)排序與外排序:內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。各節(jié)給出算法運(yùn)行時間代價的大略估算一般都按平均情況進(jìn)行估算。對于那些受對象關(guān)鍵碼序列初始排列及對象個數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。靜態(tài)排序:排序的過程是對數(shù)據(jù)對象本身進(jìn)行物理地重排，經(jīng)過比較和判斷，將對象移到合適的位置。這時，數(shù)據(jù)對象一般都存放在一個順序的表中。動態(tài)排序:給每個對象增加一個鏈接指針，在排序的過程中不移動對象或傳送數(shù)據(jù)，僅通過修改鏈接指針來改變對象之間的邏輯順序，從而達(dá)到排序的目的。算法執(zhí)行時所需的附加存儲:評價算法好壞的另一標(biāo)準(zhǔn)。靜態(tài)排序過程中所用到的數(shù)據(jù)表類定義，體現(xiàn)了抽象數(shù)據(jù)類型的思想。待排序數(shù)據(jù)表的類定義#ifndefDATALIST_H#defineDATALIST_H#include<iostream.h>constint

DefaultSize=100;

template<classType>class

datalist

{template<classType>classElement

{private:Typekey;

//關(guān)鍵碼

field

otherdata;

//其它數(shù)據(jù)成員public:Element():key(0),

otherdata(NULL){}

Type

getKey(){return

key;}

//提取關(guān)鍵碼

void

setKey

(constType

x){

key=x;}

//修改

Element<Type>&operator=//賦值(Element<Type>&

x){

this=x;}

intoperator==(Type&

x)//判this==x

{return!(this<x

||

x<this);

}

intoperator!=(Type&

x)//判this!=x

{return

this<x

||

x<this;

}

intoperator<=(Type&

x)//判thisx

{return!(this>x);}

intoperator>=(Type&

x)//判thisx

{return!(this<x);}

intoperator<(Type&

x)//判this<x

{returnthis>x;}

}template<classType>class

datalist

{public:

datalist

(int

MaxSz=DefaultSize)://構(gòu)造函數(shù)

MaxSize(

Maxsz),CurrentSize(0){

Vector=new

Element<Type>[MaxSz];}

void

swap(Element<Type>&x,//對換

Element<Type>&

y){

Element<Type>temp=x;

x=y;

y=temp;}private:

Element<Type>*Vector;

//存儲向量

int

MaxSize,

CurrentSize;

//最大與當(dāng)前個數(shù)}插入排序(InsertSorting)直接插入排序的基本思想是：當(dāng)插入第i(i1)個對象時，前面的V[0],V[1],…,v[i-1]已經(jīng)排好序。這時，用v[i]的關(guān)鍵碼與v[i-1],v[i-2],…的關(guān)鍵碼順序進(jìn)行比較，找到插入位置即將v[i]插入，原來位置上的對象向后順移。插入排序的基本方法是：每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。直接插入排序(InsertSort)各趟排序結(jié)果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=221254925*1608012345012345temp21254925*1608i=4012345temp21254925*1608i=5i=325*16081649161621254925*1608012345012345temp21254925*08i=4時的排序過程012345temp21254925*完成160816i=4j=3i=4j=22525*161621254925*08012345012345temp214925*08012345temp21254925*160816162521i=4j=1i=4j=0i=4j=-116直接插入排序的算法template<classType>void

InsertionSort

(datalist<Type>

&

list){//按關(guān)鍵碼Key非遞減順序?qū)Ρ磉M(jìn)行排序

for(

int

i=1;

i<

list.CurrentSize;

i++)

Insert(list,i);}template<classType>viod

Insert(datalist<Type>

&list,

int

i){

Element<Type>

temp=list.Vector[i];

int

j=i;//從后向前順序比較

算法分析若設(shè)待排序的對象個數(shù)為curremtsize=n，則該算法的主程序執(zhí)行n-1趟。關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與對象關(guān)鍵碼的初始排列有關(guān)。while(j>0&&

temp.getKey

()<list.Vector[j-1].getKey

())

{list.Vector[j]=list.Vector[j-1];

j--;

}

list.Vector[j]=temp;

}最好情況下，排序前對象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€對象的關(guān)鍵碼比較1次，移動2次對象，總的關(guān)鍵碼比較次數(shù)為n-1，對象移動次數(shù)為2(n-1)。最壞情況下，第i趟時第i個對象必須與前面i個對象都做關(guān)鍵碼比較，并且每做1次比較就要做1次數(shù)據(jù)移動。則總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為n2/4。因此，直接插入排序的時間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。折半插入排序(BinaryInsertsort)折半插入排序基本思想是：設(shè)在順序表中有一個對象序列V[0],V[1],…,v[n-1]。其中，v[0],V[1],…,v[i-1]是已經(jīng)排好序的對象。在插入v[i]時，利用折半搜索法尋找v[i]的插入位置。

折半插入排序的算法template<classType>void

BinaryInsertSort

(

datalist<Type>

&list){

for(

int

i=1;

i<list.CurrentSize;

i++)

BinaryInsert

(list,i);}template<classType>void

BinaryInsert

(datalist<Type>

&list,

int

i){

int

left=0,Right=i-1;

Element<Type>temp=list.Vector[i];

while(left<=Right){

int

middle=(left+Right)/2;

if(temp.getKey

()<

list.Vector[middle].getKey())

Right=middle-1;

else

left=middle

+1;}

for(

int

k=i-1;k>=left;k--)

list.Vector[k+1]=list.Vector[k];

算法分析對分查找比順序查找快，所以對分插入排序就平均性能來說比直接插入排序要快。它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對象個數(shù)。在插入第i個對象時，需要經(jīng)過log2i+1次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，將n個對象（為推導(dǎo)方便，設(shè)為n=2k)用對分插入排序所進(jìn)行的關(guān)鍵碼比較次數(shù)為：list.Vector[left]=temp;}當(dāng)n較大時，總關(guān)鍵碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在對象的初始排列已經(jīng)按關(guān)鍵碼排好序或接近有序時，直接插入排序比對分插入排序執(zhí)行的關(guān)鍵碼比較次數(shù)要少。對分插入排序的對象移動次數(shù)與直接插入排序相同，依賴于對象的初始排列。對分插入排序是一個穩(wěn)定的排序方法。鏈表插入排序鏈表插入排序的基本思想是：在每個對象的結(jié)點(diǎn)中增加一個鏈接指針數(shù)據(jù)成員

link。對于存放于數(shù)組中的一組對象V[1],V[2],…,v[n]，若v[1],V[2],…,v[i-1]已經(jīng)通過指針link，按其關(guān)鍵碼的大小，從小到大鏈接起來，現(xiàn)在要插入v[i],i=2,3,…,n，則必須在前面i-1個鏈接起來的對象當(dāng)中，循鏈順序檢測比較，找到v[i]應(yīng)插入(或鏈入)的位置，把v[i]插入，并修改相應(yīng)的鏈接指針。這樣就可得到v[1],V[2],…,v[i]的一個通過鏈接指針排列好的鏈表。如此重復(fù)執(zhí)行，直到把v[n]也插入到鏈表中排好序?yàn)橹埂?54925*16080123456i=2i=321初始currentpreicurrentpre

i

precurrentii=4254925*16080123456i=5i=621precurrenti結(jié)果precurrenti鏈表插入排序示例用于鏈表排序的靜態(tài)鏈表的類定義template<classType>class

staticlinklist;template<classType>classElement

{private:Typekey;

//結(jié)點(diǎn)的關(guān)鍵碼

int

link;

//結(jié)點(diǎn)的鏈接指針public:

Element():key(0),link(NULL){}

Type

getKey(){return

key;}

//提取關(guān)鍵碼

void

setKey

(constType

x){

key=x;}

//修改

int

getLink(){

return

link;}

//提取鏈指針

void

setLink(

constint

l){link=l;

}//設(shè)置指針}

template<classType>class

staticlinklist

{ public:

dstaticlinklist

(

int

MaxSz=DefaultSize):

MaxSize(

Maxsz),

CurrentSize(0)//構(gòu)造函數(shù)

{

Vector=new

Element<Type>[MaxSz];}private:

Element<Type>*Vector;

//存儲向量

int

MaxSize,

CurrentSize;

//向量中最大元素個數(shù)和當(dāng)前元素個數(shù)}鏈表插入排序的算法template<classType>int

LinkInsertSort

(

staticlinklis<Type>&list){

list.Vector[0].setKey(

MaxNum);

list.Vector[0].setLink(1);

list.Vector[1].setLink(0);

//形成循環(huán)鏈表

for(

int

i=2;

i<=list.CurrentSize;

i++){

int

int

current=list.Vector[0].getLink

();

int

pre=0; //前驅(qū)指針

while(list.Vector[current].getKey()<=

list.Vector[i].getKey()

){//找插入位置

pre=current;//pre跟上,current向前走

current=

list.Vector[current].getLink();

}算法分析使用鏈表插入排序，每插入一個對象，最大關(guān)鍵碼比較次數(shù)等于鏈表中已排好序的對象個數(shù)，最小關(guān)鍵碼比較次數(shù)為1。故總的關(guān)鍵碼比較次數(shù)最小為n-1，最大為

list.Vector[i].setLink(current);

list.Vector[pre].setLink(i);

//在pre與current之間鏈入

}}用鏈表插入排序時，對象移動次數(shù)為0。但為了實(shí)現(xiàn)鏈表插入，在每個對象中增加了一個鏈域

link，并使用了vector[0]作為鏈表的表頭結(jié)點(diǎn)，總共用了n個附加域和一個附加對象。算法從i=2開始，從前向后插入。并且在vector[current].Key==vector[i].Key時，current還要向前走一步，pre跟到current原來的位置，此時，vector[pre].Key==vector[i].Key。將vector[i]插在vector[pre]的后面，所以，鏈表插入排序方法是穩(wěn)定的。希爾排序(ShellSort)希爾排序方法又稱為縮小增量排序。該方法的基本思想是：設(shè)待排序?qū)ο笮蛄杏衝個對象，首先取一個整數(shù)gap<n作為間隔，將全部對象分為gap個子序列，所有距離為gap的對象放在同一個子序列中，在每一個子序列中分別施行直接插入排序。然后縮小間隔gap，例如取gap=gap/2，重復(fù)上述的子序列劃分和排序工作。直到最后取gap==1，將所有對象放在同一個序列中排序?yàn)橹埂?1254925*16080123452125*i=10849Gap=32516492516084925*0821252125*1621254925*160801234521i=20849Gap=22516491625*0821254925*08162125*2521254925*160801234521i=308Gap=125164925*開始時

gap的值較大，子序列中的對象較少，排序速度較快；隨著排序進(jìn)展，gap

值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。希爾排序的算法template<classType>void

Shellsort(

datalist<Type>

&list){

int

gap=list.CurrentSize

/2;

//gap是子序列間隔

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

ShellInsert(list,gap);//一趟直接插入排序

gep=

gep==2?1:(int

)(gap/2.2);//修改}}template<classType>voidshellInsert

(

datalist<Type>&list;

constint

gep){

//一趟希爾排序,按間隔gap劃分子序列

for(

int

i=gap;

i<list.CurrentSize;

i++){

Element<Type>

temp=list.Vector[i];

int

j=i;

while(j>=gap

&&

temp.getKey

()<

list.Vector[j-gap].getKey

()){

list.Vector[j]=list.Vector[j-gap];

j-=gap;

}

list.Vector[j]=temp; }}Gap的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。后來knuth提出取gap=gap/3+1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。算法分析對特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對象移動次數(shù)。但想要弄清關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng)n很大時，關(guān)鍵碼平均比較次數(shù)和對象平均移動次數(shù)大約在n1.25到1.6n1.25的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。交換排序(ExchangeSort)起泡排序的基本方法是：設(shè)待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為n。最多作n-1趟，i=1,2,,n-2。在第i

趟中順次兩兩比較v[n-j-1].Key和v[n-j].Key，j=n-1,n-2,,i。如果發(fā)生逆序，則交換v[n-j-1]和v[n-j]。交換排序的基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵碼，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對象都排好序?yàn)橹?。起泡排?BubbleSort)21254925*16080123452125*i=149251625160849Exchang=10825*4921Exchang=1i=2i=30816Exchang=125*252125*012345i=44916Exchang=0082521起泡排序的算法template<classType>void

BubbleSort

(datalist<Type>&list){

int

pass=1;

int

exchange=1;

while(pass<list.CurrentSize

&&

exchange){

BubbleExchange

(list,pass,exchange);

pass++;

}}template<classType>void

BubbleExchange

(datalist<Type>&list,

constint

i,

int&exchange){exchange=0; //交換標(biāo)志置為0,假定未交換

for(

int

j=list.CurrentSize-1;

j>=i;

j--)

if(list.Vector[j-1].getKey

()>

list.Vector[j].getKey

()){ //逆序

Swap(list.Vector[j-1],list.Vector[j]);//交換

exchange=1;

//交換標(biāo)志置為1,有交換

}}第i

趟對待排序?qū)ο笮蛄衯[i-1],v[i],,v[n-1]進(jìn)行排序，結(jié)果將該序列中關(guān)鍵碼最小的對象交換到序列的第一個位置(i-1)，其它對象也都向排序的最終位置移動。當(dāng)然在個別情形下，對象有可能在排序中途向相反的方向移動。這樣最多做n-1趟起泡就能把所有對象排好序。算法分析在對象的初始排列已經(jīng)按關(guān)鍵碼從小到大排好序時，此算法只執(zhí)行一趟起泡，做n-1次關(guān)鍵碼比較，不移動對象。這是最好的情形。

最壞的情形是算法執(zhí)行了n-1趟起泡，第i趟(1

i

n)做了n-i次關(guān)鍵碼比較，執(zhí)行了n-i次對象交換。這樣在最壞情形下總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN為：起泡排序需要一個附加對象以實(shí)現(xiàn)對象值的對換。起泡排序是一個穩(wěn)定的排序方法。快速排序(QuickSort)快速排序方法的基本思想是任取待排序?qū)ο笮蛄兄械哪硞€對象(例如取第一個對象)作為基準(zhǔn)，按照該對象的關(guān)鍵碼大小，將整個對象序列劃分為左右兩個子序列：左側(cè)子序列中所有對象的關(guān)鍵碼都小于或等于基準(zhǔn)對象的關(guān)鍵碼右側(cè)子序列中所有對象的關(guān)鍵碼都大于基準(zhǔn)對象的關(guān)鍵碼基準(zhǔn)對象則排在這兩個子序列中間(這也是該對象最終應(yīng)安放的位置)。

然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的對象都排在相應(yīng)位置上為止。算法描述QuickSort(List){

if(List的長度大于1){

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

LeftList和RightList;

QuickSort(

LeftList);

QuickSort(

RightList

);

將兩個子序列

LeftList和

RightList

合并為一個序列List;

}}21254925*16080123452125*i=149251625160849pivot0825*4921i=2i=3081625*2521pivotpivotpivot21254925*160801234525*i=1劃分251625160849pivotpos0825*49081625*2521pivotpos21比較4次交換25,16iipivotpos21比較1次交換49,0849low

pivotpos交換21,08快速排序的算法template<classType>void

QuickSort

(datalist<Type>&list,

constint

left,

constint

right){//在待排序區(qū)間leftright中遞歸地進(jìn)行快速排序

if(left<right){

int

pivotpos=Partition(list,left,right);//劃分

QuickSort(list,left,

pivotpos-1);

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

QuickSort(list,

pivotpos+1,right);

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

}}template<classType>int

Partition(datalist<Type>&list,

constint

low,

constint

high){

int

pivotpos

=low;

//基準(zhǔn)位置

Element<Type>

pivot=list.Vector[low];

for(

int

i=low+1;

i<=high;i++)if(list.Vector[i].getKey

()<pivot.getKey()

&&++pivotpos

!=i)

Swap(list.Vector[pivotpos],list.Vector[i]);

//小于基準(zhǔn)對象的交換到區(qū)間的左側(cè)去

Swap(list.Vector[low],list.Vector[pivotpos]);

returnpivotpos;}

算法quicksort是一個遞歸的算法，其遞歸樹如圖所示。算法partition利用序列第一個對象作為基準(zhǔn)，將整個序列劃分為左右兩個子序列。算法中執(zhí)行了一個循環(huán)，只要是關(guān)鍵碼小于基準(zhǔn)對象關(guān)鍵碼的對象都移到序列左側(cè)，最后基準(zhǔn)對象安放到位，函數(shù)返回其位置。2125*25490816算法分析從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸樹的深度。如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進(jìn)行排序，這是最理想的情況。在n個元素的序列中，對一個對象定位所需時間為O(n)。若設(shè)t(n)是對n個元素的序列進(jìn)行排序所需的時間，而且每次對一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計(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ù)quicksort的平均計(jì)算時間也是o(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個?？焖倥判蚴沁f歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為log2(n+1)。因此，要求存儲開銷為o(log2n)。在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經(jīng)過n-1趟才能把所有對象定位，而且第i

趟需要經(jīng)過n-i

次關(guān)鍵碼比較才能找到第i

個對象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加存儲(即棧)將達(dá)到o(n)。若能更合理地選擇基準(zhǔn)對象，使得每次劃分所得的兩個子序列中的對象個數(shù)盡可能地接近，可以加速排序速度，但是由于對象的初始排列次序是隨機(jī)的，這個要求很難辦到。有一種改進(jìn)辦法：取每個待排序?qū)ο笮蛄械牡谝粋€對象、最后一個對象和位置接近正中的3個對象，取其關(guān)鍵碼居中者作為基準(zhǔn)對象。用第一個對象作為基準(zhǔn)對象

快速排序退化的例子

08

16212525*4908012345pivot初始

16212525*49

0816

212525*4921

081625

2525*49

081621

25*4925*

0816212549

0816212525*i=1i=2i=3i=4i=5用居中關(guān)鍵碼對象作為基準(zhǔn)對象快速排序是一種不穩(wěn)定的排序方法。對于n較大的平均情況而言，快速排序是“快速”的，但是當(dāng)n很小時，這種排序方法往往比其它簡單排序方法還要慢。

08

16212525*49012345pivot21初始

08

16

21

2525*490825*

0816

21

25

25*49i=1i=2

選擇排序的基本思想是：每一趟(例如第i趟，i=0,1,…,n-2)在后面n-i個待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象,作為有序?qū)ο笮蛄械牡趇個對象。待到第n-2趟作完，待排序?qū)ο笾皇Ｏ?個，就不用再選了。選擇排序直接選擇排序是一種簡單的排序方法，它的基本步驟是：

在一組對象v[i]～v[n-1]中選擇具有最小關(guān)鍵碼的對象；直接選擇排序(SelectSort)

若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調(diào)；

在這組對象中剔除這個具有最小關(guān)鍵碼的對象，在剩下的對象v[i+1]～v[n-1]中重復(fù)執(zhí)行第、步，直到剩余對象只有一個為止。直接選擇排序的算法template<classType>void

SelectSort

(datalist<Type>&list){for(int

i=0;i<list.CurrentSize-1;i++)

SelectExchange

(list,i);}template<classType>void

SelectExchange(datalist<Type>&

list,

constint

i){int

k=i; for(int

j=i+1;j<list.CurrentSize;

j++)if(list.Vector[j].getKey

()<

list.Vector[k].getKey

())

k=j;

//當(dāng)前具最小關(guān)鍵碼的對象

if(k!=i)

//對換到第i個位置

Swap(list.Vector[i],list.Vector[k]

); }21254925*16080123452125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者08交換21,08最小者16交換25,16最小者21交換49,214925*01234525*i=42516084925*4921結(jié)果i=308162521最小者25*無交換最小者25無交換25211608各趟排序后的結(jié)果01234549160825*49210825*2521i=1時選擇排序的過程ikj49250825*1621ikj492525*251625ikj16<2549250825*1621012345ikj2116k

指示當(dāng)前序列中最小者算法分析

直接選擇排序的關(guān)鍵碼比較次數(shù)KCN與對象的初始排列無關(guān)。第i趟選擇具有最小關(guān)鍵碼對象所需的比較次數(shù)總是n-i-1次，此處假定整個待排序?qū)ο笮蛄杏衝個對象。因此，總的關(guān)鍵碼比較次數(shù)為對象的移動次數(shù)與對象序列的初始排列有關(guān)。當(dāng)這組對象的初始狀態(tài)是按其關(guān)鍵碼從小到大有序的時候，對象的移動次數(shù)RMN=0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對象移動次數(shù)為RMN=3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。錦標(biāo)賽排序(TournamentTreeSort)它的思想與體育比賽時的淘汰賽類似。首先取得n個對象的關(guān)鍵碼，進(jìn)行兩兩比較，得到n/2

個比較的優(yōu)勝者(關(guān)鍵碼小者)，作為第一步比較的結(jié)果保留下來。然后對這n/2

個對象再進(jìn)行關(guān)鍵碼的兩兩比較，…，如此重復(fù)，直到選出一個關(guān)鍵碼最小的對象為止。在圖例中，最下面是對象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹的葉結(jié)點(diǎn)，它存放的是所有參加排序的對象的關(guān)鍵碼。如果n不是2的k次冪，則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿足2k-1<n

2k的2k個。葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵碼兩兩比較的結(jié)果。最頂層是樹的根。08Winner2108086325*2121254925*160863tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]勝者樹的概念每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種比賽樹為勝者樹。位于最底層的葉結(jié)點(diǎn)叫做勝者樹的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為勝者樹的內(nèi)結(jié)點(diǎn)。每個結(jié)點(diǎn)除了存放對象的關(guān)鍵碼data外，還存放了此對象是否要參選的標(biāo)志Active和此對象在滿二叉樹中的序號index。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關(guān)鍵碼的對象。08Winner(勝者)2108086325*2121254925*160863tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]

形成初始勝者樹（最小關(guān)鍵碼上升到根）a[0]關(guān)鍵碼比較次數(shù):616Winner(勝者)2116166325*2121254925*1663tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]輸出冠軍并調(diào)整勝者樹后樹的狀態(tài)a[1]關(guān)鍵碼比較次數(shù):221Winner(勝者)21636325*2121254925*63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]輸出亞軍并調(diào)整勝者樹后樹的狀態(tài)a[2]關(guān)鍵碼比較次數(shù):225Winner(勝者)25636325*25254925*63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]輸出第三名并調(diào)整勝者樹后樹的狀態(tài)a[3]關(guān)鍵碼比較次數(shù):225*Winner(勝者)25*636325*4925*63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]輸出第四名并調(diào)整勝者樹后樹的狀態(tài)a[4]關(guān)鍵碼比較次數(shù):263Winner(勝者)636363tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]全部比賽結(jié)果輸出時樹的狀態(tài)a[6]關(guān)鍵碼比較次數(shù):2勝者樹數(shù)據(jù)結(jié)點(diǎn)類的定義template<classType>classDataNode

{public:

Typedata;

//數(shù)據(jù)值

int

index;

//結(jié)點(diǎn)在滿二叉樹中順序號

int

active;

//參選標(biāo)志：=1,參選,=0,不參選}錦標(biāo)賽排序的算法

template<classType>void

TournamentSort

(Type

a[],

int

n){

DataNode<Type>*tree;

DataNode<Type>

item;

int

bottomRowSize=

PowerOfTwo

(n);//乘冪值

int

TreeSize=2*bottomRowSize-1;//總結(jié)點(diǎn)個數(shù)

int

loadindex=bottomRowSize-1;//內(nèi)結(jié)點(diǎn)個數(shù)

tree=new

DataNode<Type>[TreeSize];

int

j=0;//從

a向勝者樹外結(jié)點(diǎn)復(fù)制數(shù)據(jù)

for(int

i=loadindex;

i<TreeSize;i++){

tree[i].index=i;

if(j<n)

{

tree[i].active=1;tree[i].data=a[j++];}

else

tree[i].active=0;

}

i=

loadindex; //進(jìn)行初始比較選擇最小的項(xiàng)

while(i){

j=i;

while(j<2*i){

if(!tree[j+1].active||

//勝者送入雙親

tree[j].data<=tree[j+1].data)

tree[(j-1)/2]=tree[j];

else

tree[(j-1)/2]=tree[j+1];

j+=2;

}

i=(i-1)/2;//i退到雙親,直到i==0為止}

for(i=0;

i<n-1;i++){//處理其它n-1個數(shù)據(jù)

a[i]=tree[0].data;//送出最小數(shù)據(jù)

tree[tree[0].index].active=0;

//失去參選資格

UpdateTree

(tree,tree[0].index);//調(diào)整

}

a[n-1]=tree[0].data;

}

錦標(biāo)賽排序中的調(diào)整算法

template<classType>voidUpdateTree

(DataNode<Type>*tree,

int

i){

if(i%2==0)

tree[(i-1)/2]=tree[i-1];//i偶數(shù),對手左結(jié)點(diǎn)

else

tree[(i-1)/2]=tree[i+1];//i奇數(shù),對手右結(jié)點(diǎn)

i=(i-1)/2;//向上調(diào)整

while(i){//直到

i==0

if(i%2==0)j=i-1;

else

j=i+1;

if(!tree[i].active

||!tree[j].active)

if(tree[i].active)

tree[(i-1)/2]=tree[i];//i可參選,i上

else

tree[(i-1)/2]=tree[j];//否則,j上

else //兩方都可參選

if(tree[i].data<tree[j].data)

tree[(i-1)/2]=tree[i];//關(guān)鍵碼小者上

else

tree[(i-1)/2]=tree[j];

i=(i-1)/2;//i上升到雙親

}}算法分析錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為log2(n+1)，其中n為待排序元素個數(shù)。除第一次選擇具有最小關(guān)鍵碼的對象需要進(jìn)行n-1次關(guān)鍵碼比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵碼對象所需的關(guān)鍵碼比較次數(shù)均為O(log2n)?？傟P(guān)鍵碼比較次數(shù)為O(nlog2n)。對象的移動次數(shù)不超過關(guān)鍵碼的比較次數(shù)，所以錦標(biāo)賽排序總的時間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。如果有n個對象，必須使用至少2n-1個結(jié)點(diǎn)來存放勝者樹。最多需要找到滿足2k-1<n

2k

的k，使用2*2k-1個結(jié)點(diǎn)。每個結(jié)點(diǎn)包括關(guān)鍵碼、對象序號和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個穩(wěn)定的排序方法。堆排序(HeapSort)利用堆及其運(yùn)算，可以很容易地實(shí)現(xiàn)選擇排序的思路。堆排序分為兩個步驟：第一步，根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法FilterDown()形成初始堆，第二步，通過一系列的對象交換和重新調(diào)整堆進(jìn)行排序。建立初始的最大堆212525*491608012345i212525*164908025431i21254925*1608初始關(guān)鍵碼集合21254925*1608i=2時的局部調(diào)整212525*491608012345i492525*16210802543121254925*160849252125*1608i=0時的局部調(diào)整形成最大堆i=1時的局部調(diào)整最大堆的向下調(diào)整算法template<classType>void

MaxHeap<Type>::FilterDown(

constint

i,constint

EndOfHeap){

int

current=i;

intchild=2*i+1;

Type

temp=heap[i];

while(child<=

EndOfHeap){

if(child+1<EndOfHeap

&&

heap[child].getKey()<

heap[child+1].getKey())

child=child+1;

if(temp.getKey()>=heap[child].getKey())

break;

else{

heap[current]=heap[child];

current=child;

child=2*child+1;

}

}

heap[current]=temp;}將表轉(zhuǎn)換成堆for(

int

i=(CurrentSize-2)/2;

i>=0;

i--)

FilterDown(i,CurrentSize-1);

基于初始堆進(jìn)行堆排序最大堆的第一個對象V[0]具有最大的關(guān)鍵碼，將V[0]與V[n]對調(diào)，把具有最大關(guān)鍵碼的對象交換到最后，再對前面的n-1個對象，使用堆的調(diào)整算法FilterDown(0,n-1)，重新建立最大堆。結(jié)果具有次最大關(guān)鍵碼的對象又上浮到堆頂，即V[0]位置。再對調(diào)V[0]和V[n-1]，調(diào)用FilterDown(0,n-2)，對前n-2個對象重新調(diào)整，…。如此反復(fù)執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法，其細(xì)節(jié)在下面的程序中給出。492525*211608012345082525*16214902543149252125*160808252125*1649交換0號與5號對象,5號對象就位初始最大堆2525*082116490123451625*082521490254312525*210816491625*210825

49交換0號與4號對象,4號對象就位從0號到4號重新調(diào)整為最大堆25*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交換0號與3號對象,3號對象就位從0號到3號重新調(diào)整為最大堆211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交換0號與2號對象,2號對象就位從0號到2號重新調(diào)整為最大堆160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交換0號與1號對象,1號對象就位從0號到1號重新調(diào)整為最大堆堆排序的算法template<classType>void

MaxHeap<Type>::

HeapSort

(){//對表heap[0]到heap[n-1]進(jìn)行排序,使得表中各//個對象按其關(guān)鍵碼非遞減有序。

for(

int

i=(CurrentSize-2)/2;

i>=0;

i--)

FilterDown(i,CurrentSize-1);

//初始堆

for(i=CurrentSize-1;

i>=1;

i--){

Swap(heap[0],heap[i]); //交換

FilterDown

(0,i-1); //重建最大堆

}}算法分析若設(shè)堆中有n個結(jié)點(diǎn)，且2k-1

n

2k，則對應(yīng)的完全二叉樹有k層。在第i層上的結(jié)點(diǎn)數(shù)2i(i=0,1,…,k-1)。在第一個形成初始堆的for循環(huán)中對每一個非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法FilterDown()，因此該循環(huán)所用的計(jì)算時間為：其中，i是層序號，2i是第i層的最大結(jié)點(diǎn)數(shù)，(k-i-1)是第i層結(jié)點(diǎn)能夠移動的最大距離。在第二個for循環(huán)中，調(diào)用了n-1次FilterDown()算法，該循環(huán)的計(jì)算時間為O(nlog2n)。因此，堆排序的時間復(fù)雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。歸并排序(MergeSort)歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。對象序列initList中有兩個有序表V[l]…V[m]和V[m+1]…V[n]。它們可歸并成一個有序表，存于另一對象序列mergedList

的V[l]