DS-07-05 希尔排序

408 > ### 数据结构 > #### 希尔排序（Shell Sort）

---

一、定位信息

维度	内容
章节归属	第7章 排序
知识单元编号	DS-07-05
前置知识	DS-07-02 插入排序
后续衔接	DS-07-09 排序算法综合对比
考试大纲要求	掌握希尔排序的算法思想、实现及性能分析
预计学习时长	30分钟

---

二、知识点讲解

1. 基本思想

希尔排序（Shell Sort）又称缩小增量排序，是插入排序的一种高效改进版本。其核心思想是：

1. 将待排序序列按增量序列分成若干个子序列
2. 对每个子序列分别进行直接插入排序
3. 逐步缩小增量，重复上述过程
4. 当增量减至 1 时，对整个序列做一次直接插入排序，排序完成

希尔排序的关键洞察：直接插入排序在序列基本有序时时间复杂度接近 O(n)，而当 n 较小时效率也较高。希尔排序通过先让序列"大致有序"（大增量时的分组排序），最后用小增量（特别是增量为 1 时）做最终整理，从而提高效率。

2. 增量序列

常用的增量序列：

• Shell 原始序列：n/2, n/4, …, 1（每次折半），最坏情况 O(n²)
• Hibbard 序列：2^k - 1（即 1, 3, 7, 15, …），最坏情况 O(n^{3/2})
• Sedgewick 序列：1, 5, 19, 41, 109, …，最坏情况 O(n^{4/3})

408 考试中通常使用 Shell 原始序列（每次折半）。

3. 伪代码实现

void ShellSort(ElementType A[], int n) {
    // 希尔排序，A[0..n-1]
    int i, j, d;        // d 为增量
    ElementType temp;
    for (d = n / 2; d >= 1; d /= 2) {  // 增量序列：n/2, n/4, ..., 1
        // 对每个增量 d，进行一趟希尔排序
        // 相当于对 d 个子序列分别做直接插入排序
        for (i = d; i < n; i++) {  // 从第 d 个元素开始
            if (A[i].key < A[i-d].key) {  // 需要插入
                temp = A[i];  // 暂存待插入元素
                for (j = i - d; j >= 0 && A[j].key > temp.key; j -= d) {
                    A[j+d] = A[j];  // 比 temp 大的元素后移 d 位
                }
                A[j+d] = temp;  // 插入到正确位置
            }
        }
        // 一趟结束后，所有间隔为 d 的子序列各自有序
    }
    // d=1 时退化为直接插入排序，但此时序列已基本有序
}

4. 过程示例

对序列 (49, 38, 65, 97, 76, 13, 27, 49', 55, 04)，n=10：

第 1 趟（d=5）：分为 5 组

• (49, 13), (38, 27), (65, 49'), (97, 55), (76, 04)
• 各组内插入排序：(13, 27, 49', 55, 04, 49, 38, 65, 97, 76)

第 2 趟（d=2）：分为 2 组

• 奇数位：(13, 49', 04, 65, 76) → (04, 13, 49', 65, 76)
• 偶数位：(27, 55, 49, 38, 97) → (27, 38, 49, 55, 97)
• 合并后大致有序

第 3 趟（d=1）：退化为直接插入排序

• 此时序列已基本有序，直接插入排序接近 O(n)

5. 时间复杂度分析

增量序列	最好	最坏	平均
Shell（n/2, n/4, …, 1）	O(n log n)	O(n²)	O(n^{1.3}) ~ O(n²)
Hibbard（1, 3, 7, 15, …）	O(n log n)	O(n^{3/2})	O(n^{5/4})
Sedgewick	O(n log n)	O(n^{4/3})	O(n^{7/6})

Shell 序列的最坏情况：当 n 是 2 的幂时，最坏情况时间复杂度为 O(n²)。

希尔排序的平均时间复杂度至今未精确求出，这与增量序列的选择密切相关。408 中通常考查的是 Shell 原始序列的情况。

6. 空间复杂度

O(1)，原地排序。

7. 稳定性

不稳定。分组排序过程中，相同关键字可能被分到不同组，在不同的插入排序中位置发生变化。

反例：序列 [5, 5, 3]，d=2 时分组 (5, 3) 和 (5)，排序后 (3, 5, 5)，两个 5 的相对顺序改变了。

---

8. 希尔排序 vs 直接插入排序 对比表

对比维度	直接插入排序	希尔排序
基本思想	逐个插入有序区	分组插入 + 缩小增量
增量	固定为 1	递减序列，最终为 1
最好时间	O(n)	O(n log n)
最坏时间	O(n²)	O(n²)（Shell 序列）
平均时间	O(n²)	O(n^{1.3}) 左右
空间复杂度	O(1)	O(1)
稳定性	稳定	不稳定
核心改进	—	让序列先大致有序，减少插入排序的移动次数

---

三、记忆辅助

1. 希尔排序 = 缩小增量 + 分组插入排序：先粗排（大增量），后细排（小增量），最后 d=1 精排
2. 增量序列最终必须为 1：否则最后一趟不能保证全局有序
3. 不稳定的原因：分组导致相同关键字在不同组中处理，打破了原有顺序
4. Shell 序列的缺陷：相邻增量有公因子（如 8 和 4 有公因子 4），导致重复比较。Hibbard 序列改进了这一点
5. 时间复杂度的记忆：Shell 序列最坏 O(n²)，平均约 O(n^{1.3})；408 考试重点考查 Shell 序列

---

四、例题精解

例题 1：希尔排序过程模拟

题目：对序列 (8, 5, 9, 3, 7, 1, 6, 2) 使用希尔排序（增量序列 d = 4, 2, 1），写出每趟排序结果。

第一步：审题 n = 8，增量序列为 4, 2, 1，需要写出每趟排序后的序列。

第二步：逐趟模拟

初始序列：[8, 5, 9, 3, 7, 1, 6, 2]

第 1 趟（d=4）：分为 4 组

• 组 1：(8, 7) → 插入排序 → (7, 8)
• 组 2：(5, 1) → 插入排序 → (1, 5)
• 组 3：(9, 6) → 插入排序 → (6, 9)
• 组 4：(3, 2) → 插入排序 → (2, 3)
• 结果：[7, 1, 6, 2, 8, 5, 9, 3]

第 2 趟（d=2）：分为 2 组

• 组 1（偶数位）：(7, 6, 8, 9) → 插入排序 → (6, 7, 8, 9)
• 组 2（奇数位）：(1, 2, 5, 3) → 插入排序 → (1, 2, 3, 5)
• 结果：[6, 1, 7, 2, 8, 3, 9, 5]

第 3 趟（d=1）：直接插入排序

• 此时序列基本有序，直接插入排序效率高
• 结果：[1, 2, 3, 5, 6, 7, 8, 9]

第三步：解答

• d=4 后：[7, 1, 6, 2, 8, 5, 9, 3]
• d=2 后：[6, 1, 7, 2, 8, 3, 9, 5]
• d=1 后：[1, 2, 3, 5, 6, 7, 8, 9]

第四步：总结 希尔排序每趟让序列更有序一些，最后一趟 d=1 时虽然退化为直接插入排序，但由于序列已基本有序，实际效率接近 O(n)。

---

例题 2：希尔排序的不稳定性分析

题目：对序列 (5₁, 5₂, 3) 进行希尔排序（d=2, 1），分析排序后两个 5 的相对顺序。

第一步：审题 用下标区分两个相同的 5，检验希尔排序是否保持稳定。

第二步：逐趟模拟

初始序列：[5₁, 5₂, 3]

第 1 趟（d=2）：分为 2 组

• 组 1：(5₁, 3) → 插入排序 → (3, 5₁)
• 组 2：(5₂) → 无需排序
• 结果：[3, 5₂, 5₁]

第 2 趟（d=1）：直接插入排序

• 序列 [3, 5₂, 5₁] 已基本有序，比较 5₂ 和 5₁
• 5₂ ≤ 5₁（相等时不交换），保持 [3, 5₂, 5₁]

第三步：解答 最终序列为 [3, 5₂, 5₁]。原始序列中 5₁ 在 5₂ 之前，排序后 5₁ 在 5₂ 之后，相对顺序改变，希尔排序不稳定。

第四步：总结 希尔排序的不稳定性源于分组过程。相同关键字被分到不同组后，在各自的插入排序中可能被移动到不同位置。

---

五、考情分析

年份	题型	考点	难度
中频	选择题	希尔排序的过程和复杂度	★★☆
中频	分析题	希尔排序的趟数和增量序列	★★★
低频	选择题	希尔排序的不稳定性	★★☆

命题趋势：

• 希尔排序的考查频率低于快排和堆排，但属于常考知识点
• 常以选择题形式考查增量序列、时间复杂度、稳定性
• 偶尔以分析题考查具体排序过程

---

六、易错点

1. 增量序列的最终值必须为 1：如果增量序列不包含 1，排序不能保证全局有序
2. 分组排序不是独立的：虽然每趟对多个子序列分别排序，但它们共享同一个数组
3. 时间复杂度的不确定性：希尔排序的平均时间复杂度至今没有精确结论，不同增量序列结果不同
4. Shell 序列 vs Hibbard 序列：Shell 序列最坏 O(n²)，Hibbard 序列最坏 O(n^{3/2})，考试中通常默认 Shell 序列
5. 希尔排序的不稳定性：不要因为基于插入排序（稳定）就认为希尔排序也稳定

---

七、来源标注

• 《数据结构（C语言版）》严蔚敏，第10.2节 希尔排序
• 《数据结构》王道考研，第7章 7.2节 希尔排序
• 408考试大纲：数据结构部分-希尔排序
• Donald L. Shell, "A High-Speed Sorting Procedure," Communications of the ACM, 1959