1 基本原理

希爾排序是一種遞減增量插入排序算法。普通的插入排序的是以1為間隔進行排序，希爾排序是在其上做的優(yōu)化，比如取一間隔序列為1，4，9 ，首先以9為間隔排序，再次以4為間隔排序，最后以1為間隔排序，就是普通的插入排序。

2 實現(xiàn)

public static void ShellSort(int[] a){
        int n = a.length;
        int h = 1;
        while(h < n/3){
            h = 3*h + 1;
        }
        while(h >= 1){
            for(int i = h; i < n; i++){
                for(int j = i;  j >= h && SortUtil.less(a,j,j-h);j -= h){
                    SortUtil.swap(a,j,j-h);
                }
            }
            h /= 3;
        }
    }

3 算法分析

時間復(fù)雜度不好分析，空間復(fù)雜度是O(1)，不穩(wěn)定算法