https://github.com/hotwater99/practice_datastructure_and_algorithm.git
《数据结构与算法分析——C语言描述》机械工业出版社，原书第2版，7.4节
希尔排序 Shell sort / 缩小增量排序 diminishing increment sort
增量序列h1, h2, …, ht，h1=1。总共t轮排序，首轮使用增量ht，最后一轮使用增量h1=1。
Shell建议的增量序列是ht = N / 2，hk = hk+1 / 2。
每一轮相当于是用增量h进行插入排序。
时间复杂度为O(N7/6)，据说证明很复杂。
以长度为10的随机数组为例：1 7 4 0 9 4 8 8 2 4 ，增量序列h1, h2, h3 为：1, 2, 5。
1 #include <iostream> 2 #include <ctime> 3 4 using namespace std; 5 6 #define random(x) (rand()%x) 7 #define ARRAY_LENTH 100000 8 9 void ShellSort(int array[], int N) 10 { 11 int i, j, increment; 12 int tmp; 13 14 for (increment = N / 2; increment > 0; increment /= 2) { 15 for (i = increment; i < N; i++) { 16 tmp = array[i]; 17 for (j = i; j >= increment; j -= increment) { 18 if (tmp < array[j - increment]) 19 array[j] = array[j - increment]; 20 else 21 break; 22 } 23 array[j] = tmp; 24 } 25 } 26 } 27 28 int main() { 29 int test_array[ARRAY_LENTH]; 30 int i, N = ARRAY_LENTH; 31 clock_t start_time, stop_time; 32 33 for (i = 0; i < N; i++) { 34 test_array[i] = random(N); 35 } 36 37 cout << "raw : "; 38 for (i = 0; i < N; i++) { 39 cout << test_array[i] << " "; 40 } 41 cout << endl; 42 43 start_time = clock(); 44 45 ShellSort(test_array, N); 46 47 stop_time = clock(); 48 49 cout << "sort: " ; 50 for (i = 0; i < N; i++) { 51 cout << test_array[i] << " "; 52 } 53 cout << endl; 54 55 cout << "ShellSort(" << N << ")..." << endl; 56 cout << "total time used: "; 57 cout << (double)(stop_time - start_time) / CLOCKS_PER_SEC << "s" << endl; 58 59 system("pause"); 60 61 return 0; 62 }
测试结果
N=10
raw : 1 7 4 0 9 4 8 8 2 4 sort: 0 1 2 4 4 4 7 8 8 9 ShellSort(10)... total time used: 0s
N=100
raw : 41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2 53 92 82 21 16 18 95 47 26 71 38 69 12 67 99 35 94 3 11 22 33 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78 16 35 90 42 88 6 40 42 64 48 46 5 90 29 70 50 6 1 93 48 29 23 84 54 56 40 66 76 31 8 44 39 26 23 37 38 18 82 29 41 sort: 0 1 2 3 4 5 5 6 6 8 11 11 12 16 16 18 18 21 22 23 23 23 24 26 26 27 27 29 29 29 29 31 33 34 35 35 36 37 37 38 38 39 40 40 41 41 41 41 42 42 42 44 44 45 46 47 47 48 48 50 53 53 54 56 57 58 59 61 62 62 64 64 64 66 67 67 68 69 69 70 71 73 76 78 78 81 82 82 84 88 90 90 91 91 92 93 94 95 95 99 ShellSort(100)... total time used: 0s
N=1000
ShellSort(1000)... total time used: 0s
N=10000
ShellSort(10000)... total time used: 0.002s
N = 100000
ShellSort(100000)... total time used: 0.022s
原文：https://www.cnblogs.com/hotwater99/p/12786421.html