1.什么是希尔排序
对于大规模的乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点的从一端移动到另一端。例如最小的数在数组的末尾，那么它需要移动N-1次。
希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入的排序将局部有限的数组排序。
- h有序数组
数组中任意间隔为h的元素都是有序的，则该数组成为h有序数组。
一个h有序数组就是由h个互相独立的有序数组编织在一起组成的数组，如下图所示：
h有序数组.png
希尔排序的思想就是使随机数组成为h有序数组，这样当h很大时，我们就能将元素移动到很远的地方。h由大变小，最终变为1，这样对于任意以1结尾的h序列，我们都能将数组排序，这就是希尔排序。
2.实现
下面的代码实现了从N/3开始递减到1的希尔排序。
public static void shellSort(int[] a) {
int n = a.length;
// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) {
// 将数组变为h有序
for (int i = h; i < n; i++) {
//将a[i] 插入到a[i-h],a[i - 2*h],a[i - 3*h]....
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
assert isHsorted(a, h);
h /= 3;
}
assert isSorted(a);
}
希尔排序轨迹图.png
上面的实现方法其实就是将普通插入排序的1变为了递减的h。
