1 // 快速排序：begin
2 // 快速排序在平均情况下的时间复杂性是O(nlogn)，快速排序时不稳定的排序
3
4 // 方法1：
5 template<class T>
6 void quick_sort1(T *a, int left, int right)
7 {
8 if (left < right) // 数组元素至少有2个才进行排序
9 {
10 int p = partition(a, left, right);
11 quick_sort1(a, left, p - 1);
12 quick_sort1(a, p + 1, right);
13 }
14 }
15
16 template<class T>
17 int partition(T *a, int left, int right)
18 {
19 int l = left, r = right;
20 T pivot = a[left];
21 while (l < r)
22 {
23 while (a[l] < pivot) ++l;
24 while (a[r] > pivot) --r;
25 swap(a[l], a[r]);
26 }
27 swap(a[l], a[r]); // 当i>=j时，上面while循环会多swap操作一次，所以必须撤销最后一次操作
28 swap(a[r], pivot);
29
30 return r;
31 }
32
33 //==================================
34 // 方法2：
35 template<class T>
36 void quick_sort2(T *a, int left, int right)
37 {
38 if(left >= right)
39 return;
40
41 int l = left, r = right;
42 T pivot = a[left];
43 while(l != r)
44 {
45 while(l < r && a[r] >= pivot) r--;
46 a[l] = a[r];
47 while(l < r && a[l] <= pivot) l++;
48 a[r] = a[l];
49 }
50 a[l] = pivot;
51
52 quick_sort2(a, left, l - 1);
53 quick_sort2(a, l + 1, right);
54 }
55 // 快速排序：end
测试代码如下：
1 int main()
2 {
3 // 测试快速排序
4 int test1[7] = {7, 6, 5, 4, 3, 2 ,1};
5 // char test1[7] = {'e', 'x', 'a', 'm', 'p', 'l', 'e'};
6 //quick_sort1(test1, 0, 6);
7 quick_sort2(test1, 0, 6);
8 cout << "After QuickSort:"<<endl;
9 for(int i = 0; i < 7; ++i)
10 cout << test1[i] << "";
11 cout << endl;
12
13 return 0;
14 }