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

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

前言：

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

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

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

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

    好的，請(qǐng)一一細(xì)看。

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

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

PARTITION(A, p, r)
1  x ← A[r]         //以最后一個(gè)元素，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

然后，對(duì)整個(gè)數(shù)組進(jìn)行遞歸排序：

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過(guò)程：

int partition(int data[],int lo,int hi)
{
 int key=data[hi];  //以最后一個(gè)元素，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;
}

補(bǔ)充說(shuō)明：舉個(gè)例子，如下為第一趟排序（更多詳盡的分析請(qǐng)參考第二篇文章）：
第一趟(4步)：
   a：3   8   7   1   2   5   6   4   //以最后一個(gè)元素，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ù)的編寫，是足夠簡(jiǎn)單的： 

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

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

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)在，我有一個(gè)問題要問各位了，保持其它的不變，稍微修改一下上述的partition過(guò)程，如下：

int partition(int data[],int lo,int hi)   //請(qǐng)讀者思考
{
 int key=data[hi];  //以最后一個(gè)元素，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.
}

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

PARTITION(A, p, r)   //請(qǐng)讀者思考版本。
1  x ← A[r]
2  i ← p - 1
3  for j ← p to r      //讓j 從p指向了最后一個(gè)元素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é)果在評(píng)論里告知我。

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

    為什么這么說(shuō)列?請(qǐng)具體看以下的請(qǐng)讀者思考版本，

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

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

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

int partition(int data[],int lo,int hi)
{
 int i,j,t;
 int key = data[hi];   //還是以最后一個(gè)元素作為哨兵，即主元元素
 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)換這倆條語(yǔ)句的順序。
  return i+1;
}

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

   ok，以上程序的測(cè)試用例，可以簡(jiǎn)單編寫如下：

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)然，如果，你如果對(duì)以上的測(cè)試用例不夠放心，可以采取1~10000的隨機(jī)數(shù)進(jìn)行極限測(cè)試，保證程序的萬(wàn)無(wú)一失（主函數(shù)中測(cè)試用的隨機(jī)數(shù)例子，即所謂的“極限”測(cè)試，下文會(huì)給出）。
    至于上述程序是什么結(jié)果，相信，不用我再啰嗦。:D。

補(bǔ)充一種寫法：

void quickSort(int p, int q)  
{  
 if(p < q)  
 {  
  int x = a[p];    //以第一個(gè)元素為主元
  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);  
 }  
}  

二、國(guó)內(nèi)教材雙向掃描版
    國(guó)內(nèi)教材上一般所用的通用版本，是我寫的第二篇文章中所提到的霍爾排序或其變形，而非上述所述的算法導(dǎo)論上的版本。而且，現(xiàn)在網(wǎng)上一般的朋友，也是更傾向于采用此種思路來(lái)實(shí)現(xiàn)快速排序算法。ok，請(qǐng)看：
          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之類的。
  }
 }
} //這個(gè)版本，已經(jīng)證明有誤，因?yàn)楫?dāng)data[l] == data[h] == key的時(shí)候，將會(huì)進(jìn)入死循環(huán)，所以淘汰。因此，使用上面的do-while 形式吧。

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

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

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

而第一個(gè)程序不存在這種情況，因?yàn)樗偸窃趌和h調(diào)整后比較，也就是l終究會(huì)大于等于h。

.

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

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

int partition(int data[],int lo,int hi)  //雙向掃描。
{
 int key=data[lo];   //以第一個(gè)元素為主元
 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)要賦值的情況，才事先保存好第一個(gè)元素的值。
 return l;     //這里和以下所有的Hoare的變形版本都是返回的是樞紐元素，即主元元素l。
}

補(bǔ)充說(shuō)明：同樣，還是舉上述那個(gè)例子，如下為第一趟排序（更多詳盡的分析請(qǐng)參考第二篇文章）：
第一趟(五步曲)：
   a：3   8   7   1   2   5   6   4   //以第一個(gè)元素為主元
        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   //最后補(bǔ)上，關(guān)鍵字3

然后，對(duì)整個(gè)數(shù)組進(jìn)行遞歸排序：

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)然，你也可以這么寫，把遞歸過(guò)程寫在同一個(gè)排序過(guò)程里：

void QuickSort(int data[],int lo,int hi)
{
   int i,j,temp;
   temp=data[lo];    //還是以第一個(gè)元素為主元。
   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);  //遞歸右邊
}

  或者，如下：

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

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

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

    ok，再給出一種取中間元素為主元的實(shí)現(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--;
  }
 }
}

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

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

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

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

//分割，換一種方式，采取指針a指向數(shù)組中第一個(gè)元素
int RandPartition(int* data, int lo , int hi)
{   
 //普通的分割方法和隨機(jī)化分割方法的區(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; //此就是上文說(shuō)所的“極限”測(cè)試。為了保證程序的準(zhǔn)確無(wú)誤，你也可以讓N=10000。
 int *data = new int[N];     
    for(int i =0; i<N; i++)
  data[i] = rand();   //同樣，隨機(jī)化的版本，采取隨機(jī)輸入。
    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)在想一個(gè)問題了，那就是，像上面的程序版本，其中算法導(dǎo)論上采取單向掃描中，是以最后一個(gè)元素為樞紐元素，即主元，而在Hoare版本及其幾個(gè)變形中，都是以第一個(gè)元素、或中間元素為主元，最后，上述給的快速排序算法的隨機(jī)化版本，則是以序列中任一一個(gè)元素作為主元。
    那么，樞紐元素的選取，即主元元素的選取是否決定快速排序最終的效率列?
   
    答案是肯定的，當(dāng)我們采取data[lo],data[mid],data[hi]三者之中的那個(gè)第二大的元素為主元時(shí)，便能盡最大限度保證快速排序算法不會(huì)出現(xiàn)O（N^2）的最壞情況。這就是所謂的三數(shù)取中分割方法。當(dāng)然，針對(duì)的還是那個(gè)Partition過(guò)程。

    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)過(guò)測(cè)試，這種方法可行且有效，不過(guò)到底其性能、效率有多好，還有待日后進(jìn)一步的測(cè)試。

第二部分、快速排序的非遞歸版
    ok，相信，您已經(jīng)看到，上述所有的快速排序算法，都是遞歸版本的，那還有什么辦法可以實(shí)現(xiàn)此快速排序算法列?對(duì)了，遞歸，與之相對(duì)的，就是非遞歸了。
    以下，就是快速排序算法的非遞歸實(shí)現(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ì)是什么?對(duì)了，就是借助棧，進(jìn)棧，出棧來(lái)實(shí)現(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);
    }
}

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

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

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

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