希尔排序

定义与基本思想

希尔排序（Shell Sort）是插入排序的改进版，也称“缩小增量排序”。其基本思想是：先将整个序列按一定增量分组，对每组分别进行插入排序，然后逐步缩小增量，最终整体插入排序。

希尔排序演示

231218345423

当前增量 gap: 4

下一步

算法描述

1. 选定一个初始增量 $gap$，将序列分为若干组
2. 对每组分别进行插入排序
3. 缩小增量 $gap$，重复分组和排序
4. 当 $gap=1$ 时，整体插入排序，排序完成

伪代码如下：

for gap = n/2; gap >= 1; gap = gap/2:
    for i = gap to n-1:
        key = A[i]
        j = i - gap
        while j >= 0 and A[j] > key:
            A[j+gap] = A[j]
            j = j - gap
        A[j+gap] = key

代码实现

void ShellSort(int A[], int n) {
    // 增量序列：n/2, n/4, ..., 1（可换用 Hibbard 等更优序列）
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        // 对每个分组进行直接插入排序
        for (int i = gap; i < n; i++) {
            int key = A[i];
            int j = i - gap;
            while (j >= 0 && A[j] > key) {
                A[j + gap] = A[j];  // 组内元素后移 gap 位
                j -= gap;
            }
            A[j + gap] = key;
        }
    }
}

增量序列的选择

• 常用序列：$n/2, n/4, \ldots, 1$（简单但最坏 $O(n^2)$）
• Hibbard 序列：$2^k-1, \ldots, 15, 7, 3, 1$，最坏 $O(n^{3/2})$
• Sedgewick 序列：$1, 5, 19, 41, 109, \ldots$，性能更好

增量序列的选择直接影响希尔排序的效率，是研究重点。

时间复杂度分析

• 最好情况：$O(n\log n)$
• 最坏情况：$O(n^2)$（与增量序列有关）
• 空间复杂度：$O(1)$
• 稳定性：不稳定排序

习题

习题 1

简述希尔排序的基本思想及其与直接插入排序的区别。

习题 2

希尔排序的时间复杂度和空间复杂度分别是多少？

上一章节选择排序介绍选择排序的基本思想、算法流程、复杂度分析及典型习题。

下一章节快速排序介绍快速排序的基本思想、算法流程、复杂度分析及典型习题。