Java希尔排序（Shell Sort）

希尔排序（Shell Sort）是插入排序的一种，也是直接插入排序的更高效的改进版本，希尔排序充分利用了插入排序的两个特点：

1）当数据规模小的时候非常高效。

2）当给定数据已经有序时的时间复杂度为O(n)。

所以，Shell排序每次把数据分成若干块，来使用插入排序，而且之后在这若干个小块排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停地合并小块，直到最后一个小块。

这里每次分成若干个小块是通过“增量”来控制的，开始的时候增量较大，接近n/2，从而使得分割出来接近n/2个小块，逐渐的减小“增量”，最终减小到1。

例如：

public class Main {
    public static int count = 0;
    public static void shellSort(int[] data) {
        // 计算出最大的h值
        int h = 1;
        while(h <= data.length / 3) {
            h = h * 3 + 1;
        }
        while(h > 0) {
            for(int i=h;i<data.length;i+=h) {
                if(data[i] < data[i-h]) {
                    int tmp = data[i];
                    int j = i-h;
                    while(j >= 0 && data[j] > tmp) {
                        data[j+h] = data[j];
                        j -= h;
                    }
                    data[j+h] = tmp;
                    print(data);
                }
            }
            // 计算出下一个h值
            h = (h - 1) / 3;
        }
    }
    public static void print(int[] data) {
        for(int i=0;i< data.length;i++) {
            System.out.print(data[i]+"\t");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] data = new int[]{4,6,1,9,5,8};
        print(data);
        shellSort(data);
        print(data);
    }
}

运行结果如下：

4   6   1   9   5   8  
1   4   6   9   5   8  
1   4   5   6   9   8  
1   4   5   6   8   9  
1   4   5   6   8   9