希尔排序是插入排序的一种类型，也可以用一个形象的叫法缩小增量法。基本思想就是把一个数组分为好几个数组，有点像分治法，不过这里的划分是用一个常量d来控制。

这个0<d<n,n为数组的长度。这个算法有了插入排序的速度，也可以算是一个改进算法，在插入算法中，如果有一个最小的数在数组的最后面，用插入算法就会重最后一个

位置移动到第一个，这样就会浪费很大，使用这个改进的希尔排序可以实现数据元素的大跨度的移动。也就是这个算法的优越之处。

     希尔排序算法的基本思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各 组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…< d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。     

public static void ShellSort(int[] H) {

        int dk = 1;

        while (dk <= H.length / 3)

            dk = dk * 3 + 1;                          //确定增量的过程

        while (dk>= 1) {                             

            for (int i = dk; i <= H.length - 1; i = i + dk) {         //直接插入法

                 int x = H[i];

                int j = i - dk;                               

                for (; j >= 0&&x < H[j]; j = j - dk) {

                        H[j + dk] = H[j];                                    //   for (; j >= 0; j--) {if (x < H[j]) {H[j + 1] = H[j]; }  else break;}    对比一下，简便方法

                }

                H[j + dk] = x;

            }

            dk = dk / 3;                                                     //缩小增量，到1的时候是直接插入法。

        }

        for (int k : H) {

            System.out.print(k + " ");

        }      

    }

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] H = { 4,  6, 3, 7, 21,  14, 28, 24, 31, 33, 2 };

        ShellSort(H);

    }