文章標題：各種排序算法
原 作 者：xulion
原 出 處：不詳
發 布 者：loose_went
發布類型：轉載
發布日期：2004-05-17
今日瀏覽：6
總 瀏 覽：523
  

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

  對于排序的算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。 
  我將按照算法的復雜度，從簡單到難來分析算法。 
  第一部分是簡單排序算法，后面你將看到他們的共同點是算法復雜度為O(N*N)（因為沒有 
使用word,所以無法打出上標和下標）。 
  第二部分是高級排序算法，復雜度為O(Log2(N))。這里我們只介紹一種算法。另外還有幾種 
算法因為涉及樹與堆的概念，所以這里不于討論。 
  第三部分類似動腦筋。這里的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較 
奇特，值得參考（編程的角度）。同時也可以讓我們從另外的角度來認識這個問題。 
  第四部分是我送給大家的一個餐后的甜點——一個基于模板的通用快速排序。由于是模板函數 
可以對任何數據類型排序（抱歉，里面使用了一些論壇專家的呢稱）。 
   
  現在，讓我們開始吧： 
   
一、簡單排序算法 
由于程序比較簡單，所以沒有加什么注釋。所有的程序都給出了完整的運行代碼，并在我的VC環境 
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平臺上應該也不會有什么 
問題的。在代碼的后面給出了運行過程示意，希望對理解有幫助。 

1.冒泡法： 
這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡： 
#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次) 
循環次數：6次 
交換次數：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次) 
循環次數：6次 
交換次數：3次 

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

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

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


2.交換法： 
交換法的程序最清晰簡單，每次用當前的元素一一的同其后的元素比較并交換。 
#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次) 
循環次數：6次 
交換次數：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次) 
循環次數：6次 
交換次數：3次 

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

3.選擇法： 
現在我們終于可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下） 
這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從省下的部分中 
選擇最小的與第二個交換，這樣往復下去。 
#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次) 
循環次數：6次 
交換次數：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次) 
循環次數：6次 
交換次數：3次 
遺憾的是算法需要的循環次數依然是1/2*(n-1)*n。所以算法復雜度為O(n*n)。 
我們來看他的交換。由于每次外層循環只產生一次交換（只有一個最小值）。所以f(n)<=n 
所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。 


4.插入法： 
插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然后繼續下一張 
#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次)(循環1次) 
第二輪：9,10,8,7->8,9,10,7(交換1次)(循環2次) 
第一輪：8,9,10,7->7,8,9,10(交換1次)(循環3次) 
循環次數：6次 
交換次數：3次 

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

上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中最好的，其實不是， 
因為其循環次數雖然并不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<= 
1/2*n*(n-1)<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單 
排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似 
選擇法），但我們每次要進行與內層循環相同次數的‘=’操作。正常的一次交換我們需要三次‘=’ 
而這里顯然多了一些，所以我們浪費了時間。 

最終，我個人認為，在簡單排序算法中，選擇法是最好的。 


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

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))//從左掃描大于中值的數 
      i++;      
    while((pData[j]>middle) && (j>left))//從右掃描大于中值的數 
      j--; 
    if(i<=j)//找到了一對值 
    { 
      //交換 
      iTemp = pData[i]; 
      pData[i] = pData[j]; 
      pData[j] = iTemp; 
      i++; 
      j--; 
    } 
  }while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次） 

  //當左邊部分有值(left<j)，遞歸左半邊