Java进阶ch4 希尔排序

基本思想：先将待排序序列分割为若干子序列，分别进行直接插入排序，增量逐渐减小，直到增量减为1，此时相当于对全体记录进行直接插入排序。

private void shellSort(int[] a) {
    int dk = a.length / 2;
    while (dk >= 1) {
        ShellInsertSort(a, dk);
        dk = dk / 2;
    }
}

private void ShellInsertSort(int[] a, int dk) {
    // 类似插入排序，插入排序增量是1
    for (int i = dk; i < a.length; i++) {
        if (a[i] < a[i - dk]) {
            // a[i - dk] > a[i]需交换
            int j;
            int x = a[i]; // x是待插入元素
            a[i] = a[i - dk];
            for (j = i - dk; j >= 0 && x < a[j]; j = j - dk) {
                a[j + dk] = a[j];
            }
            a[j + dk] = x; // 插入
        }
    }
}

本文作者： Yao Zhu
发布时间： 2019-12-08
最后更新： 2019-12-08
本文链接： https://juoyo.github.io/posts/c04bd42a.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信