当前位置：首页 > ds >正文

数据结构：希尔排序 (Shell Sort)

ds 2025/9/4 23:03:55

从“改进插入排序”的思路开始

希尔排序的完整策略：

手动模拟全过程

代码的逐步完善

第一阶段：搭建外层循环框架（控制 gap）

第二阶段：实现“分组插入排序”（中间循环）

第三阶段：实现核心的“插入”逻辑（内层循环）

复杂度与特性分析

时间复杂度 (Time Complexity)

空间复杂度 (Space Complexity)

稳定性 (Stability)

我们来探讨一个非常巧妙的排序算法——希尔排序 (Shell Sort)。它也被称为缩小增量排序 (Diminishing Increment Sort)。

理解希尔排序的关键，在于先理解它要“改进”的那个算法的优缺点。

从“改进插入排序”的思路开始

我们先回顾一下插入排序 (Insertion Sort)：

优点：当一个数组几乎有序时，插入排序的效率极高，接近 O(n)。
致命弱点：当一个非常小的元素处在数组的末尾时，插入排序的效率极低。因为它每次只能将元素移动一个位置，要把这个小元素挪到数组开头，需要进行大量的、一步一步的移动。

这就启发我们思考一个根本性的问题：有没有办法让元素可以进行“长距离”的移动？

如果我们可以先通过某种方式，将那个在末尾的小元素，一次性地“跳”到数组的前半部分，那么后续的排序就会轻松很多。

💡唐纳德·希尔 (Donald Shell) 的天才构想：

不要直接对整个数组进行插入排序。我们可以先设定一个比较大的步长（或称增量/间隔，gap），比如 gap = 4。然后，我们不把数组看作一个整体，而是看作4个独立的“子数组”：

由 arr[0], arr[4], arr[8], ... 构成的子数组。
由 arr[1], arr[5], arr[9], ... 构成的子数组。
由 arr[2], arr[6], arr[10], ... 构成的子数组。
由 arr[3], arr[7], arr[11], ... 构成的子数组。

然后，我们对这4个子数组分别进行插入排序。

✅这样做有什么好处？

在对 {arr[0], arr[4], arr[8]} 进行排序时，arr[8] 的元素如果比 arr[0] 小，它们就可以一次性交换！这实现了一次跨度为8的“长距离移动”。

这个过程完成后，数组并没有完全排好序，但它变得比原来“更有序”了。那些非常小的元素，通过这种大步长的交换，被快速地移动到了数组的前端。

希尔排序的完整策略：

选择一个大的 gap 值，对所有“gap-子数组”进行插入排序。
缩小 gap 的值，例如减半，重复第1步。
不断缩小 gap，直到最后 gap = 1。

当 gap = 1 时，我们做的是什么？就是对整个数组进行一次普通的插入排序。但这里的“魔法”在于：

经过前面几轮大 gap 的宏观调控，当 gap 最终为1时，这个数组已经几乎是有序的了！而我们知道，对一个几乎有序的数组进行插入排序，效率是极高的。

这个“先宏观调控，再逐步细化，最后精准完成”的思路，就是希尔排序的第一性原理。

下面我们以一个数组为例，详细展示希尔排序的全过程。

手动模拟全过程

假设我们有以下数组： [9, 1, 5, 2, 8, 3, 7, 4, 6, 0]

为了简化演示，我们使用 Hibbard 增量序列：2^k − 1。假设初始增量为 2^3 − 1=7。

第1轮排序：增量 gap = 4

我们以4为间隔将数组分为4个子序列：

子序列1：[9, 8, 6]
子序列2：[1, 3, 0]
子序列3：[5, 7]
子序列4：[2, 4]

对每个子序列进行插入排序：

子序列1：[9, 8, 6] 排序后为 [6, 8, 9]
子序列2：[1, 3, 0] 排序后为 [0, 1, 3]
子序列3：[5, 7] 排序后为 [5, 7]
子序列4：[2, 4] 排序后为 [2, 4]

将排序后的子序列重新放回原数组，得到：

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

第2轮排序：增量 gap = 2

现在，我们将增量减小为2。我们将数组分为两个子序列：

子序列1：[6, 5, 8, 7, 9]
子序列2：[0, 2, 1, 4, 3]

对每个子序列进行插入排序：

子序列1：[6, 5, 8, 7, 9] 排序后为 [5, 6, 7, 8, 9]
子序列2：[0, 2, 1, 4, 3] 排序后为 [0, 1, 2, 3, 4]

将排序后的子序列重新放回原数组，得到：

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

第3轮排序：增量 gap = 1

最后，我们将增量减小为1。此时，希尔排序就退化为标准的插入排序。我们对整个数组进行排序，因为之前的排序已经让数组变得“大致有序”，所以这一次的插入排序效率会非常高。

对数组 [5, 0, 6, 1, 7, 2, 8, 3, 9, 4] 进行插入排序。

0 插入到 5 前面：[0, 5, 6, 1, 7, 2, 8, 3, 9, 4]
1 插入到 5 前面：[0, 1, 5, 6, 7, 2, 8, 3, 9, 4]
2 插入到 6 前面：[0, 1, 2, 5, 6, 7, 8, 3, 9, 4]
3 插入到 8 前面：[0, 1, 2, 3, 5, 6, 7, 8, 9, 4]
4 插入到 9 前面：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

经过这一轮排序，数组最终变为完全有序：

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

总结一下，希尔排序通过 “先宏观，后微观” 的方式，先将数组进行大跨度分组排序，使其接近有序状态，然后再逐步减小增量，最后以小增量（1）进行精细排序，从而大大提高了效率。

代码的逐步完善

第一阶段：搭建外层循环框架（控制 `gap`）

希尔排序的“总指挥”是一个控制 gap 变化的循环。最简单的 gap 序列就是 希尔本人提出的 n/2, n/4, ..., 1。

#include <iostream>void shellSort(int arr[], int n) {// 这个外层循环控制着步长 gap 的变化// 从 n/2 开始，每次减半，直到 gap 为 1for (int gap = n / 2; gap > 0; gap /= 2) {// 在这里，我们将对当前 gap 值下的所有子数组进行插入排序}
}

第二阶段：实现“分组插入排序”（中间循环）

对于一个固定的 gap，我们如何对所有子数组（例如 {arr[0], arr[4], ...} 和 {arr[1], arr[5], ...}）进行排序呢？

我们不需要真的把它们拆分出来。我们可以用一个统一的循环来处理。这个循环从第 gap 个元素开始，一直到数组末尾。arr[i] 就是我们每次要进行插入操作的“新牌”。

void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {// 这个中间循环，从 gap 开始，遍历整个数组// 它隐式地处理了所有交织在一起的子数组for (int i = gap; i < n; i++) {// 对于 arr[i]，我们需要将它插入到它所属的// 那个 gapped 子数组的正确位置// 例如，当 gap=4, i=5 时，// 我们要把 arr[5] 插入到 {arr[1], arr[5], ...} 这个子数组的正确位置}}
}

第三阶段：实现核心的“插入”逻辑（内层循环）

这一步几乎就是标准插入排序的翻版，但有一个关键区别：所有元素的移动和比较，都是以 gap 为步长，而不是以 1 为步长。

void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {// 1. 暂存待插入的元素 arr[i]int temp = arr[i];// 2. j 指向 arr[i] 的前一个同组元素int j;// 3. 在当前子数组中，为 temp 寻找插入位置//    比较和移动都是以 gap 为步长for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {// 如果前面的元素更大，就把它向后移动 gap 个位置arr[j] = arr[j - gap];}// 4. 将 temp 插入到找到的正确位置arr[j] = temp;}}
}

将这三层循环组合在一起，我们就得到了一个完整的、逻辑清晰的希尔排序实现。

复杂度与特性分析

希尔排序的分析是所有基础排序算法中最复杂的，因为它和 gap 序列的选择密切相关。

时间复杂度 (Time Complexity)

希尔排序的时间复杂度至今没有一个公认的、精确的数学公式，它取决于所使用的 gap 序列。
最坏情况：
- 使用希尔原始的 n/2 序列，最坏情况时间复杂度是 O(n^2)。在某些特殊构造的数据下，它会退化。
- 使用更优的 gap 序列（如 Hibbard 序列: 2^k−1 或 Sedgewick 序列），可以获得更好的最坏情况性能，例如 O(n^3/2) 或 O(n^4/3)。
平均情况：
- 平均性能也和 gap 序列有关，但通常远好于 O(n^2)。可以认为是介于 O(nlogn) 和 O(n^2) 之间的一个“亚二次方”级别。

📌关键点：我们无法像归并排序那样给出一个稳定的 O(nlogn) 保证，但它的实际表现通常比 O(n^2) 的插入、选择排序要快得多。

空间复杂度 (Space Complexity)

观察我们的代码，排序过程是在原数组上直接进行的。我们只使用了几个额外的变量（gap, i, j, temp）来辅助操作。
这些变量的数量是固定的，不随输入数组的大小 n 变化。
因此，希尔排序的空间复杂度是：O(1)
它是一个原地排序 (In-place Sort) 算法。

稳定性 (Stability)

希尔排序的核心操作涉及到长距离的元素交换。
例如，在数组 [5a, 5b, 1] 中，gap=2。
- 第一个子数组是 {5a, 1}。为了排序，5a 和 1 需要交换。
- 数组变为 [1, 5b, 5a]。
在这个过程中，5a “跳过”了 5b，跑到了它的后面。两个相等元素 5a 和 5b 的原始相对顺序被破坏了。
因此，希尔排序是不稳定的排序算法 (Unstable Sort)。