2種方案的C++實現(xiàn)：
1 #include <vector>
2 #include <iterator>
3 #include <algorithm>
4 #include <iostream>
5 #include <cstdlib>
6 #include <ctime>
7 #include <cassert>
8
9 void printv(const std::vector<int>& v)
10 {
11 std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
12 std::cout << std::endl;
13 }
14
15 void printv(const std::vector<int>& v, int l, int h)
16 {
17 std::copy(v.begin()+l, v.begin()+h+1, std::ostream_iterator<int>(std::cout, " "));
18 std::cout << std::endl;
19 }
20
21 int exchange(int& a, int& b)
22 {
23 int tmp = a;
24 a = b;
25 b = tmp;
26 }
27
28 int partition1(std::vector<int>& v, int l, int h)
29 {
30 int i = l-1;
31 int pivot = v[h];
32 int j = l;
33 while (j < h) {
34 if (v[j] < pivot) {
35 i++;
36 exchange(v[i], v[j]);
37 }
38 j++;
39 }
40 exchange(v[i+1], v[h]);
41 return i+1;
42 }
43
44 int partition2(std::vector<int>& v, int l, int h)
45 {
46 int m = l+(h-l)/2;
47 int i = l;
48 int j = h;
49
50 int pivot = v[m];
51 while (1) {
52 while (v[i] < pivot) i++;
53 while (v[j] > pivot) j--;
54 if (!(i<j)) {
57 return j;
58 }
59 exchange(v[i], v[j]);
60 i++;j--;
61 }
62 }
63
64 void myQuickSort1(std::vector<int>& v, int l, int h)
65 {
66 /*
67 Please note, returned m is the loc of pivot,
68 in below myQuickSort1, can remove m, since left of m, all <= pivot
69 right of m, all >= pivot
70 */
71 if (l < h) {
72 int m = partition1(v, l, h);
73 myQuickSort1(v, l, m-1);
74 myQuickSort1(v, m+1, h);
75 }
76 }
77
78 void myQuickSort2(std::vector<int>& v, int l, int h)
79 {
80 /*
81 if partition2 return i, please call below
82 myQuickSort2(v, l, m-1);
83 myQuickSort2(v, m, h);
84 else if it return j, please call below
85 myQuickSort2(v, l, m);
86 myQuickSort2(v, m+1, h);
87 */
88 if (l < h) {
89 int m = partition2(v, l, h);
90 myQuickSort2(v, l, m);
91 myQuickSort2(v, m+1, h);
92 }
93 }
94
95 int main()
96 {
97
98 const int N = 100;
99 srand(time(0));
100 std::vector<int> v, vtmp;
101 for (int i = 0; i < N; i++)
102 v.push_back(int(rand()%N));
103 vtmp.insert(vtmp.end(), v.begin(), v.end());
104 std::cout << "Original data sequence is:\n";
105 std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
106 std::cout << std::endl;
107 myQuickSort1(v, 0, N-1);
108 std::cout << "After quicksort(1), the data sequence is:\n";
109 std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
110 std::cout << std::endl;
111
112 myQuickSort2(vtmp, 0, N-1);
113 std::cout << "After quicksort(2), the data sequence is:\n";
114 std::copy(vtmp.begin(), vtmp.end(), std::ostream_iterator<int>(std::cout, " "));
115 std::cout << std::endl;
116
117 assert(v==vtmp);
118 return 0;
119 }
120