Quick Sort (cpp_quick_sort.cc)
================================================================================
最好时间复杂度 O(nlogn)
平均时间复杂度 O(nlogn)
最坏时间复杂度 O(n^2)
空间复杂度 O(logn)
是否稳定 否
Quick Sort基于分治法，每次在序列中选出一个元素作为划分点p，对序列进行一次扫描，将序列划分为：<(x<p)，(x=p)，(x>p)>这样的的形式，然后对左右两个集合进行递归处理直到排序完毕。
在快速排序中，对划分点p的选择是影响排序性能的一个关键因素，常用的选择方法有随机选择法和三数取中法。随机法可以保证对于算法任何输入都只有极小的概率以O(n^2)时间运行；三数取中法是对首、中、尾三数进行排序后取中间元素作为划分点，对极少数输入有O(n^2)的最坏时间，由于进行三数取中操作会在序列首尾形成两个“哨兵”元素，所以使用三数取中操作后的划分操作可以适当简化，提高速度。在测试代码中我使用的是三数取中的方法。
Quick Sort算法正如其名，在所有测试的算法中速度是最快的，它是SGI-STL库中std::sort()的主要算法。
1 #include <cstdio>
2 #include <cstdlib>
3 #include <ctime>
4
5 static unsigned int set_times = 0;
6 static unsigned int cmp_times = 0;
7
8 template<typename item_type> void setval(item_type& item1, item_type& item2) {
9 set_times += 1;
10 item1 = item2;
11 return;
12 }
13
14 template<typename item_type> int compare(item_type& item1, item_type& item2) {
15 cmp_times += 1;
16 return item1 < item2;
17 }
18
19 template<typename item_type> void swap(item_type& item1, item_type& item2) {
20 item_type item3;
21
22 setval(item3, item1);
23 setval(item1, item2);
24 setval(item2, item3);
25 return;
26 }
27
28 template<typename item_type> void quick_sort(item_type* array, int size) {
29 item_type pivot;
30 int l = 0;
31 int m = size / 2;
32 int r = size - 1;
33
34 if(size > 1) {
35 if(compare(array[r], array[l])) swap(array[l], array[r]);
36 if(compare(array[m], array[l])) swap(array[l], array[m]);
37 if(compare(array[r], array[m])) swap(array[m], array[r]);
38 pivot = array[m];
39
40 while(l <= r) {
41 while(compare(array[l], pivot)) l++;
42 while(compare(pivot, array[r])) r--;
43 if(l <= r) {
44 swap(array[l++], array[r--]);
45 }
46 }
47 quick_sort(array, r + 1);
48 quick_sort(array + l, size - l);
49 }
50 return;
51 }
52
53 int main(int argc, char** argv) {
54 int capacity = 0;
55 int size = 0;
56 int i;
57 clock_t clock1;
58 clock_t clock2;
59 double data;
60 double* array = NULL;
61
62 // generate randomized test case
63 while(scanf("%lf", &data) == 1) {
64 if(size == capacity) {
65 capacity = (size + 1) * 2;
66 array = (double*)realloc(array, capacity * sizeof(double));
67 }
68 array[size++] = data;
69 }
70
71 // sort
72 clock1 = clock();
73 quick_sort(array, size);
74 clock2 = clock();
75
76 // output test result
77 fprintf(stderr, "quick_sort:\t");
78 fprintf(stderr, "time %.2lf\t", (double)(clock2 - clock1) / CLOCKS_PER_SEC);
79 fprintf(stderr, "cmp_per_elem %.2lf\t", (double)cmp_times / size);
80 fprintf(stderr, "set_per_elem %.2lf\n", (double)set_times / size);
81 for(i = 0; i < size; i++) {
82 fprintf(stdout, "%lf\n", array[i]);
83 }
84 free(array);
85 return 0;
86 }