十二之再續、快速排序算法所有版本的c/c++實(shí)現
作者：July、二零一一年三月二十日。
出處：http://blog.csdn.net/v_JULY_v。
--------------------------------------------------
前言：
相信，經(jīng)過(guò)本人之前寫(xiě)的前倆篇關(guān)于快速排序算法的文章：第一篇、一、快速排序算法，及第二篇、一之續、快速排序算法的深入分析，各位，已經(jīng)對快速排序算法有了足夠的了解與認識。但僅僅停留在對一個(gè)算法的認識層次上，顯然是不夠的，即便你認識的有多透徹與深入。最好是，編程實(shí)現它。
而網(wǎng)上，快速排序的各種寫(xiě)法層次不清，缺乏統一、整體的闡述與實(shí)現，即，沒(méi)有個(gè)一錘定音，如此，我便打算自己去實(shí)現它了。
于是，今花了一個(gè)上午，把快速排序算法的各種版本全部都寫(xiě)程序一一實(shí)現了一下。包括網(wǎng)上有的，沒(méi)的，算法導論上的，國內教材上通用的，隨機化的，三數取中分割法的，遞歸的，非遞歸的，所有版本都用c/c++全部寫(xiě)了個(gè)遍。
鑒于時(shí)間倉促下，一個(gè)人考慮問(wèn)題總有不周之處，以及水平有限等等，不正之處，還望各位不吝賜教。不過(guò)，以下，所有全部c/c++源碼，都經(jīng)本人一一調試，若有任何問(wèn)題，懇請指正。
ok，本文主要分為以下幾部分內容：
第一部分、遞歸版
一、算法導論上的單向掃描版本
二、國內教材雙向掃描版
2.1、Hoare版本
2.2、Hoare的幾個(gè)變形版本
三、隨機化版本
四、三數取中分割法
第二部分、非遞歸版
好的，請一一細看。
第一部分、快速排序的遞歸版本
一、算法導論上的版本
在我寫(xiě)的第二篇文章中，我們已經(jīng)知道：
“再到后來(lái)，N.Lomuto又提出了一種新的版本，此版本....，即優(yōu)化了PARTITION程序,它現在寫(xiě)在了 算法導論 一書(shū)上”：
快速排序算法的關(guān)鍵是PARTITION過(guò)程，它對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
然后，對整個(gè)數組進(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)
根據上述偽代碼，我們不難寫(xiě)出以下的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;
}
補充說(shuō)明：舉個(gè)例子，如下為第一趟排序（更多詳盡的分析請參考第二篇文章）：
第一趟(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函數的編寫(xiě)，是足夠簡(jiǎn)單的：
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
然后是，調用partition，對整個(gè)數組進(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);
}
}
現在，我有一個(gè)問(wèn)題要問(wèn)各位了，保持其它的不變，稍微修改一下上述的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從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.
}
如上，其它的不變，請問(wèn)，讓j掃描到了最后一個(gè)元素，后與data[i+1]交換，去掉最后的swap(&data[i+1],&data[hi])，然后，再返回i。請問(wèn)，如此，是否可行？
其實(shí)這個(gè)問(wèn)題，就是我第二篇文章中，所提到的：
“上述的PARTITION(A, p, r)版本，可不可以改成這樣咧?以下這樣列”：
PARTITION(A, p, r) //請讀者思考版本。
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ǎn)單論述下：上述請讀者思考版本，只是代碼做了以下三處修改而已：1、j從 p->r；2、去掉最后的交換步驟；3、返回 i。首先，無(wú)論是我的版本，還是算法導論上的原裝版本，都是準確無(wú)誤的，且我都已經(jīng)編寫(xiě)程序測試通過(guò)了。但，其實(shí)這倆種寫(xiě)法，思路是完全一致的。
為什么這么說(shuō)列?請具體看以下的請讀者思考版本，
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++) //....
{
if(data[j]<=key) //如果讓j從lo指向hi，那么當j指到hi時(shí)，是一定會(huì )有A[j]<=x的
{
i=i+1;
swap(&data[i],&data[j]);
}
}
//swap(&data[i+1],&data[hi]); //事實(shí)是，應該加上這句，直接交換，即可。
return i; //
}
我們知道當j最后指到了r之后，是一定會(huì )有A[j]<=x的（即=），所以這個(gè)if判斷就有點(diǎn)多余，沒(méi)有意義。所以應該如算法導論上的版本那般，最后直接交換swap(&data[i+1],&data[hi]); 即可，返回i+1。所以，總體說(shuō)來(lái)，算法導論上的版本那樣寫(xiě)，比請讀者思考版本更規范，更合乎情理。ok，請接著(zhù)往下閱讀。
當然，上述partition過(guò)程中，也可以去掉swap函數的調用，直接寫(xiě)在分割函數里：
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]
//不可調換這倆條語(yǔ)句的順序。
return i+1;
}
提醒：
1、程序中盡量不要有任何多余的代碼。
2、你最好絕對清楚的知道，程序的某一步，是該用if，還是該用while，等任何細節的東西。
ok，以上程序的測試用例，可以簡(jiǎn)單編寫(xiě)如下：
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;
}
當然，如果，你如果對以上的測試用例不夠放心，可以采取1~10000的隨機數進(jìn)行極限測試，保證程序的萬(wàn)無(wú)一失（主函數中測試用的隨機數例子，即所謂的“極限”測試，下文會(huì )給出）。
至于上述程序是什么結果，相信，不用我再啰嗦。:D。
補充一種寫(xiě)法：
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);
}
}
二、國內教材雙向掃描版
國內教材上一般所用的通用版本，是我寫(xiě)的第二篇文章中所提到的霍爾排序或其變形，而非上述所述的算法導論上的版本。而且，現在網(wǎng)上一般的朋友，也是更傾向于采用此種思路來(lái)實(shí)現快速排序算法。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
同樣，根據以上偽代碼，不難寫(xiě)出以下的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。不是返回各位習以為常的樞紐元素，即不是l之類(lèi)的。
}
}
} //這個(gè)版本，已經(jīng)證明有誤，因為當data[l] == data[h] == key的時(shí)候，將會(huì )進(jìn)入死循環(huán)，所以淘汰。因此，使用上面的do-while 形式吧。
讀者可以試下，對這個(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數組有相同元素就可能陷入死循環(huán)，比如：
2 3 4 5 6 2
l->| |<-h
交換l和h單元后重新又回到：
2 3 4 5 6 2
l->| |<-h
而第一個(gè)程序不存在這種情況，因為它總是在l和h調整后比較，也就是l終究會(huì )大于等于h。
.
相信，你已經(jīng)看出來(lái)了，上述的第一個(gè)程序中partition過(guò)程的返回值h并不是樞紐元的位置，但是仍然保證了A[p..j] <= A[j+1...q]。
這種方法在效率上與以下將要介紹的Hoare的幾個(gè)變形版本差別甚微，只不過(guò)是上述代碼相對更為緊湊點(diǎn)而已。
2.2、Hoare的幾個(gè)變形版本
ok，可能，你對上述的最初的霍爾排序partition過(guò)程，理解比較費力，沒(méi)關(guān)系，我再寫(xiě)幾種變形，相信，你立馬就能了解此雙向掃描是怎么一回事了。
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。只有出現要賦值的情況，才事先保存好第一個(gè)元素的值。
return l; //這里和以下所有的Hoare的變形版本都是返回的是樞紐元素，即主元元素l。
}
補充說(shuō)明：同樣，還是舉上述那個(gè)例子，如下為第一趟排序（更多詳盡的分析請參考第二篇文章）：
第一趟(五步曲)：
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 //最后補上，關(guān)鍵字3
然后，對整個(gè)數組進(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ě)，把遞歸過(guò)程寫(xiě)在同一個(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); //遞歸右邊
}
或者，如下：
另，本人在一本國內的數據結構教材上（注，此處非指嚴那本），看到的一種寫(xiě)法，發(fā)現如下問(wèn)題：一、冗余繁雜，二、錯誤之處無(wú)所不在，除了會(huì )犯一些注釋上的錯誤，一些最基本的代碼，都會(huì )弄錯。詳情，如下：
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];”，有誤。
//因為只能用一個(gè)臨時(shí)變量key保存著(zhù)主元，data[lo]，而若為以上，則相當于覆蓋原元素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)測試：原教材上，原句為“data[i]=data[0];”，有誤。
QuickSort(data,lo,i-1); //對標準值左半部遞歸調用本函數
QuickSort(data,i+1,hi); //對標準值右半部遞歸調用本函數
}
}
然后，你能很輕易的看到，這個(gè)寫(xiě)法，與上是同一寫(xiě)法，之所以寫(xiě)出來(lái)，是希望各位慎看國內的教材，多多質(zhì)疑+思考，勿輕信。
ok，再給出一種取中間元素為主元的實(shí)現：
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);
}
或者，這樣寫(xiě)：
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ò)程，如下圖所示（取中間元素為主元，第一趟排序）：
三、快速排序的隨機化版本
以下是完整測試程序，由于給的注釋夠詳盡了，就再做多余的解釋了：
//交換兩個(gè)元素值，咱們換一種方式，采取引用“&”
void swap(int& a , int& b)
{
int temp = a;
a = b;
b = temp;
}
//返回屬于[lo,hi)的隨機整數
int rand(int lo,int hi)
{
int size = hi-lo+1;
return lo+ rand()%size;
}
//分割，換一種方式，采取指針a指向數組中第一個(gè)元素
int RandPartition(int* data, int lo , int hi)
{
//普通的分割方法和隨機化分割方法的區別就在于下面三行
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ō)所的“極限”測試。為了保證程序的準確無(wú)誤，你也可以讓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;
}
四、三數取中分割法
我想，如果你愛(ài)思考，可能你已經(jīng)在想一個(gè)問(wèn)題了，那就是，像上面的程序版本，其中算法導論上采取單向掃描中，是以最后一個(gè)元素為樞紐元素，即主元，而在Hoare版本及其幾個(gè)變形中，都是以第一個(gè)元素、或中間元素為主元，最后，上述給的快速排序算法的隨機化版本，則是以序列中任一一個(gè)元素作為主元。
那么，樞紐元素的選取，即主元元素的選取是否決定快速排序最終的效率列?
答案是肯定的，當我們采取data[lo],data[mid],data[hi]三者之中的那個(gè)第二大的元素為主元時(shí)，便能盡最大限度保證快速排序算法不會(huì )出現O（N^2）的最壞情況。這就是所謂的三數取中分割方法。當然，針對的還是那個(gè)Partition過(guò)程。
ok，直接寫(xiě)代碼：
//三數取中分割方法
int RandPartition(int* a, int p , int q)
{
//三數取中方法的關(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ò)測試，這種方法可行且有效，不過(guò)到底其性能、效率有多好，還有待日后進(jìn)一步的測試。
第二部分、快速排序的非遞歸版
ok，相信，您已經(jīng)看到，上述所有的快速排序算法，都是遞歸版本的，那還有什么辦法可以實(shí)現此快速排序算法列?對了，遞歸，與之相對的，就是非遞歸了。
以下，就是快速排序算法的非遞歸實(shí)現：
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ì)是什么?對了，就是借助棧，進(jìn)棧，出棧來(lái)實(shí)現的。
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);
}
}
如果你還尚不知道快速排序算法的原理與算法思想，請參考本人寫(xiě)的關(guān)于快速排序算法的前倆篇文章：一之續、快速排序算法的深入分析，及一、快速排序算法。如果您看完了此篇文章后，還是不知如何從頭實(shí)現快速排序算法，那么好吧，伸出手指，數數，1,2,3,4,5....數到100之后，再來(lái)看此文。
-------------------------------------------------------------
據本文評論里頭網(wǎng)友ybt631的建議，表示非常感謝，并補充闡述下所謂的并行快速排序：
Intel Threading Building Blocks(簡(jiǎn)稱(chēng)TBB)是一個(gè)C++的并行編程模板庫，它能使你的程序充分利用多核CPU的性能優(yōu)勢，方便使用，效率很高。
以下是，parallel_sort.h頭文件中的關(guān)鍵代碼：
再貼一下插入排序、快速排序之其中的倆種版本、及插入排序與快速排序結合運用的實(shí)現代碼，如下：
聯(lián)系客服
