希尔排序

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
最优时间复杂度 ---- O(n)
平均时间复杂度 ---- 根据步长序列的不同而不同。
所需辅助空间 ------ O(1)
稳定性 ------------ 不稳定

原理

       希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）

代码实现

public class ShellSort {
    void sort(Integer[] array) {
        int n = array.length;
        int i, j, get;
        int h = 0;
        // 生成初始增量
        while (h <= n)
        {
            h = 3 * h + 1;
        }
        while (h >= 1)
        {
            // 每次从增量开始
            for (i = h; i < n; i++)
            {
                // 获取对比位置j--增长位置i向前间隔增量h的位置
                j = i - h;
                get = array[i];
                // 如果对比位置大于等于0且对比值大于增长值
                while ((j >= 0) && (array[j] > get))
                {
                    // 把数组大的放到后面的位置
                    array[j + h] = array[j];
                    // 再根据间隔往前对比
                    j = j - h;
                }
                //把最前面的位置放入最小值
                array[j + h] = get;
            }
            // 递减增量
            h = (h - 1) / 3;
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0,7};
        ShellSort sort = new ShellSort();
        sort.sort(a);
        System.out.println("array by ShellSort is " + Tool.arrayToString(a));
    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

实现结果：

array by ShellSort is [0,1,2,3,4,5,6,7,9,10,11,13,16,20]