快速排序的本質是從數組中選一個參考值ref，比該參考值的大的，將其放在ref的右邊，比ref小的放在左邊，然后不斷的對兩邊重復執行該動作

我們先列出來快速排序的步驟：

1.從數組中選一個參考值ref，比該參考值的大的，將其放在ref的右邊，

上面的動作將數組劃分為兩部分:

A ref B

A是比ref小的數組元素集合，它仍然是數組，B是比ref大的元素集合，它也仍然是數組

2.在對ref左右兩邊的元素重復上述動作，直到A和B都只剩下一個元素，那么排序就算完成了。

重點是如何分別選出來兩個集合A和B。算法導論里面把這個步驟叫做partition動作。

先把算法導論里面的偽代碼貼出來，大家先看一下：

先看第一種ref的選擇方法，即ref = a[r]

partition(a[], p, r){i = pj = p-1ref = a[r]for(; i<r; i++){　　if(a[i]<ref){j++exchange(a[i], a[j])}}exchange(a[r], a[j+1])return j+1;}

首先找一個參考值，ref = a[r]，為了簡單起見，這里取最后一個作為參考值，實際上可以去任意一個值作為參考值。這個我們一會再說。

然后找定義兩個游標，分別是i 和j。i=p， j=p-1。為什么要這么定義呢？原因是我們既然選的是第一個，也就是a[p]，同時表示是從數組的第一個元素開始遍歷的。

選取j的目的是，我們要時刻知道當前最近一次比ref小的值的位置。由于我們選取的是a[r]，作為參考值，且從第一個元素開始遍歷，為了跟蹤最近一次比ref小的數的游標，暫時j=p-1。大家可以仔細體會一下這個做的意義。

觀察上述代碼可以看到，j總是記錄著最近一次比ref小的數的游標，因此最后return j+1，所有比ref小的數的游標均小于j+1，所有比ref大的數的游標均大于j+2。

總之我們執行partition的目的就是為了得到A，B，以及中間數的游標，這樣我們就可以分別對A和B重復執行上述動作。

接下來我們考慮另外兩種選取ref的方法。從上面選取最后一個值a[r]，作為參考值，并且在最后，將a[r]和a[j+1]交換的動作可以知道，我們總是希望知道我們選取參考值在partition過程中的位置，以便我們可以在最后一步，將a[refId] 和 a[j+1]的值交換。這里的refId表示選取ref值在a[]中的游標。

如果我們選取ref為最后一個值，那么在所有的partition過程中，這個值的位置是固定的。但是，假如我們選取的ref的refId是p到r范圍內的一個隨機數呢？

顯然，假如我們隨機選取ref的值，那么在partition過程中，refId對于的ref就有可能和其他值交換。這時候我們就需要更新ref對應的游標。

這樣一來，思路就很清晰了。

先給出partition的偽代碼：

partition(a[], p, r){refId = random(p,r)i = pj = p-1for(; i<=r; i++){if(a[i]<ref){j++ if(j == refId)//此時j剛好等refId，并且要和a[i]交換，則更新refId { refId = i }exchange(a[i], a[j])}}exchange(a[j+1], a[refId])return j+1}

從三種選擇ref的方法可以看到本質上都是一樣的，都為用一個游標j記錄最近一次遍歷到的比ref小的數據的游標，然后將ref和a[j+1]交換，返回j+1。

下面給出C++的代碼實現

#include <iostream>#include <stack>#include"stdlib.h"#include <time.h>using namespace std;template<class T>class SORT{public:static void myQsort(T a[], int p, int r);static void myQsortNoRecur(T a[], int p, int r);private:static int partition(T a[], int p, int r);static void exchange(T a[], int i, int j);};template<class T>void SORT<T>::exchange(T a[], int i, int j){T temp = a[i];a[i] = a[j];a[j] = temp;return;}template<class T>int SORT<T>::partition(T a[],int p,int r){int i = p;int j = p-1;T ref = a[p];int refId = p;srand((unsigned)time(NULL));refId = (rand() % (r-p+1))+ p;//cout<<refId<<endl;ref = a[refId];for(; i<=r; i++){if(a[i] < ref){j++;exchange(a, i, j);if(j == refId){refId = i;}}}exchange(a, j+1, refId);return j+1;}template<class T>void SORT<T>::myQsort(T a[],int p,int r){int q = 0;if(p<r){q = partition(a, p, r);myQsort(a, p, q-1);myQsort(a, p+1, r);}return;}template<class T>void SORT<T>::myQsortNoRecur(T a[], int p, int r){int start = p;int end = r;int mid = 0;std::stack<int> sortStk;sortStk.push(p);sortStk.push(r);while(!sortStk.empty()){end = sortStk.top();sortStk.pop();start = sortStk.top();sortStk.pop();if(start < end){mid = partition(a, start, end);sortStk.push(start);sortStk.push(mid -1);sortStk.push(mid + 1);sortStk.push(end);}}}int main(int argc, char** argv){int a[10];int b[10];srand((unsigned)time(NULL));for(int i=0; i<9; i++){a[i] = rand();}srand((unsigned)time(NULL));for(int i=0; i<9; i++){b[i] = rand();}SORT<int>::myQsort(a,0, 9);SORT<int>::myQsortNoRecur(b,0, 9);for(int i=0; i<10; i++){cout<<a[i]<<" ";}cout<<endl;for(int i=0; i<10; i++){cout<<b[i]<<" ";}return 0;}