数据结构之shell排序

希尔排序是插入排序的一种类型，也可以用一个形象的叫法缩小增量法。基本思想就是把一个数组分为好几个数组，有点像分治法，不过这里的划分是用一个常量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);
    }