zhengrenzhe's blog   About

希尔排序

插入排序虽然较选择排序效率有了大幅提升,但还是不够,因为它一次只能移动一个元素。假设有一序列长度为 N 要从小到大排序,其最小值在序列的末尾,那就需要 N-1 次才能将它移动到最前面,效率有些低。

由此就诞生了希尔排序,它是插入排序的改进版本,解决了插入排序每次只能移动一个元素的问题。

假设有一数组要进行从小到大的排序:

const arr = [5, 2, 8, 3, 9, 4, 7, 1, 6];

如果使用插入排序,则需要对数组进行遍历,遍历过程中将当前元素插入到左边已经排好序的序列中的合适位置,当遍历至数字 1 处时,arr是这样的:

[ 2, 3, 4, 5, 7, 8, 9, 1, 6 ]

要将 1 移动到最左端,需要交换 7 次,对于一个大型序列而言这是不可接受的。希尔排序的重点就是要提升交换的效率,尽可能的使 1 使用最少的步骤移动到最左端,那么它是怎么做的呢?

首先,希尔排序将原始序列看作几个跨度为 h 的子序列的组合,这称为 h有序数组,在上例中,如果设跨度为4,那么 h 有序数组即为:


const arr    = [5, 2, 8, 3, 9, 4, 7, 1, 6];

const child1 = [5,          9,          6];
const child2 = [   2,          4,        ];
const child3 = [      8,          7,     ];
const child4 = [         3,          1,  ];

对这四个子序列分别使用插入排序,完成后将其组合:

const child1 = [5,          6,          9];
const child2 = [   2,          4,        ];
const child3 = [      7,          8,     ];
const child4 = [         1,          3,  ];

arr = [5, 2, 7, 1, 6, 4, 8, 3, 9];

这一下就把 1 和 6 移动了 4 位,虽然把 3 搞到后面去了,但我们下一步就能弥补回来。

接着设跨度为 2,经过上面同样的步骤产生的新序列为:

arr = [1, 2, 4, 5, 3, 7, 8, 6, 9];

最后设跨度为 1,这样就退化为插入排序,由这一步对上一步的产生的结果做最后的排序。在整个希尔排序过程中,交换次数为 3 + 3 + 4 = 10 次,如果使用插入排序则需要 18 次,这是一个巨大的提升。

在希尔排序中,步长序列是一个重要的参数,不同的步长参数会有不同的效果,在上例中,我们的步长序列为 [4 2 1],也就是由希尔排序的作者 Donald Shell 所提出的:

$$[\frac{N}{2}], [\frac{N}{4}], \cdots, 1$$

它在最坏情况下时间复杂度为 $\theta(N^2)$,更多的步长序列可以在wikipedia找到。

最后让我们用代码来实现它吧!

import { swap } from "./tools";

export default function sort<T>(items: T[], cmp = (a: T, b: T) => a > b) {
    const length = items.length;
    let h = Math.floor(length / 2); // 初始步长为 N/2

    // 对每个h进行处理,直到步长为1 ,此时退化为插入排序
    while (h >= 1) {
        // 将当前步长作为初始索引开始向后遍历,代码中并未进行可见的子序列切割与合并
        // 而是依靠步长作为索引进行隐式的切割
        let index = h;
        while (index < length) {
            let jIndex = index;

            // 这里判断 jIndex >= h 是因为当前步长内的第一次遍历是以步长作为索引开始的,
            // 需要通过它来防止数组越界
            // 这一层循环实际上就是插入排序的内层循环,只不过比较的是间隔为 h 的两个元素,
            // 通过它来进行隐式的子序列切割与排序
            while (jIndex >= h && cmp(items[jIndex], items[jIndex - h])) {
                swap(items, jIndex, jIndex - h);
                jIndex -= h;
            }

            index++;
        }

        h = Math.floor(h / 2);
    }

    return items;
}

← 选择与插入排序  归并排序 →