前言

希尔排序是基于插入排序实现的（如果不了解插入排序，可以先阅读这篇文章）

一、插入排序的缺点

假设数据中最小的数排在靠右端位置上，这本来是较大值的数据所在位置，把这个小数据移动到左边位置上，所有的中间数据项都必须向右移动一位。

在这里插入图片描述

这个步骤对每一个数据项都执行了将近N次的复制。（虽然不是所有数据项都必须移动N个位置，但是数据项平均移动了N/2位置）执行N次N/2个位移，总共是次复制。因此，插入排序的执行效率是

因此如果能以某种方式不必一个一个的移动所有中间数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率就会有很大改进。

二、希尔排序

希尔排序通过加大插入排序中元素之间的间隔，并在这些间隔的元素中进行插入排序，从而使数据能大跨度移动。当这些数据排过一趟之后，希尔排序算法减小数据项的间隔再进行排序。进行排序时数据项之间的间隔被称为增量，用字母h来表示。

下图为增量为4是对包含10个数据项的数据进行排序的过程。

在这里插入图片描述

当对7、2、4数据项完成排序之后，算法向右移一步，对10、5、3号数据进行排序。直到所有的数据项都完成了4-增量排序。也就是说所有间隔为4的数据项之间都已经排列有序。

上述例子中，完成以4位增量的希尔排序之后，所有元素离它最终有序的位置相差不到两个单元。这也是希尔排序的奥秘所在。通过创建这种交错的内部有序的数据集合，把完成排序所必须的工作量将到最小。

三、 寻找间隔

上面展示了以4位初始间隔，对10个数据项的数组进行排序。但对于不同长度的数据，如何定义初始间隔，然后不断减小间隔，直到间隔变成1表示排序完成.
这里我们使用公式 以逆向形式从1开始，来查找初始间隔。（这是由Knuth提出的）下面以1000长度的数据项为例

h	3*h+1	(h-1)/3
1	4
4	13	1
13	40	4
40	121	13
121	364	40
364	1093	121
1093	3280	364

h值最初为1，然后应用公式h=3*h+1生成序列1,4，13,40,121,364等等。当间隔大于数组长度时停止。对于1000个数据项的数据，1093太大了。因此用364作增量排序。然后，每完成一次排序，就用前面的公式倒推减小间隔：
当数组用1增量排序之后，算法结束。

四、java实现

 public class ShellSort {
    private int[] arr;

    public ShellSort(int[] arr) {
        this.arr = arr;
    }

    public void shellSort() {
        int left, right;
        int temp;
        int h = 1;
        //计算初始增量
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }
        System.out.println("h: "+ h);
        while (h > 0) {
            for (right = h; right < arr.length; right++) {
                temp = arr[right];
                left = right;
                while (left > h-1 && arr[left - h] >= temp) {
                    arr[left] = arr[left - h];
                    left-=h;
                }
                arr[left] = temp;
            }
           // System.out.println(Arrays.toString(arr));
            //倒推增量
            h = (h-1)/3;
        }

    }
}

五、总结

对比插入排序代码可以看出，插入排序与希尔排序的差别就是增加了一个增量h，但是效率却提高了很多。希尔排序效率大概在O(N^(3/2)) ~O(N^(7/6))之间。