希尔排序

定义与基本思想

希尔排序（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

时间复杂度分析

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

练习题

练习 1

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

参考答案

解题思路：比较分组插入与直接插入。

详细步骤：

1. 希尔排序先分组插入，逐步缩小增量
2. 直接插入每次只插入一个元素

答案：希尔排序分组插入，效率高于直接插入。

练习 2

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

参考答案

解题思路：考查复杂度和空间。

详细步骤：

1. 时间复杂度 $O(n\log n)$（最好），$O(n^2)$（最坏）
2. 空间复杂度 $O(1)$

答案：时间 $O(n\log n)$~$O(n^2)$，空间 $O(1)$。