希尔排序 Shell sort

https://github.com/hotwater99/practice_datastructure_and_algorithm.git

《数据结构与算法分析——C语言描述》机械工业出版社，原书第2版，7.4节

希尔排序也叫缩小增量排序 diminishing increment sort，可以认为是插入排序的进阶版，时间复杂度为O(N^7/6)。

1、增量序列h₁=1, h₂, …, h_t。总共t轮排序，首轮使用增量h_t，最后一轮使用增量h₁=1，每一轮用增量h进行插入排序；

2、希尔排序的效率依赖于增量序列的选择，Shell建议的增量序列是h_t = N / 2，h_k = h_k+1 / 2，使用很方便（并非最优）；

3、在每轮的插入过程中，使用临时变量tmp来实现一个“前滤”的策略，可以避免交换操作。

希尔排序比插入排序效率高，个人理解的原因是：

1、插入排序需要逐个比较，希尔排序的增量使得可以跳过某些项，直接到达靠前的位置；

2、每一轮排序之后，得到的序列变得更有序了，不会做无用功。

以长度N=10的随机数组为例：1 7 4 0 9 4 8 8 2 4 ，增量序列h1, h2, h3 为：1, 2, 5

希尔排序：

  1 void ShellSort(int array[], int N)
  2 {
  3   int i, j, increment;
  4   int tmp;
  5 
  6   for (increment = N / 2; increment > 0; increment /= 2) {
  7     for (i = increment; i < N; i++) {
  8       tmp = array[i];
  9       for (j = i; j >= increment; j -= increment) {
 10         if (tmp < array[j - increment])
 11           array[j] = array[j - increment];
 12         else
 13           break;
 14       }
 15       array[j] = tmp;
 16     }
 17   }
 18 }

完整代码：

  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