Shell Sort (cpp_shell_sort.cc)
================================================================================
最好时间复杂度 O(?)
平均时间复杂度 O(?)
最坏时间复杂度 O(?)
空间复杂度 O(1)
是否稳定 否
Shell Sort是变步长的插入排序，利用插入排序在数据基本有序时速度较快的特点，先用较大步长的插入排序使数据变得基本有序，再用小步长的插入排序完成整个排序过程。
Shell Sort的时间复杂度随着增量序列的改变而不同，要证明一个增量序列的时间复杂度是一个很困难的问题，一般的增量序列会得到一个O(n^k)的复杂度(1 < k <= 2)。在测试中我使用的是来自维基百科上的一个增量序列，在n <= 2^30的测试样例中基本上与O(nlogn)的算法没有差别。
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 shell_sort(item_type* array, int size) {
29 static const unsigned int inc[] = {
30 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787,
31 45806244, 217378076, 1031612713,
32 };
33 int inc_index = sizeof(inc) / sizeof(*inc) - 1;
34 int delta;
35 int start;
36 int i;
37 int j;
38 item_type tempitem;
39
40 if(size > 1) {
41 while(inc[inc_index] >= size) {
42 inc_index -= 1;
43 }
44 while(inc_index >= 0) {
45 delta = inc[inc_index--];
46 for(start = 0; start < delta; start++) {
47 for(i = start; i + delta < size; i += delta) {
48 setval(tempitem, array[i + delta]);
49 for(j = i; j >= 0 && compare(tempitem, array[j]); j -= delta) {
50 setval(array[j + delta], array[j]);
51 }
52 setval(array[j + delta], tempitem);
53 }
54 }
55 }
56 }
57 return;
58 }
59
60 int main(int argc, char** argv) {
61 int capacity = 0;
62 int size = 0;
63 int i;
64 clock_t clock1;
65 clock_t clock2;
66 double data;
67 double* array = NULL;
68
69 // generate randomized test case
70 while(scanf("%lf", &data) == 1) {
71 if(size == capacity) {
72 capacity = (size + 1) * 2;
73 array = (double*)realloc(array, capacity * sizeof(double));
74 }
75 array[size++] = data;
76 }
77
78 // sort
79 clock1 = clock();
80 shell_sort(array, size);
81 clock2 = clock();
82
83 // output test result
84 fprintf(stderr, "shell_sort:\t");
85 fprintf(stderr, "time %.2lf\t", (double)(clock2 - clock1) / CLOCKS_PER_SEC);
86 fprintf(stderr, "cmp_per_elem %.2lf\t", (double)cmp_times / size);
87 fprintf(stderr, "set_per_elem %.2lf\n", (double)set_times / size);
88 for(i = 0; i < size; i++) {
89 fprintf(stdout, "%lf\n", array[i]);
90 }
91 free(array);
92 return 0;
93 }