希尔排序

希尔排序又称缩小增量排序，它本质上是一个插入排序算法，为什么那？

因为，对于插入排序而言，插入排序是将当前的待排序的元素与前面的所有的元素比较，而希尔排序是将当前的元素与前面的增量位置上的元素进行比较，然后，再将该元素插入到合适的位置。当一趟希尔排序完成后，处于增量位置上的元素是有序的。

希尔排序算法的效率依赖于增量的选取

假设增量序列为h(1),h(2)......h(k),其中h(1)必须为1，且h(1)<h(2)<......<h(k)。

第一趟排序时在增量为h(k)的各个元素上进行比较；

第二趟排序时在增量为h(k-1)的各个元素上进行比较；

......

最后一趟在增量h(1)上进行比较。由此可见，每进行一趟排序，增量是一个不断减少的过程，因此称之为缩小增量。

当增量减少到h(1)=1时，这里完全就是插入排序了，而在此时，整个元素经过前段的k-1趟排序后，已经变的基本有序了，而我们知道，对于插入排序而言，当待排序的数组基本有序时，插入序列的效率是非常高的。因此，希尔排序就是利用“增量”技巧将插入排序的平均时间复杂度O(N^2)降低为亚二次方。

希尔排序分析

假设原始数组为：32    42    43    23    97    12    48。h(1)=1 h(2)=3

这里一共有两个增量序列，故一共有两趟排序，第一趟按照增量3来排序，处于增量3上的元素集合如下<32 23 48><42 97><43 12>排序后变成：<23 32 48><42 97><12 43>，即数组变成了23 42 12 32 97 43 48，可以看出，在增量为3的各个位置上的元素都是有序的。经过前面一趟排序，此时数组已经基本有序，再使用增量为1的排序时，比较的次数将会大大的降低。

第二趟为h(1)=1来排序

代码如下：

//希尔排序算法

func ShellSort(in []int)  (eerror) {

    //使用希尔推荐的增量 h(k) = N/2

   var temp int

   h := len(in)

   for h >=1 {

        for i := h; i < len(in); i +=h {

            for j := i; j >= h && in[j] < in[j-h]; j -= h {

                temp = in[j]

                in[j] = in[j-h]

                in[j-h] = temp

            }

        }

        h /=2

       }

    return nil

}

希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列n/2，（n/2/2)......1,其最坏的时间复杂度为O(n^2)。