数据结构--希尔排序

希尔排序

思想：让数组越来越有序，不能只处理相邻的逆序对
对元素间距为n/2的所有数组做插入排序
对元素间距为n/4的所有数组做插入排序
对元素为n/8的所有数组做插入排序
...
对元素间距为1的所有数组做插入排序

代码示例

    public static <E extends Comparable<E>> void sort(E[] data){

        // h : ......8,4,2,1 步长序列
        int h = data.length/2; //子数组元素间隔为h
        while ( h >= 1 ){
            //每个子数组起始的位置
            for (int start = 0; start < h; start++) {
                //对子数组data[start, start + h, start + 2h..]插入排序
                //i = start + h 从第二个元素开始看 是否需要插入到前面
                for (int i = start + h; i < data.length; i+= h) {
                    E t = data[i];
                    int j;
                    for (j = i; j - h >= 0 && t.compareTo(data[j - h]) <0; j -= h)
                        data[j] = data[j - h];
                    
                    //执行了 j -= h 
                    data[j] = t;
                }
            }
            h /= 2;
        }
    }

    //优化1 代码优化 时间复杂度没有优化
    public static <E extends Comparable<E>> void sort2(E[] data) {

        int h = data.length / 2; //子数组元素间隔为h
        while (h >= 1) {
            //对子数组data[h, n)插入排序
            //i = h 从第二个元素开始看 是否需要插入到前面
            for (int i = h; i < data.length; i++) {
                E t = data[i];
                int j; //需要插入的位置
                for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h)
                    data[j] = data[j - h];

                //执行了 j -= h 
                data[j] = t;
            }
            h /= 2;
        }
    }

    //优化2 步长序列 h: ....8,4,2,1 改变步长序列可以优化希尔排序性能 不同的步长序列。复杂度分析不同
    public static <E extends Comparable<E>> void sort3(E[] data) {

        int h = 1;
        while (h < data.length) h = h * 3 + 1;
        while (h >= 1) {
            //对子数组data[h, n)插入排序
            //i = h 从第二个元素开始看 是否需要插入到前面
            //连续处理 h h+1 h+2...
            for (int i = h; i < data.length; i++) {
                E t = data[i];
                int j;
                for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h)
                    data[j] = data[j - h];

                //执行了 j -= h 
                data[j] = t;
            }
            h /= 3;
        }
    }

//ShellSort, n = 100000: 0.051397 s
//InsertionSort, n = 100000: 10.049346 s
//MergeSort, n = 100000: 0.061452 s

//ShellSort, n = 1000000: 0.933648 s
//MergeSort, n = 1000000: 0.424324 s

//在数据不是非常大的时候 ShellSort 优于其他  但是数据较大的时候相反

时间复杂度

在O(nlogn) O(n^2) 之间

稳定性

排序前相等的俩个元素，排序后相对位置不变。
希尔排序是不稳定的，元素位置跳跃。