快速排序的本质是从数组中选一个参考值ref，比该参考值的大的，将其放在ref的右边，比ref小的放在左边，然后不断的对两边重复执行该动作
我们先列出来快速排序的步骤：
1.从数组中选一个参考值ref，比该参考值的大的，将其放在ref的右边，
上面的动作将数组划分为两部分:
A ref B
A是比ref小的数组元素集合，它仍然是数组，B是比ref大的元素集合，它也仍然是数组
2.在对ref左右两边的元素重复上述动作，直到A和B都只剩下一个元素，那么排序就算完成了。
重点是如何分别选出来两个集合A和B。算法导论里面把这个步骤叫做partition动作。
先把算法导论里面的伪代码贴出来，大家先看一下：
先看第一种ref的选择方法，即ref = a[r]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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的伪代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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++的代码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#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;} |
上面的代码我直接给出了快速排序的递归和非递归实现。
递归的实现方式很好理解，但是加入别人正在面试你快速排序算法的时候，多半会让你用非递归的方式实现给他看。下面我们就讨论一下。
先观察一下递归算法的运行过程，即每次都去对一段更小的范围去调用partition函数。所以我们需要知道每一次调用partition函数的start和end游标，同时，每一次partition调用都会产生新的start和end游标。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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;} |
这样的话，我们就可以用一个通用容器去存放每次调用partition生成的start和end游标。知道虽有的合法的start和end游标都作为参数调用了partition函数。所谓合法的start和end就是start < end。。。。。
关于递归算法的非递归实现，第一个想到的数据结构肯定是栈。其实别的数据结构，例如队列，也是可以实现。这里给出基于stl内的stack的实现方法。代码如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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);}}} |
上面代码的运行过程就是每次循环，从容器内拿一个start和end，如果是合法的，就依次将他们再次放入容易，知道这个容器为空未知。
给个运行实例吧，我在代码里面实现的是实现随机数排序，ref采用随机选取的方式。
原文链接：http://www.cnblogs.com/real-madrid/p/7203618.html
