数据结构与算法（第二季）：希尔排序（Shell Sort）

希尔排序（Shell Sort）

一、概念

• 希尔排序把序列看作一个矩阵，分为m列，逐列进行排序。
• m从某个整数逐渐减为1，当m为1时，整个序列将完全有序。因此也被称为递减增量排序。
• 矩阵的列数取决于步长序列，如果步长序列为【1，5，19，41，109...】就代表依次分为109列，41列，19列，5列，1列进行排序。不同的步长序列，执行效率也不同。

二、实例

1、实例一

• 希尔本人给出的步长序列是n/2^k，比如n为16，k为2时，步长序列是【1，2，4，8】。

image

• 分为8列进行排序。

image

• 逐列进行排序，必须16和8这一列排序，则8在上16在下。

image

• 最终输出的结果为：

image

• 接着分为4列进行排序。

image

• 得到的结果为：

image

• 接着分为2列进行排序。

image

• 分为一列排序。

image

• 总结：从8列变为1列的过程中，逆序对的数量在逐渐减少。
• 因此希尔排序底层一般使用插入排序对每一列进行排序。

2、实例二

• 假设有11个元素，步长序列是【1，2，5】。

image

• 假设元素在第 col 列、第 row 行，步长（总列数）是 step
• 那么这个元素在数组中的索引是 col + row * step
• 比如 9 在排序前是第 2 列、第 0 行，那么它排序前的索引是 2 + 0 * 5 = 2
• 比如 4 在排序前是第 2 列、第 1 行，那么它排序前的索引是 2 + 1 * 5 = 7

三、代码实现

• 首先需要一个生成步长序列的函数。

private List<Integer> shellStepSequence() {
    List<Integer> stepSequence = new ArrayList<>();
    int step = array.length;
    while ((step >>= 1) > 0) {
        stepSequence.add(step);
    }
    return stepSequence;
}
复制代码

• 排序代码：

/**
 * 分成step列进行排序
 */
private void sort(int step) {
    // 一共有多少列，就排多少次
    // col : 第几列，column的简称
    for (int col = 0; col < step; col++) { // 对第col列进行排序
        // 每一列元素的索引为：col、col+step、col+2*step、col+3*step
        // 插入排序
        for (int begin = col + step; begin < array.length; begin += step) {
            int cur = begin;
            while (cur > col && cmp(cur, cur - step) < 0) {
                swap(cur, cur - step);
                cur -= step;
            }
        }
    }
}
复制代码

四、最好的步长序列

• 目前已知的最好的步长序列，最坏情况时间复杂度是O(n^4/3)。

image

private List<Integer> sedgewickStepSequence() {
    List<Integer> stepSequence = new LinkedList<>();
    int k = 0, step = 0;
    while (true) {
        if (k % 2 == 0) {
            int pow = (int) Math.pow(2, k >> 1);
            step = 1 + 9 * (pow * pow - pow);
        } else {
            int pow1 = (int) Math.pow(2, (k - 1) >> 1);
            int pow2 = (int) Math.pow(2, (k + 1) >> 1);
            step = 1 + 8 * pow1 * pow2 - 6 * pow2;
        }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
}