Comb Sort (cpp_comb_sort.cc)
================================================================================
最好时间复杂度 O(?)
平均时间复杂度 O(?)
最坏时间复杂度 O(?)
空间复杂度 O(1)
是否稳定 否
Comb Sort与Shell Sort的思想基本相同，不过使用的是变步长的冒泡排序。
Comb Sort的大部分特性和Shell Sort相同，也存在复杂度难以确定的问题。但是Comb Sort在比较数据的时候不像Shell Sort那样跳跃地进行比较，减少了CPU更新缓存和操作系统换页上的时间开销，所以效率比Shell Sort要高。同时Comb 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 comb_sort(item_type* array, int size) {
29 int noswap = 1;
30 int delta = size;
31 int i;
32
33 while(!noswap || delta > 1) {
34 if(delta > 1) {
35 delta /= 1.25;
36 }
37 for(noswap = 1, i = 0; i + delta < size; i++) {
38 if(compare(array[i + delta], array[i])) {
39 noswap = 0;
40 swap(array[i + delta], array[i]);
41 }
42 }
43 }
44 return;
45 }
46
47 int main(int argc, char** argv) {
48 int capacity = 0;
49 int size = 0;
50 int i;
51 clock_t clock1;
52 clock_t clock2;
53 double data;
54 double* array = NULL;
55
56 // generate randomized test case
57 while(scanf("%lf", &data) == 1) {
58 if(size == capacity) {
59 capacity = (size + 1) * 2;
60 array = (double*)realloc(array, capacity * sizeof(double));
61 }
62 array[size++] = data;
63 }
64
65 // sort
66 clock1 = clock();
67 comb_sort(array, size);
68 clock2 = clock();
69
70 // output test result
71 fprintf(stderr, "comb_sort:\t");
72 fprintf(stderr, "time %.2lf\t", (double)(clock2 - clock1) / CLOCKS_PER_SEC);
73 fprintf(stderr, "cmp_per_elem %.2lf\t", (double)cmp_times / size);
74 fprintf(stderr, "set_per_elem %.2lf\n", (double)set_times / size);
75 for(i = 0; i < size; i++) {
76 fprintf(stdout, "%lf\n", array[i]);
77 }
78 free(array);
79 return 0;
80 }