文章標(biāo)題：各種排序算法小結(jié)
原 作 者：不詳
原 出 處：不詳
發(fā) 布 者：loose_went
發(fā)布類型：轉(zhuǎn)載
發(fā)布日期：2004-09-03
今日瀏覽：6
總 瀏 覽：804
  

排序算法是一種基本并且常用的算法。由于實(shí)際工作中處理的數(shù)量巨大，所以排序算法 
對(duì)算法本身的速度要求很高。 
而一般我們所謂的算法的性能主要是指算法的復(fù)雜度，一般用O方法來表示。在后面我將 
給出詳細(xì)的說明。 

對(duì)于排序的算法我想先做一點(diǎn)簡(jiǎn)單的介紹，也是給這篇文章理一個(gè)提綱。 
我將按照算法的復(fù)雜度，從簡(jiǎn)單到難來分析算法。 
第一部分是簡(jiǎn)單排序算法，后面你將看到他們的共同點(diǎn)是算法復(fù)雜度為O(N*N)（因?yàn)闆]有 
使用word,所以無法打出上標(biāo)和下標(biāo)）。 
第二部分是高級(jí)排序算法，復(fù)雜度為O(Log2(N))。這里我們只介紹一種算法。另外還有幾種 
算法因?yàn)樯婕皹渑c堆的概念，所以這里不于討論。 
第三部分類似動(dòng)腦筋。這里的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較 
奇特，值得參考（編程的角度）。同時(shí)也可以讓我們從另外的角度來認(rèn)識(shí)這個(gè)問題。 
第四部分是我送給大家的一個(gè)餐后的甜點(diǎn)——一個(gè)基于模板的通用快速排序。由于是模板函數(shù) 
可以對(duì)任何數(shù)據(jù)類型排序（抱歉，里面使用了一些論壇專家的呢稱）。 

現(xiàn)在，讓我們開始吧： 

一、簡(jiǎn)單排序算法 
由于程序比較簡(jiǎn)單，所以沒有加什么注釋。所有的程序都給出了完整的運(yùn)行代碼，并在我的VC環(huán)境 
下運(yùn)行通過。因?yàn)闆]有涉及MFC和WINDOWS的內(nèi)容，所以在BORLAND C++的平臺(tái)上應(yīng)該也不會(huì)有什么 
問題的。在代碼的后面給出了運(yùn)行過程示意，希望對(duì)理解有幫助。 

1.冒泡法： 
這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩?
#include <iostream.h> 

void BubbleSort(int* pData,int Count) 
{ 
int iTemp; 
for(int i=1;i<Count;i++) 
{ 
for(int j=Count-1;j>=i;j--) 
{ 
if(pData[j]<pData[j-1]) 
{ 
iTemp = pData[j-1]; 
pData[j-1] = pData[j]; 
pData[j] = iTemp; 
} 
} 
} 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4}; 
BubbleSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 

倒序(最糟情況) 
第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次) 
第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次) 
第一輪：7,8,10,9->7,8,9,10(交換1次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：6次 

其他： 
第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次) 
第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次) 
第一輪：7,8,10,9->7,8,9,10(交換1次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：3次 

上面我們給出了程序段，現(xiàn)在我們分析它：這里，影響我們算法性能的主要部分是循環(huán)和交換， 
顯然，次數(shù)越多，性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為1+2+...+n-1。 
寫成公式就是1/2*(n-1)*n。 
現(xiàn)在注意，我們給出O方法的定義： 

若存在一常量K和起點(diǎn)n0，使當(dāng)n>=n0時(shí)，有f(n)<=K*g(n),則f(n) = O(g(n))。（呵呵，不要說沒 
學(xué)好數(shù)學(xué)呀，對(duì)于編程數(shù)學(xué)是非常重要的！！！） 

現(xiàn)在我們來看1/2*(n-1)*n，當(dāng)K=1/2，n0=1，g(n)=n*n時(shí)，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) 
=O(g(n))=O(n*n)。所以我們程序循環(huán)的復(fù)雜度為O(n*n)。 
再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實(shí)交換本身同數(shù)據(jù)源的 
有序程度有極大的關(guān)系，當(dāng)數(shù)據(jù)處于倒序的情況時(shí)，交換次數(shù)同循環(huán)一樣（每次循環(huán)判斷都會(huì)交換）， 
復(fù)雜度為O(n*n)。當(dāng)數(shù)據(jù)為正序，將不會(huì)有交換。復(fù)雜度為O(0)。亂序時(shí)處于中間狀態(tài)。正是由于這樣的 
原因，我們通常都是通過循環(huán)次數(shù)來對(duì)比算法。 


2.交換法： 
交換法的程序最清晰簡(jiǎn)單，每次用當(dāng)前的元素一一的同其后的元素比較并交換。 
#include <iostream.h> 
void ExchangeSort(int* pData,int Count) 
{ 
int iTemp; 
for(int i=0;i<Count-1;i++) 
{ 
for(int j=i+1;j<Count;j++) 
{ 
if(pData[j]<pData[i]) 
{ 
iTemp = pData[i]; 
pData[i] = pData[j]; 
pData[j] = iTemp; 
} 
} 
} 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4}; 
ExchangeSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 
倒序(最糟情況) 
第一輪：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次) 
第二輪：7,10,9,8->7,9,10,8->7,8,10,9(交換2次) 
第一輪：7,8,10,9->7,8,9,10(交換1次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：6次 

其他： 
第一輪：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交換1次) 
第二輪：7,10,8,9->7,8,10,9->7,8,10,9(交換1次) 
第一輪：7,8,10,9->7,8,9,10(交換1次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：3次 

從運(yùn)行的表格來看，交換幾乎和冒泡一樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡一樣 
也是1/2*(n-1)*n，所以算法的復(fù)雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以 
只能直接告訴大家他們?cè)诮粨Q上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。 

3.選擇法： 
現(xiàn)在我們終于可以看到一點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能（某些情況下） 
這種方法類似我們?nèi)藶榈呐判蛄?xí)慣：從數(shù)據(jù)中選擇最小的同第一個(gè)值交換，在從省下的部分中 
選擇最小的與第二個(gè)交換，這樣往復(fù)下去。 
#include <iostream.h> 
void SelectSort(int* pData,int Count) 
{ 
int iTemp; 
int iPos; 
for(int i=0;i<Count-1;i++) 
{ 
iTemp = pData[i]; 
iPos = i; 
for(int j=i+1;j<Count;j++) 
{ 
if(pData[j]<iTemp) 
{ 
iTemp = pData[j]; 
iPos = j; 
} 
} 
pData[iPos] = pData[i]; 
pData[i] = iTemp; 
} 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4}; 
SelectSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 
倒序(最糟情況) 
第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次) 
第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次) 
第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：2次 

其他： 
第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1次) 
第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次) 
第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：3次 
遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復(fù)雜度為O(n*n)。 
我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個(gè)最小值）。所以f(n)<=n 
所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時(shí)候，可以減少一定的交換次數(shù)。 


4.插入法： 
插入法較為復(fù)雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應(yīng)的位置插入，然后繼續(xù)下一張 
#include <iostream.h> 
void InsertSort(int* pData,int Count) 
{ 
int iTemp; 
int iPos; 
for(int i=1;i<Count;i++) 
{ 
iTemp = pData[i]; 
iPos = i-1; 
while((iPos>=0) && (iTemp<pData[iPos])) 
{ 
pData[iPos+1] = pData[iPos]; 
iPos--; 
} 
pData[iPos+1] = iTemp; 
} 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4}; 
InsertSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 

倒序(最糟情況) 
第一輪：10,9,8,7->9,10,8,7(交換1次)(循環(huán)1次) 
第二輪：9,10,8,7->8,9,10,7(交換1次)(循環(huán)2次) 
第一輪：8,9,10,7->7,8,9,10(交換1次)(循環(huán)3次) 
循環(huán)次數(shù)：6次 
交換次數(shù)：3次 

其他： 
第一輪：8,10,7,9->8,10,7,9(交換0次)(循環(huán)1次) 
第二輪：8,10,7,9->7,8,10,9(交換1次)(循環(huán)2次) 
第一輪：7,8,10,9->7,8,9,10(交換1次)(循環(huán)1次) 
循環(huán)次數(shù)：4次 
交換次數(shù)：2次 

上面結(jié)尾的行為分析事實(shí)上造成了一種假象，讓我們認(rèn)為這種算法是簡(jiǎn)單算法中最好的，其實(shí)不是， 
因?yàn)槠溲h(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結(jié)果可以看出，循環(huán)的次數(shù)f(n)<= 
1/2*n*(n-1)<=1/2*n*n。所以其復(fù)雜度仍為O(n*n)（這里說明一下，其實(shí)如果不是為了展示這些簡(jiǎn)單 
排序的不同，交換次數(shù)仍然可以這樣推導(dǎo)）。現(xiàn)在看交換，從外觀上看，交換次數(shù)是O(n)（推導(dǎo)類似 
選擇法），但我們每次要進(jìn)行與內(nèi)層循環(huán)相同次數(shù)的‘=’操作。正常的一次交換我們需要三次‘=’ 
而這里顯然多了一些，所以我們浪費(fèi)了時(shí)間。 

最終，我個(gè)人認(rèn)為，在簡(jiǎn)單排序算法中，選擇法是最好的。 


二、高級(jí)排序算法： 
高級(jí)排序算法中我們將只介紹這一種，同時(shí)也是目前我所知道（我看過的資料中）的最快的。 
它的工作看起來仍然象一個(gè)二叉樹。首先我們選擇一個(gè)中間值middle程序中我們使用數(shù)組中間值，然后 
把比它小的放在左邊，大的放在右邊（具體的實(shí)現(xiàn)是從兩邊找，找到一對(duì)后交換）。然后對(duì)兩邊分別使 
用這個(gè)過程（最容易的方法——遞歸）。 

1.快速排序： 
#include <iostream.h> 

void run(int* pData,int left,int right) 
{ 
int i,j; 
int middle,iTemp; 
i = left; 
j = right; 
middle = pData[(left+right)/2]; //求中間值 
do{ 
while((pData[i]<middle) && (i<right))//從左掃描大于中值的數(shù) 
i++; 
while((pData[j]>middle) && (j>left))//從右掃描大于中值的數(shù) 
j--; 
if(i<=j)//找到了一對(duì)值 
{ 
//交換 
iTemp = pData[i]; 
pData[i] = pData[j]; 
pData[j] = iTemp; 
i++; 
j--; 
} 
}while(i<=j);//如果兩邊掃描的下標(biāo)交錯(cuò)，就停止（完成一次）