首页/数据结构/07-sorting/希尔排序 🔗 在 Obsidian 中打开
数据结构 · 07-sorting

希尔排序

重要度 ★★ 数据结构/排序排序插入排序408考研
速查
希尔排序（Shell Sort，缩小增量排序）是直接插入排序的改进：按递减增量序列将序列分成若干子序列分别插入排序，最后一趟增量必为 1。时间复杂度与增量序列有关（一般 $O(n^{1.3})$），不稳定，只适用于顺序表。

核心概念 ▾

希尔排序由 Donald Shell 于 1959 年提出，是对直接插入排序的改进。其核心思路：

  • 直接插入排序对基本有序序列效率很高（最好 $O(n)$）
  • 希尔排序通过分组预排序使序列逐渐基本有序
  • 最后一趟增量 $d=1$，即对整个序列做直接插入排序，此时效率最高
关键特性
  1. 不稳定
  2. 只适用于顺序表，不适合链表
  3. 时间复杂度与增量序列选择有关
  4. 最后一趟前不能保证元素已在最终位置

算法步骤 ▾

  1. 选择增量序列 $d[1],d[2],\dots,d[t]$，其中 $d[t]=1$
  2. 对每个增量 $d[k]$（从大到小）：将序列分成 $d[k]$ 个子序列，每个子序列由相隔 $d[k]$ 个位置的元素组成
  3. 对每个子序列分别做直接插入排序
  4. 当 $d[k]=1$ 时，对整个序列做直接插入排序，完成

增量序列常见选择：经典 $d = n/2, n/4, \dots, 1$；Hibbard $1,3,7,15,\dots,2^k-1$；Sedgewick $1,5,19,41,109,\dots$

代码实现 ▾

void ShellSort(int A[], int n) {
    int i, j, d, temp;
    for (d = n / 2; d >= 1; d /= 2) {       // 初始增量 n/2，每次减半
        for (i = d; i < n; i++) {
            if (A[i] < A[i - d]) {
                temp = A[i];
                for (j = i - d; j >= 0 && A[j] > temp; j -= d)
                    A[j + d] = A[j];         // 子序列内后移（步长 d）
                A[j + d] = temp;
            }
        }
    }
}

手算示例 ▾

对 {49, 38, 65, 97, 76, 13, 27, 49*}，初始 $d = 8/2 = 4$：

第一趟（d=4）

4 个子序列：{49,76}、{38,13}、{65,27}、{97,49*}，分别插入排序 → 49, 13, 27, 49*, 76, 38, 65, 97

第二趟（d=2）

2 个子序列：{49,27,76,65}、{13,49*,38,97} → 27, 13, 49, 38, 65, 49*, 76, 97

第三趟（d=1）

整体插入排序 → 13, 27, 38, 49, 49*, 65, 76, 97

时间 / 空间复杂度与稳定性 ▾

情况时间复杂度说明
最坏$O(n^2)$希尔增量 $n/2,n/4,\dots,1$
一般$O(n^{1.3})$希尔增量序列
Sedgewick$O(n^{4/3})$Sedgewick 增量
空间$O(1)$原地排序
稳定性希尔排序不稳定。原因：相同元素可能被分到不同子序列中排序，打乱原有相对顺序。反例 {3, 1, 3*, 2}。

易错点 ▾

注意
  1. 希尔排序不稳定
  2. 最后一趟增量必须为 1
  3. 不适合链表（需按增量随机访问）
  4. 时间复杂度一般 $O(n^{1.3})$，最坏 $O(n^2)$
  5. 最后一趟前不能保证元素在最终位置

核心结论 ▾

必背希尔排序是直接插入排序的改进；不稳定；时间复杂度与增量序列有关（一般 $O(n^{1.3})$）；空间 $O(1)$；只适用于顺序表；最后一趟增量必为 1；最后一趟前不能保证元素在最终位置。

记忆卡片 ▾

为什么不稳定？
相同元素可能被分到不同子序列，打乱相对顺序。
与直接插入排序关系？
是直接插入排序的改进，靠分组预排序使序列基本有序。
时间复杂度？
与增量序列有关；希尔增量最坏 $O(n^2)$，一般 $O(n^{1.3})$。
最后一趟增量是多少？
必须是 1，确保最终整体有序。

交互动画 · 希尔排序逐增量 ▾

点击「下一增量」按 d=4 → d=2 → d=1 分组插入排序
同色块属于同一子序列（相隔增量 d 的位置）；每步对各子序列做插入排序。

相关知识点

（暂无关联知识点）