希爾排序（Shell Sort）是插入排序的一種，也是直接插入排序的更高效的改進(jìn)版本，希爾排序充分利用了插入排序的兩個(gè)特點(diǎn)：

1）當(dāng)數(shù)據(jù)規(guī)模小的時(shí)候非常高效。

2）當(dāng)給定數(shù)據(jù)已經(jīng)有序時(shí)的時(shí)間復(fù)雜度為O(n)。

所以，Shell排序每次把數(shù)據(jù)分成若干塊，來使用插入排序，而且之后在這若干個(gè)小塊排好序的情況下把它們合成大一點(diǎn)的小塊，繼續(xù)使用插入排序，不停地合并小塊，直到最后一個(gè)小塊。

這里每次分成若干個(gè)小塊是通過“增量”來控制的，開始的時(shí)候增量較大，接近n/2，從而使得分割出來接近n/2個(gè)小塊，逐漸的減小“增量”，最終減小到1。

例如：

public class Main {
    public static int count = 0;
    public static void shellSort(int[] data) {
        // 計(jì)算出最大的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);
                }
            }
            // 計(jì)算出下一個(gè)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);
    }
}

運(yùn)行結(jié)果如下：

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