十二之再續(xù)、快速排序算法所有版本的c/c++實現(xiàn)

作者：July、二零一一年三月二十日。
出處：http://blog.csdn.net/v_JULY_v。
--------------------------------------------------

前言：

    相信，經(jīng)過本人之前寫的前倆篇關(guān)于快速排序算法的文章：第一篇、一、快速排序算法，及第二篇、一之續(xù)、快速排序算法的深入分析，各位，已經(jīng)對快速排序算法有了足夠的了解與認識。但僅僅停留在對一個算法的認識層次上，顯然是不夠的，即便你認識的有多透徹與深入。最好是，編程實現(xiàn)它。
    而網(wǎng)上，快速排序的各種寫法層次不清，缺乏統(tǒng)一、整體的闡述與實現(xiàn)，即，沒有個一錘定音，如此，我便打算自己去實現(xiàn)它了。

    于是，今花了一個上午，把快速排序算法的各種版本全部都寫程序一一實現(xiàn)了一下。包括網(wǎng)上有的，沒的，算法導(dǎo)論上的，國內(nèi)教材上通用的，隨機化的，三數(shù)取中分割法的，遞歸的，非遞歸的，所有版本都用c/c++全部寫了個遍。
    鑒于時間倉促下，一個人考慮問題總有不周之處，以及水平有限等等，不正之處，還望各位不吝賜教。不過，以下，所有全部c/c++源碼，都經(jīng)本人一一調(diào)試，若有任何問題，懇請指正。

    ok，本文主要分為以下幾部分內(nèi)容：

第一部分、遞歸版
一、算法導(dǎo)論上的單向掃描版本
二、國內(nèi)教材雙向掃描版
      2.1、Hoare版本
      2.2、Hoare的幾個變形版本
三、隨機化版本
四、三數(shù)取中分割法
第二部分、非遞歸版

    好的，請一一細看。

第一部分、快速排序的遞歸版本
一、算法導(dǎo)論上的版本
在我寫的第二篇文章中，我們已經(jīng)知道：
“再到后來，N.Lomuto又提出了一種新的版本，此版本....，即優(yōu)化了PARTITION程序,它現(xiàn)在寫在了 算法導(dǎo)論 一書上”：

快速排序算法的關(guān)鍵是PARTITION過程，它對A[p..r]進行就地重排：

PARTITION(A, p, r)
1  x ← A[r]         //以最后一個元素，A[r]為主元
2  i ← p - 1
3  for j ← p to r - 1    //注，j從p指向的是r-1，不是r。
4       do if A[j] ≤ x
5             then i ← i + 1
6                  exchange A[i] <-> A[j]
7  exchange A[i + 1] <-> A[r]    //最后，交換主元
8  return i + 1

然后，對整個數(shù)組進行遞歸排序：

QUICKSORT(A, p, r)
1 if p < r
2    then q ← PARTITION(A, p, r)   //關(guān)鍵
3         QUICKSORT(A, p, q - 1)
4         QUICKSORT(A, q + 1, r)

    根據(jù)上述偽代碼，我們不難寫出以下的c/c++程序：
首先是，PARTITION過程：

int partition(int data[],int lo,int hi)
{
 int key=data[hi];  //以最后一個元素，data[hi]為主元
 int i=lo-1;
 for(int j=lo;j<hi;j++)   ///注，j從p指向的是r-1，不是r。
 {
  if(data[j]<=key)
  {
   i=i+1;
   swap(&data[i],&data[j]);
  }
 }
 swap(&data[i+1],&data[hi]);   //不能改為swap(&data[i+1],&key)
 return i+1;
}

補充說明：舉個例子，如下為第一趟排序（更多詳盡的分析請參考第二篇文章）：
第一趟(4步)：
   a：3   8   7   1   2   5   6   4   //以最后一個元素，data[hi]為主元

   b：3   1   7   8   2   5   6   4

   c：3   1   2   8   7   5   6   4

   d：3   1   2   4   7   5   6   8    //最后，swap(&data[i+1],&data[hi])

  而其中swap函數(shù)的編寫，是足夠簡單的： 

void swap(int *a,int *b)
{
 int temp=*a;
 *a=*b;
 *b=temp;
}

    然后是，調(diào)用partition，對整個數(shù)組進行遞歸排序：

void QuickSort(int data[], int lo, int hi)
{
    if (lo<hi)
    {
        int k = partition(data, lo, hi);
        QuickSort(data, lo, k-1);
        QuickSort(data, k+1, hi);
    }
} 

     現(xiàn)在，我有一個問題要問各位了，保持其它的不變，稍微修改一下上述的partition過程，如下：

int partition(int data[],int lo,int hi)   //請讀者思考
{
 int key=data[hi];  //以最后一個元素，data[hi]為主元
 int i=lo-1;
 for(int j=lo;j<=hi;j++)   //現(xiàn)在，我讓j從lo指向了hi，不是hi-1。
 {
  if(data[j]<=key)
  {
   i=i+1;
   swap(&data[i],&data[j]);
  }
 }
 //swap(&data[i+1],&data[hi]);   //去掉這行
 return i;                       //返回i，非i+1.
}

    如上，其它的不變，請問，讓j掃描到了最后一個元素，后與data[i+1]交換，去掉最后的swap(&data[i+1],&data[hi])，然后，再返回i。請問，如此，是否可行？
    其實這個問題，就是我第二篇文章中，所提到的：
    “上述的PARTITION(A, p, r)版本，可不可以改成這樣咧?以下這樣列”：

PARTITION(A, p, r)   //請讀者思考版本。
1  x ← A[r]
2  i ← p - 1
3  for j ← p to r      //讓j 從p指向了最后一個元素r
4       do if A[j] ≤ x
5             then i ← i + 1
6                  exchange A[i] <-> A[j]
//7  exchange A[i + 1] <-> A[r]   去掉此最后的步驟
8  return i      //返回 i，不再返回 i+1.

    望讀者思考，后把結(jié)果在評論里告知我。

    我這里簡單論述下：上述請讀者思考版本，只是代碼做了以下三處修改而已：1、j從 p->r；2、去掉最后的交換步驟；3、返回 i。首先，無論是我的版本，還是算法導(dǎo)論上的原裝版本，都是準(zhǔn)確無誤的，且我都已經(jīng)編寫程序測試通過了。但，其實這倆種寫法，思路是完全一致的。

    為什么這么說列?請具體看以下的請讀者思考版本，

int partition(int data[],int lo,int hi)   //請讀者思考
{
 int key=data[hi];  //以最后一個元素，data[hi]為主元
 int i=lo-1;
 for(int j=lo;j<=hi;j++)   //....
 {
  if(data[j]<=key)           //如果讓j從lo指向hi，那么當(dāng)j指到hi時，是一定會有A[j]<=x的
  {
   i=i+1;
   swap(&data[i],&data[j]);
  }
 }
 //swap(&data[i+1],&data[hi]);   //事實是，應(yīng)該加上這句，直接交換，即可。
 return i;                       //
}

    我們知道當(dāng)j最后指到了r之后，是一定會有A[j]<=x的（即=），所以這個if判斷就有點多余，沒有意義。所以應(yīng)該如算法導(dǎo)論上的版本那般，最后直接交換swap(&data[i+1],&data[hi]);   即可，返回i+1。所以，總體說來，算法導(dǎo)論上的版本那樣寫，比請讀者思考版本更規(guī)范，更合乎情理。ok，請接著往下閱讀。

    當(dāng)然，上述partition過程中，也可以去掉swap函數(shù)的調(diào)用，直接寫在分割函數(shù)里：

int partition(int data[],int lo,int hi)
{
 int i,j,t;
 int key = data[hi];   //還是以最后一個元素作為哨兵，即主元元素
 i = lo-1;
 for (j =lo;j<=hi;j++)
  if(data[j]<key)
  {
   i++;
   t = data[j];
   data[j] = data[i];
   data[i] = t;
  }
  data[hi] = data[i+1];  //先,data[i+1]賦給data[hi]
  data[i+1] = key;       //后，把事先保存的key值，即data[hi]賦給data[i+1]
  //不可調(diào)換這倆條語句的順序。
  return i+1;
}

提醒：
1、程序中盡量不要有任何多余的代碼。
2、你最好絕對清楚的知道，程序的某一步，是該用if，還是該用while，等任何細節(jié)的東西。

   ok，以上程序的測試用例，可以簡單編寫如下：

int main()
{
 int a[8]={3,8,7,1,2,5,6,4};
 QuickSort(a,0,N-1);
 for(int i=0;i<8;i++)
  cout<<a[i]<<endl;
 return 0;
}

    當(dāng)然，如果，你如果對以上的測試用例不夠放心，可以采取1~10000的隨機數(shù)進行極限測試，保證程序的萬無一失（主函數(shù)中測試用的隨機數(shù)例子，即所謂的“極限”測試，下文會給出）。
    至于上述程序是什么結(jié)果，相信，不用我再啰嗦。:D。

補充一種寫法：

void quickSort(int p, int q)  
{  
 if(p < q)  
 {  
  int x = a[p];    //以第一個元素為主元
  int i = p;  
  for(int j = p+1; j < q; j++)  
  {  
   if(a[j] < x)  
   {  
    i++;  
    int temp = a[i];  
    a[i] = a[j];   
    a[j] = temp;  
   }  
  }  
  int temp = a[p];  
  a[p] = a[i];  
  a[i] = temp;  
  quickSort(p, i);  
  quickSort(i+1, q);  
 }  
}  

二、國內(nèi)教材雙向掃描版
    國內(nèi)教材上一般所用的通用版本，是我寫的第二篇文章中所提到的霍爾排序或其變形，而非上述所述的算法導(dǎo)論上的版本。而且，現(xiàn)在網(wǎng)上一般的朋友，也是更傾向于采用此種思路來實現(xiàn)快速排序算法。ok，請看：
          2.1、Hoare版本
    那么，什么是霍爾提出的快速排序版本列?如下，即是：

HOARE-PARTITION(A, p, r)
 1  x ← A[p]
 2  i ← p - 1
 3  j ← r + 1
 4  while TRUE
 5      do repeat j ← j - 1
 6           until A[j] ≤ x
 7         repeat i ← i + 1
 8           until A[i] ≥ x
 9         if i < j
10            then exchange A[i] <-> A[j]
11            else return j

     同樣，根據(jù)以上偽代碼，不難寫出以下的c/c++代碼：

int partition(int data[],int lo,int hi)  //。
{
 int key=data[lo];
 int l=lo;
 int h=hi;
 for(;;)
 {
  while(data[h]>key)   //不能加 “=”
   h--;
  while(data[l]<key)    //不能加 “=”
   l++;
  if(l<h)
  {
   swap(data[l],data[h]);
  }
  else
  {
   return h;   //各位注意了，這里的返回值是h。不是返回各位習(xí)以為常的樞紐元素，即不是l之類的。
  }
 }
} //這個版本，已經(jīng)證明有誤，因為當(dāng)data[l] == data[h] == key的時候，將會進入死循環(huán)，所以淘汰。因此，使用上面的do-while 形式吧。

    讀者可以試下，對這個序列進行排序，用上述淘汰版本將立馬進入死循環(huán)：int data[16]={ 1000, 0, 6, 5, 4, 3, 2, 1, 7, 156, 44, 23, 123, 11, 5 };。

或者，如朋友顏沙所說：
如果data數(shù)組有相同元素就可能陷入死循環(huán)，比如：
      2 3 4 5 6 2 
  l->|             |<-h

交換l和h單元后重新又回到：
      2 3 4 5 6 2 
  l->|             |<-h

而第一個程序不存在這種情況，因為它總是在l和h調(diào)整后比較，也就是l終究會大于等于h。

.

    相信，你已經(jīng)看出來了，上述的第一個程序中partition過程的返回值h并不是樞紐元的位置，但是仍然保證了A[p..j] <= A[j+1...q]。
    這種方法在效率上與以下將要介紹的Hoare的幾個變形版本差別甚微，只不過是上述代碼相對更為緊湊點而已。

       2.2、Hoare的幾個變形版本
    ok，可能，你對上述的最初的霍爾排序partition過程，理解比較費力，沒關(guān)系，我再寫幾種變形，相信，你立馬就能了解此雙向掃描是怎么一回事了。

int partition(int data[],int lo,int hi)  //雙向掃描。
{
 int key=data[lo];   //以第一個元素為主元
 int l=lo;
 int h=hi;
 while(l<h)
 {
  while(key<=data[h] && l<h)
   h--;
  data[l]=data[h];
  while(data[l]<=key && l<h)
   l++;
  data[h]=data[l];
 }
 data[l]=key;  //1.key。只有出現(xiàn)要賦值的情況，才事先保存好第一個元素的值。
 return l;     //這里和以下所有的Hoare的變形版本都是返回的是樞紐元素，即主元元素l。
}

補充說明：同樣，還是舉上述那個例子，如下為第一趟排序（更多詳盡的分析請參考第二篇文章）：
第一趟(五步曲)：
   a：3   8   7   1   2   5   6   4   //以第一個元素為主元
        2   8   7   1       5   6   4
   b：2       7   1   8   5   6   4
   c：2   1   7       8   5   6   4
   d：2   1       7   8   5   6   4
   e：2   1   3   7   8   5   6   4   //最后補上，關(guān)鍵字3

然后，對整個數(shù)組進行遞歸排序：

void QuickSort(int data[], int lo, int hi)
{
    if (lo<hi)
    {
        int k = partition(data, lo, hi);
        QuickSort(data, lo, k-1);
        QuickSort(data, k+1, hi);
    }
}

當(dāng)然，你也可以這么寫，把遞歸過程寫在同一個排序過程里：

void QuickSort(int data[],int lo,int hi)
{
   int i,j,temp;
   temp=data[lo];    //還是以第一個元素為主元。
   i=lo;
   j=hi;
   if(lo>hi)
      return;
   while(i!=j)
   {
      while(data[j]>=temp && j>i)
         j--;
      if(j>i)
         data[i++]=data[j];
      while(data[i]<=temp && j>i)
         i++;
      if(j>i)
   data[j--]=data[i];    
   }
   data[i]=temp;                       //2.temp。同上，返回的是樞紐元素，即主元元素。
   QuickSort(data,lo,i-1);  //遞歸左邊
   QuickSort(data,i+1,hi);  //遞歸右邊
}

  或者，如下：

另，本人在一本國內(nèi)的數(shù)據(jù)結(jié)構(gòu)教材上（注，此處非指嚴那本），看到的一種寫法，發(fā)現(xiàn)如下問題：一、冗余繁雜，二、錯誤之處無所不在，除了會犯一些注釋上的錯誤，一些最基本的代碼，都會弄錯。詳情，如下：

void QuickSort(int data[],int lo,int hi)
{
 int i,j,key;
 if(lo<hi)
 {
  i=lo;
  j=hi;
  key=data[lo];
  //已經(jīng)測試：原教材上，原句為“data[0]=data[lo];”，有誤。
  //因為只能用一個臨時變量key保存著主元，data[lo]，而若為以上，則相當(dāng)于覆蓋原元素data[0]的值了。
        do
        {
   while(data[j]>=key&&i<j)
    j--;       
   if(i<j)                            
   {
    data[i]=data[j];
    //i++;  這是教材上的語句，為使代碼簡潔，我特意去掉。
   }          
   while(data[i]<=key&&i<j)
    i++;    
   if(i<j)                      
   {
    data[j]=data[i];
    //j--;    這是教材上的語句，為使代碼簡潔，我特意去掉。
   }             
        }while(i!=j);
        data[i]=key;        //3.key。
  //已經(jīng)測試：原教材上，原句為“data[i]=data[0];”，有誤。
        QuickSort(data,lo,i-1);     //對標(biāo)準(zhǔn)值左半部遞歸調(diào)用本函數(shù)
        QuickSort(data,i+1,hi);    //對標(biāo)準(zhǔn)值右半部遞歸調(diào)用本函數(shù)
 }
}

    然后，你能很輕易的看到，這個寫法，與上是同一寫法，之所以寫出來，是希望各位慎看國內(nèi)的教材，多多質(zhì)疑+思考，勿輕信。

    ok，再給出一種取中間元素為主元的實現(xiàn)：

void QuickSort(int data[],int lo,int hi)
{
 int pivot,l,r,temp;
 l = lo;
 r = hi;
 pivot=data[(lo+hi)/2]; //取中位值作為分界值
 while(l<r) 
 { 
  while(data[l]<pivot)
   ++l; 
  while(data[r]>pivot)
   --r;    
  if(l>=r)
   break; 
  temp = data[l]; 
  data[l] = data[r]; 
  data[r] = temp; 
  ++l; 
  --r; 
 }
 if(l==r)
  l++;
 if(lo<r)
  QuickSort(data,lo,l-1);
 if(l<hi)
  QuickSort(data,r+1,hi);
}

或者，這樣寫：

 void quickSort(int arr[], int left, int right)
{
 int i = left, j = right;
 int tmp;
 int pivot = arr[(left + right) / 2];   //取中間元素為主元
 
 /* partition */
 while (i <= j)
 {
  while (arr[i] < pivot)
   i++;
  while (arr[j] > pivot)
   j--;
  if (i <= j)
  {
   tmp = arr[i];
   arr[i] = arr[j];
   arr[j] = tmp;
   i++;
   j--;
  }
 }
}

上述演示過程，如下圖所示（取中間元素為主元，第一趟排序）：

三、快速排序的隨機化版本
    以下是完整測試程序，由于給的注釋夠詳盡了，就再做多余的解釋了：

//交換兩個元素值，咱們換一種方式，采取引用“&”
void swap(int& a , int& b)
{
 int temp = a;
 a = b;
 b = temp;
}

//返回屬于[lo,hi)的隨機整數(shù)
int rand(int lo,int hi)
{
 int size = hi-lo+1;
 return  lo+ rand()%size;
}

//分割，換一種方式，采取指針a指向數(shù)組中第一個元素
int RandPartition(int* data, int lo , int hi)
{   
 //普通的分割方法和隨機化分割方法的區(qū)別就在于下面三行
 swap(data[rand(lo,hi)], data[lo]);
    int key = data[lo];
 int i = lo;
 
    for(int j=lo+1; j<=hi; j++)
 {
  if(data[j]<=key)
  {
   i = i+1;
   swap(data[i], data[j]);
  }           
 } 
 swap(data[i],data[lo]);
 return i;
}

//逐步分割排序
void RandQuickSortMid(int* data, int lo, int hi)
{
 if(lo<hi)
 {
  int k = RandPartition(data,lo,hi);
  RandQuickSortMid(data,lo,k-1);
  RandQuickSortMid(data,k+1,hi);
 }
}
int main()
{
 const int N = 100; //此就是上文說所的“極限”測試。為了保證程序的準(zhǔn)確無誤，你也可以讓N=10000。
 int *data = new int[N];     
    for(int i =0; i<N; i++)
  data[i] = rand();   //同樣，隨機化的版本，采取隨機輸入。
    for(i=0; i<N; i++)
  cout<<data[i]<<" ";
    RandQuickSortMid(data,0,N-1);
 cout<<endl;
 for(i=0; i<N; i++)
  cout<<data[i]<<" ";
 cout<<endl;
    return 0;
}

 
四、三數(shù)取中分割法

    我想，如果你愛思考，可能你已經(jīng)在想一個問題了，那就是，像上面的程序版本，其中算法導(dǎo)論上采取單向掃描中，是以最后一個元素為樞紐元素，即主元，而在Hoare版本及其幾個變形中，都是以第一個元素、或中間元素為主元，最后，上述給的快速排序算法的隨機化版本，則是以序列中任一一個元素作為主元。
    那么，樞紐元素的選取，即主元元素的選取是否決定快速排序最終的效率列?
   
    答案是肯定的，當(dāng)我們采取data[lo],data[mid],data[hi]三者之中的那個第二大的元素為主元時，便能盡最大限度保證快速排序算法不會出現(xiàn)O（N^2）的最壞情況。這就是所謂的三數(shù)取中分割方法。當(dāng)然，針對的還是那個Partition過程。

    ok，直接寫代碼：

//三數(shù)取中分割方法
int RandPartition(int* a, int p , int q)
{   
 //三數(shù)取中方法的關(guān)鍵就在于下述六行，
 int m=(p+q)/2;
 if(a[p]<a[m])
  swap(a[p],a[m]);
 if(a[q]<a[m])
  swap(a[q],a[m]);
 if(a[q]<a[p])
  swap(a[q],a[p]);
 int key = a[p];
 int i = p;
 
 for(int j = p+1; j <= q; j++)
 {
  if(a[j] <= key)
  {
   i = i+1;
   if(i != j)
    swap(a[i], a[j]);                
  }           
 }
 
 swap(a[i],a[p]);  
 return i;
}

void QuickSort(int data[], int lo, int hi)
{
    if (lo<hi)
    {
        int k = RandPartition(data, lo, hi);
        QuickSort(data, lo, k-1);
        QuickSort(data, k+1, hi);
    }
}

    經(jīng)過測試，這種方法可行且有效，不過到底其性能、效率有多好，還有待日后進一步的測試。

第二部分、快速排序的非遞歸版
    ok，相信，您已經(jīng)看到，上述所有的快速排序算法，都是遞歸版本的，那還有什么辦法可以實現(xiàn)此快速排序算法列?對了，遞歸，與之相對的，就是非遞歸了。
    以下，就是快速排序算法的非遞歸實現(xiàn)：

  template <class T>
int RandPartition(T data[],int lo,int hi)
{
 T v=data[lo];
 while(lo<hi)
 { 
  while(lo<hi && data[hi]>=v)
   hi--;
  data[lo]=data[hi];
  while(lo<hi && data[lo]<=v)
   lo++;
  data[hi]=data[lo];
 }
 data[lo]=v;
 return lo;
}

//快速排序的非遞歸算法
template <class T>
void QuickSort(T data[],int lo,int hi)
{
 stack<int> st;
 int key;
 do{
  while(lo<hi)
  {
   key=partition(data,lo,hi);  
   //遞歸的本質(zhì)是什么?對了，就是借助棧，進棧，出棧來實現(xiàn)的。
   if( (key-lo)<(key-key) )
   {
    st.push(key+1);   
    st.push(hi);
    hi=key-1;
   }
   else
   {
    st.push(lo);
    st.push(key-1);
    lo=key+1;
   }  
  }
  if(st.empty())
   return;
  hi=st.top();
  st.pop(); 
  lo=st.top();
  st.pop(); 
 }while(1);
}

void QuickSort(int data[], int lo, int hi)
{
    if (lo<hi)
    {
        int k = RandPartition(data, lo, hi);
        QuickSort(data, lo, k-1);
        QuickSort(data, k+1, hi);
    }
}

    如果你還尚不知道快速排序算法的原理與算法思想，請參考本人寫的關(guān)于快速排序算法的前倆篇文章：一之續(xù)、快速排序算法的深入分析，及一、快速排序算法。如果您看完了此篇文章后，還是不知如何從頭實現(xiàn)快速排序算法，那么好吧，伸出手指，數(shù)數(shù)，1,2,3,4,5....數(shù)到100之后，再來看此文。

    -------------------------------------------------------------
    據(jù)本文評論里頭網(wǎng)友ybt631的建議，表示非常感謝，并補充闡述下所謂的并行快速排序：

    Intel Threading Building Blocks(簡稱TBB)是一個C++的并行編程模板庫，它能使你的程序充分利用多核CPU的性能優(yōu)勢，方便使用，效率很高。
    以下是，parallel_sort.h頭文件中的關(guān)鍵代碼：

    再貼一下插入排序、快速排序之其中的倆種版本、及插入排序與快速排序結(jié)合運用的實現(xiàn)代碼，如下：