2.希尔排序

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。