作者：July、二零一一年三月二十日。
出處：http://blog.csdn.net/v_JULY_v。
--------------------------------------------------
前言：
相信，經過本人之前寫的前倆篇關於快速排序算法的文章：第一篇、一、快速排序算法，及第二篇、一之續、快速排序算法的深入分析，各位，已經對快速排序算法有了足夠的了解與認識。但僅僅停留在對一個算法的認識層次上，顯然是不夠的，即便你認識的有多透徹與深入。最好是，編程實現它。
而網上，快速排序的各種寫法層次不清，缺乏統一、整體的闡述與實現，即，沒有個一錘定音，如此，我便打算自己去實現它了。
於是，今花了一個上午，把快速排序算法的各種版本全部都寫程序一一實現了一下。包括網上有的，沒的，算法導論上的，國內教材上通用的，隨機化的，三數取中分割法的，遞歸的，非遞歸的，所有版本都用c/c++全部寫了個遍。
鑒於時間倉促下，一個人考慮問題總有不周之處，以及水平有限等等，不正之處，還望各位不吝賜教。不過，以下，所有全部c/c++源碼，都經本人一一調試，若有任何問題，懇請指正。
ok，本文主要分為以下幾部分內容：
第一部分、遞歸版
一、算法導論上的單向掃描版本
二、國內教材雙向掃描版
2.1、Hoare版本
2.2、Hoare的幾個變形版本
三、隨機化版本
四、三數取中分割法
第二部分、非遞歸版
好的，請一一細看。
第一部分、快速排序的遞歸版本
一、算法導論上的版本
在我寫的第二篇文章中，我們已經知道：
“再到後來，N.Lomuto又提出了一種新的版本，此版本....，即優化了PARTITION程序,它現在寫在了 算法導論 一書上”：
快速排序算法的關鍵是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
然後，對整個數組進行遞歸排序：
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r) //關鍵
3 QUICKSORT(A, p, q - 1)
4 QUICKSORT(A, q + 1, r)
根據上述偽代碼，我們不難寫出以下的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函數的編寫，是足夠簡單的：
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
然後是，調用partition，對整個數組進行遞歸排序：
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);
}
}
現在，我有一個問題要問各位了，保持其它的不變，稍微修改一下上述的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從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.
望讀者思考，後把結果在評論裡告知我。
我這裡簡單論述下：上述請讀者思考版本，只是代碼做了以下三處修改而已：1、j從 p->r；2、去掉最後的交換步驟；3、返回 i。首先，無論是我的版本，還是算法導論上的原裝版本，都是准確無誤的，且我都已經編寫程序測試通過了。但，其實這倆種寫法，思路是完全一致的。
為什麼這麼說列?請具體看以下的請讀者思考版本，
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，那麼當j指到hi時，是一定會有A[j]<=x的
{
i=i+1;
swap(&data[i],&data[j]);
}
}
//swap(&data[i+1],&data[hi]); //事實是，應該加上這句，直接交換，即可。
return i; //
}
我們知道當j最後指到了r之後，是一定會有A[j]<=x的（即=），所以這個if判斷就有點多余，沒有意義。所以應該如算法導論上的版本那般，最後直接交換swap(&data[i+1],&data[hi]); 即可，返回i+1。所以，總體說來，算法導論上的版本那樣寫，比請讀者思考版本更規范，更合乎情理。ok，請接著往下閱讀。
當然，上述partition過程中，也可以去掉swap函數的調用，直接寫在分割函數裡：
int partition(int data[],int lo,int hi)
{
int i,j,t;
int key = data[hi]; //還是以最後一個元素作為哨兵，即主元元素
