希尔排序

1 基本原理

希尔排序是一种递减增量插入排序算法。普通的插入排序的是以1为间隔进行排序，希尔排序是在其上做的优化，比如取一间隔序列为1，4，9 ，首先以9为间隔排序，再次以4为间隔排序，最后以1为间隔排序，就是普通的插入排序。

2 实现

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 算法分析

时间复杂度不好分析，空间复杂度是O(1)，不稳定算法