快速排序的本質(zhì)是從數(shù)組中選一個(gè)參考值ref，比該參考值的大的，將其放在ref的右邊，比ref小的放在左邊，然后不斷的對(duì)兩邊重復(fù)執(zhí)行該動(dòng)作
我們先列出來(lái)快速排序的步驟：
1.從數(shù)組中選一個(gè)參考值ref，比該參考值的大的，將其放在ref的右邊，
上面的動(dòng)作將數(shù)組劃分為兩部分:
A ref B
A是比ref小的數(shù)組元素集合，它仍然是數(shù)組，B是比ref大的元素集合，它也仍然是數(shù)組
2.在對(duì)ref左右兩邊的元素重復(fù)上述動(dòng)作，直到A和B都只剩下一個(gè)元素，那么排序就算完成了。
重點(diǎn)是如何分別選出來(lái)兩個(gè)集合A和B。算法導(dǎo)論里面把這個(gè)步驟叫做partition動(dòng)作。
先把算法導(dǎo)論里面的偽代碼貼出來(lái)，大家先看一下：
先看第一種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;} |
首先找一個(gè)參考值，ref = a[r]，為了簡(jiǎn)單起見(jiàn)，這里取最后一個(gè)作為參考值，實(shí)際上可以去任意一個(gè)值作為參考值。這個(gè)我們一會(huì)再說(shuō)。
然后找定義兩個(gè)游標(biāo)，分別是i 和j。i=p， j=p-1。為什么要這么定義呢？原因是我們既然選的是第一個(gè)，也就是a[p]，同時(shí)表示是從數(shù)組的第一個(gè)元素開(kāi)始遍歷的。
選取j的目的是，我們要時(shí)刻知道當(dāng)前最近一次比ref小的值的位置。由于我們選取的是a[r]，作為參考值，且從第一個(gè)元素開(kāi)始遍歷，為了跟蹤最近一次比ref小的數(shù)的游標(biāo)，暫時(shí)j=p-1。大家可以仔細(xì)體會(huì)一下這個(gè)做的意義。
觀(guān)察上述代碼可以看到，j總是記錄著最近一次比ref小的數(shù)的游標(biāo)，因此最后return j+1，所有比ref小的數(shù)的游標(biāo)均小于j+1，所有比ref大的數(shù)的游標(biāo)均大于j+2。
總之我們執(zhí)行partition的目的就是為了得到A，B，以及中間數(shù)的游標(biāo)，這樣我們就可以分別對(duì)A和B重復(fù)執(zhí)行上述動(dòng)作。
接下來(lái)我們考慮另外兩種選取ref的方法。從上面選取最后一個(gè)值a[r]，作為參考值，并且在最后，將a[r]和a[j+1]交換的動(dòng)作可以知道，我們總是希望知道我們選取參考值在partition過(guò)程中的位置，以便我們可以在最后一步，將a[refId] 和 a[j+1]的值交換。這里的refId表示選取ref值在a[]中的游標(biāo)。
如果我們選取ref為最后一個(gè)值，那么在所有的partition過(guò)程中，這個(gè)值的位置是固定的。但是，假如我們選取的ref的refId是p到r范圍內(nèi)的一個(gè)隨機(jī)數(shù)呢？
顯然，假如我們隨機(jī)選取ref的值，那么在partition過(guò)程中，refId對(duì)于的ref就有可能和其他值交換。這時(shí)候我們就需要更新ref對(duì)應(yīng)的游標(biāo)。
這樣一來(lái)，思路就很清晰了。
先給出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)//此時(shí)j剛好等refId，并且要和a[i]交換，則更新refId { refId = i }exchange(a[i], a[j])}}exchange(a[j+1], a[refId])return j+1} |
從三種選擇ref的方法可以看到本質(zhì)上都是一樣的，都為用一個(gè)游標(biāo)j記錄最近一次遍歷到的比ref小的數(shù)據(jù)的游標(biāo)，然后將ref和a[j+1]交換，返回j+1。
下面給出C++的代碼實(shí)現(xiàn)
|
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;} |
上面的代碼我直接給出了快速排序的遞歸和非遞歸實(shí)現(xiàn)。
遞歸的實(shí)現(xiàn)方式很好理解，但是加入別人正在面試你快速排序算法的時(shí)候，多半會(huì)讓你用非遞歸的方式實(shí)現(xiàn)給他看。下面我們就討論一下。
先觀(guān)察一下遞歸算法的運(yùn)行過(guò)程，即每次都去對(duì)一段更小的范圍去調(diào)用partition函數(shù)。所以我們需要知道每一次調(diào)用partition函數(shù)的start和end游標(biāo)，同時(shí)，每一次partition調(diào)用都會(huì)產(chǎn)生新的start和end游標(biāo)。
|
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;} |
這樣的話(huà)，我們就可以用一個(gè)通用容器去存放每次調(diào)用partition生成的start和end游標(biāo)。知道雖有的合法的start和end游標(biāo)都作為參數(shù)調(diào)用了partition函數(shù)。所謂合法的start和end就是start < end。。。。。
關(guān)于遞歸算法的非遞歸實(shí)現(xiàn)，第一個(gè)想到的數(shù)據(jù)結(jié)構(gòu)肯定是棧。其實(shí)別的數(shù)據(jù)結(jié)構(gòu)，例如隊(duì)列，也是可以實(shí)現(xiàn)。這里給出基于stl內(nèi)的stack的實(shí)現(xiàn)方法。代碼如下
|
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);}}} |
上面代碼的運(yùn)行過(guò)程就是每次循環(huán)，從容器內(nèi)拿一個(gè)start和end，如果是合法的，就依次將他們?cè)俅畏湃肴菀祝肋@個(gè)容器為空未知。
給個(gè)運(yùn)行實(shí)例吧，我在代碼里面實(shí)現(xiàn)的是實(shí)現(xiàn)隨機(jī)數(shù)排序，ref采用隨機(jī)選取的方式。
原文鏈接：http://www.cnblogs.com/real-madrid/p/7203618.html
