排序算法（四） —— 希尔排序

1. 和直接插入排序的关系

　　在之前直接插入排序中提到过，希尔排序（Shell sort）是直接插入排序的变种方式之一，是一种更高效的改进版本。其基本思想如下：

记录按下标的一定增量分组，对每组进行直接插入排序。
不断地缩小增量，对每组进行直接插入排序，直至增量为1。

　　由此可见，希尔排序本质就是多次使用直接插入排序。其优于直接插入排序的原因在之前也提到过，就是：直接插入排序对于基本有序的数组，拥有较高的性能。

　　希尔入排序的时间复杂度是O(n^2)（只是针对最坏情况而言，平均的效率要远远高出其他时间复杂度为O(n^2)的排序算法），空间复杂度是O(1)，但是在提供优秀性能的同时，打破了排序算法的稳定性。

　　直接插入排序：http://www.cnblogs.com/jing-an-feng-shao/p/6165094.html

2. 希尔排序的实现

　　希尔排序，又称缩小增量排序，其重点显然在于初始增量 d 的选取，以及每次增量 d 缩小的额度。一般来说，初始增量设为数组长度的一半，同时每次增量减半，直至 d=1，可以满足大多数的需求。

　　下面用一个具体的场景，直观地体会一下希尔排序的过程。

场景：

现有一个无序数组，共7个数：89 45 54 29 90 34 68。

使用希尔排序法，对这个数组进行升序排序。

初始数组：

89 45 54 29 90 34 68

第一步：增量 d=3

29 45 34 68 90 54 89

第二步：增量 d=1

29 34 45 54 68 89 90

希尔排序的 Java 代码实现：

 1     public static void basal(int[] array) {
 2         if (array == null || array.length < 2) {
 3             return;
 4         }
 5         // 初始增量
 6         int d = array.length >>> 1;
 7         while (d > 0) {
 8             // d 次直接插入排序
 9             for (int i = 0; i < d; i++) {
10                 // 组内进行，相隔增量 d 项的直接插入排序
11                 for (int j = i + d; j < array.length; j += d) {
12                     int cur = array[j];
13                     boolean flag = false;
14                     for (int k = j - d; k > -1; k -= d) {
15                         if (cur < array[k]) {
16                             array[k + d] = array[k];
17                         } else {
18                             array[k + d] = cur;
19                             flag = true;
20                             break;
21                         }
22                     }
23                     if (!flag) {
24                         array[i] = cur;
25                     }
26                 }
27             }
28             // 每次增量减半
29             d >>>= 1;
30         }
31     }

basal

3. “优化”希尔排序

　　希尔排序，最终还是要通过直接插入排序来实现的，那么就自然而然地有这么一个想法：直接插入排序的优化手段，在希尔排序上，是不是也能够适用呢？况且，由于希尔排序的不稳定性，使得二分查找优化直接插入排序法用起来没有后顾之忧。

设置哨兵位优化希尔排序的 Java 代码实现：

 1     // 优化：记录上一次插入的位置
 2     public static void optimized_1(int[] array) {
 3         if (array == null || array.length < 2) {
 4             return;
 5         }
 6         // 初始增量
 7         int d = array.length >>> 1;
 8         while (d > 0) {
 9             for (int i = 0; i < d; i++) {
10                 int checkN = array[i];
11                 int checkI = i;
12                 // 组内进行，相隔增量 d 项的直接插入排序
13                 for (int j = i + d; j < array.length; j += d) {
14                     int cur = array[j];
15                     int start = j - d;
16                     // 根据上一个值，定位开始遍历的位置
17                     if (cur < checkN) {
18                         start = checkI;
19                         for (int k = j - d; k > start - d; k -= d) {
20                             array[k + d] = array[k];
21                         }
22                     }
23                     boolean flag = false;
24                     for (int k = start; k > -1; k -= d) {
25                         if (cur < array[k]) {
26                             array[k + d] = array[k];
27                         } else {
28                             array[k + d] = cur;
29                             checkN = cur;
30                             checkI = k + d;
31                             flag = true;
32                             break;
33                         }
34                     }
35                     if (!flag) {
36                         array[i] = cur;
37                     }
38                 }
39             }
40             // 每次增量减半
41             d >>>= 1;
42         }
43     }

optimized_1

二分查找法优化希尔排序的 Java 代码实现：

 1     // 优化：二分查找定位
 2     public static void optimized_2(int[] array) {
 3         if (array == null || array.length < 2) {
 4             return;
 5         }
 6         // 初始增量
 7         int d = array.length >>> 1;
 8         while (d > 0) {
 9             for (int i = 0; i < d; i++) {
10                 // 二分查找定位
11                 for (int j = i + d; j < array.length; j += d) {
12                     int cur = array[j];
13                     int low = i, high = j - d;
14                     int index = binarySearch(array, low, high, cur, d);
15                     for (int k = j - d; k > index - d; k -= d) {
16                         array[k + d] = array[k];
17                     }
18                     array[index] = cur;
19                 }
20             }
21             // 每次增量减半
22             d >>>= 1;
23         }
24     }
25 
26     // 二分查找，返回待插入的位置
27     private static int binarySearch(int[] array, int low, int high, int cur, int d) {
28         while (low <= high) {
29             // 带增量 d 的中间数，是不一样的
30             // 注意移位运算符的优先级
31             int mid = ((low / d + high / d) >>> 1) * d + low % d;
32             int mVal = array[mid];
33             if (mVal < cur) {
34                 low = mid + d;
35             } else if (mVal > cur) {
36                 high = mid - d;
37             } else {
38                 return mid;
39             }
40         }
41         // 未查到
42         return low;
43     }

optimized_2

4. 简单的性能比较

　　通过上述代码，我们对希尔排序进行了一定的优化，但是具体的性能还有待商榷，使用以下测试代码进行简单的性能研究。

 1     public static void main(String[] args) {
 2 
 3         final int size = 100000;
 4         // 模拟数组
 5         int[] array = new int[size];
 6         for (int i = 0; i < array.length; i++) {
 7             array[i] = new Random().nextInt(size) + 1;
 8         }
 9         
10         // 时间输出：纳秒
11         long s1 = System.nanoTime();
12         Shell.basal(array);
13         long e1 = System.nanoTime();
14         System.out.println(e1 - s1);
15     }

test

执行结果：

结论如下：

直接插入排序的优化手段，对希尔排序没有作用，反而是一种伤害。原因在直接插入排序中提到过：其优化手段对于小规模的数组是有害的。而希尔排序的原理是将整个数组拆成若干个小数组，利用直接插入排序对基本有序的数组拥有良好的性能这一特性出发的。
同样是不稳定排序，对比直接插入排序的二分查找优化，无论数组规模的大小，希尔排序在性能上都有明显的优势。