【数据结构】排序算法精讲 | 希尔排序全解：增量优化、性能跃升、实战剖析
【数据结构】排序算法精讲 | 希尔排序全解：增量优化、性能跃升、实战剖析
蒙奇D索隆
发布于 2025-12-28 08:58:56
发布于 2025-12-28 08:58:56
(希尔排序)
导读
大家好，很高兴又和大家见面啦！！！ 在上一篇内容中我们学习了 直接插入排序 的第一种优化：
- 查找优化：将 顺序查找 优化为 折半查找 ，从而提升算法的 查找 效率
这种将 折半查找 与 插入排序 相结合的 排序算法 就是 折半插入排序。 因为 顺序移动 的过程无法优化，就导致了 直接插入排序 与 折半插入排序 这两种 排序算法 都处于同一数量级 O(N^2) ，但是在数据规模庞大的情况下，折半插入排序 的算法效率优于 直接插入排序； 不管是 折半插入排序 还是 直接插入排序 它们都是有自己的优势：
- 直接插入排序 适用于数据规模较小或基本有序的情况，并且既能够在 顺序表 中使用，也能够在 链表 中使用
- 折半插入排序 适用于数据规模较大或无序的情况，并且仅适用于 顺序表
在数据规模上，正是因为这两种算法都处于同一数量级 O(N^2) ，这就使得二者在规模较小的 顺序表 时，效率基本一致，而 直接插入排序 的实现上会更加的简单，因此也就更加适用； 在数据是否有序上，二者对有序和无序的区别就非常明显：
- 数据基本有序： 直接插入排序 在 最好情况下 可以做到 O(N) 的量级 折半插入排序 则是因为 折半查找 的过程不受数据的初始状态影响，因此 最好情况下 也是有 O(N \log N) 的量级
- 数据基本无序： 直接插入排序 因为采用的是 顺序查找 因此其 查找操作 时间消耗上是处于 O(N^2) 的量级 折半插入排序 因为采用的是 折半查找 因此其 查找操作 时间消耗上是处于 O(N \log N) 的量级 由于双方的 移动操作 均为 顺序移动 ，因此双方整体的时间消耗均为 O(N^2) 这个量级
理解了这二者的区别后，下面我们就需要思考一个问题——有没有优于 折半插入排序 的 插入排序算法 呢？ 答案是肯定的，这就是我们今天要介绍的 希尔排序。 下面就让我们一起进入今天的内容吧！！！
一、基本概念
希尔排序（Shell Sort）又称为 缩小增量排序，是一种 先追求表中的元素部分有序，再逐步逼近全局有序 的 排序算法。 从前面的分析中可知，直接插入排序 在处理 正序 序列时，其 时间复杂度 可以从 O(N^2) 提升至 O(N)；而对于 小规模的数据 进行排序时，直接插入排序 与 折半插入排序 在时间消耗上基本没啥区别。正因如此，结合这两点优势，并将其加以改进，就得到了能够在处理 大规模的无序数据 以及 小规模的有序数据 时更加高效的 排序算法 —— 希尔排序
二、基本思想
希尔排序 的 基本思想 是：
- 先将待排序表分割成若干形如 L[i,i+d,i+2d,……,i+kd] 的 特殊子表，即将原表中相隔 增量 d 的记录组成一个 逻辑子表
- 对各个子表分别进行直接插入排序。
- 缩小增量d，重复上述过程，直到 d=1 为止。
简单的理解就是 希尔排序 是将一个 大规模 的 数据序列 分割成若干个 小规模 的 子序列，并对每一个 子序列 进行 直接插入排序 ，在这种情况下，即使每个 子序列 都 无序 ，那对应的时间消耗也不会太高； 当经过一轮处理后，数据整体就开始慢慢趋近 有序 ，这时只需要逐步增加 子序列 的 数据规模，并重复这一过程，就能够保证每一次的 直接插入排序 均是对 基本有序 的 子序列 执行，从而降低 排序 的 整体时间消耗； 这种思想也是对应着咱们的一句话—— 大事化小，小事化了 的这种 拆分思想 与 分治思想 的结合。 希尔排序正是拆分思想与分治哲学的一种巧妙结合，但更准确地说，是一种具有独创性的、非典型的应用。
三、排序过程
为了更好的感受 希尔排序 的 拆分 与 分治，接下来我们就以具体的实例来说明 希尔排序 的整个排序过程： 这里我们以初始序列 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 为例，通过 希尔排序 将该 降序序列 重新按 升序排列；
3.1 第一轮排序
这里总共有 11 个关键字，因此我们先以 增量 d = 5 进行分割，此时我们就得到了下面的这些 子序列：
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{10}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{5}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{0}$ |
PS: 这里我们以字体颜色作为区分，颜色相同的为同一组 子序列 中的元素；
按照 直接插入排序算法 对各个 子序列 进行排序，这里我们需要进行 6 趟排序，具体过程如下所示：
- 第一趟：10 > 510 右移，将 5 插入 10 这个位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{5}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{10}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{0}$ |
- 第二趟：9 > 49 右移，将 4 插入 9 这个位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{5}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{10}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{0}$ |
- 第三趟：8 > 38 右移，将 3 插入 8 这个位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{5}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{10}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{0}$ |
- 第四趟：7 > 27 右移，将 2 插入 7 这个位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{5}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{6}$ | $\textcolor{red}{10}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{1}$ | $\textcolor{red}{0}$ |
- 第五趟：6 > 16 右移，将 1 插入 6 这个位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{5}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{10}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{0}$ |
- 第六趟：10 > 010 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{5}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{10}$ |
5 > 05 右移，将 0 插入 5 这个位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{4}$ | $\textcolor{green}{3}$ | $\textcolor{orange}{2}$ | $\textcolor{black}{1}$ | $\textcolor{red}{5}$ | $\textcolor{blue}{9}$ | $\textcolor{green}{8}$ | $\textcolor{orange}{7}$ | $\textcolor{black}{6}$ | $\textcolor{red}{10}$ |
经过第一轮排序后，目前各个 子序列 已经做到了 局部有序；
3.2 第二轮排序
接下来我们再以 增量 d = 2 进行分割，此时我们就得到了下面的这些子序列
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
此时我们需要继续对各个 子序列 进行 直接插入排序，总共需要进行 9 趟排序，其具体过程如下所示：
- 第一趟：0 < 3
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第二趟：4 > 24 右移，将 2 插入到 4 的位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第三趟：3 > 13 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
0 < 11 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第四趟：4 < 5
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第五趟：3 < 9
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第六趟：5 < 8
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第七趟：9 > 79 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
3 < 77 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{10}$ |
- 第八趟：8 > 68 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{10}$ |
5 < 66 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{10}$ |
- 第九趟：9 < 10
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{blue}{2}$ | $\textcolor{red}{1}$ | $\textcolor{blue}{4}$ | $\textcolor{red}{3}$ | $\textcolor{blue}{5}$ | $\textcolor{red}{7}$ | $\textcolor{blue}{6}$ | $\textcolor{red}{9}$ | $\textcolor{blue}{8}$ | $\textcolor{red}{10}$ |
经过这一趟排序后，数据的 局部有序 已经更加明显，但是仍为达到 整体有序 的要求；
3.3 第三轮排序
这一轮我们将会采用 增量 d = 1 进行分割，此时我们就得到了下面这些子序列：
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{2}$ | $\textcolor{red}{1}$ | $\textcolor{red}{4}$ | $\textcolor{red}{3}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
这时我们需要的就是对其进行整体的 直接插入排序 ，总共需要进行 10 趟排序，具体的排序过程如下所示：
- 第一趟：0 < 2
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{2}$ | $\textcolor{red}{1}$ | $\textcolor{red}{4}$ | $\textcolor{red}{3}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第二趟：2 > 12 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{}$ | $\textcolor{red}{2}$ | $\textcolor{red}{4}$ | $\textcolor{red}{3}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
0 < 11 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{4}$ | $\textcolor{red}{3}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第三趟：2 < 4
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{4}$ | $\textcolor{red}{3}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第四趟：4 > 34 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
2 < 33 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第五趟：4 < 5
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第六趟：5 < 7
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{7}$ | $\textcolor{red}{6}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第七趟：7 > 67 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{}$ | $\textcolor{red}{7}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
5 < 66 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{6}$ | $\textcolor{red}{7}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第八趟：7 < 9
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{6}$ | $\textcolor{red}{7}$ | $\textcolor{red}{9}$ | $\textcolor{red}{8}$ | $\textcolor{red}{10}$ |
- 第九趟：9 > 89 右移
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{6}$ | $\textcolor{red}{7}$ | $\textcolor{red}{}$ | $\textcolor{red}{9}$ | $\textcolor{red}{10}$ |
7 < 88 插入到当前位置
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{6}$ | $\textcolor{red}{7}$ | $\textcolor{red}{8}$ | $\textcolor{red}{9}$ | $\textcolor{red}{10}$ |
- 第十趟：9 < 10
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
$\textcolor{red}{0}$ | $\textcolor{red}{1}$ | $\textcolor{red}{2}$ | $\textcolor{red}{3}$ | $\textcolor{red}{4}$ | $\textcolor{red}{5}$ | $\textcolor{red}{6}$ | $\textcolor{red}{7}$ | $\textcolor{red}{8}$ | $\textcolor{red}{9}$ | $\textcolor{red}{10}$ |
可以看到，经过这一轮排序后，序列已经从 局部有序 恢复到了 整体有序。 在 希尔排序 的这三轮排序中，每一轮的比较次数以及移动次数分别为：
- 第一轮排序：7 次比较，7 次移动
- 第二轮排序：12 次比较，4 次移动
- 第三轮排序：14 次比较，4 次移动
也就是说，整个排序过程我们只进行了 33 次比较，15 次移动，相比于直接对整体进行 直接插入排序 ，效率得到了显著提升；
四、C语言实现
4.1 准备工作
在实现 希尔排序 之前，我们需要先创建好三个文件：
- 排序算法头文件
Shell_Sort.h—— 用于进行排序算法的声明 - 排序算法实现文件
Shell_Sort.c—— 用于实现排序算法 - 排序算法测试文件
text.c—— 用于测试排序算法
4.2 函数三要素
与 直接插入排序 一样，希尔排序 只不过是在其基础上进行了分组优化因此我们这里的三要素只需要修改一下函数名即可：
// 插入排序——希尔排序
void ShellSort(ElemType* nums, int len) {
}4.3 排序对象的划分
希尔排序 是将 排序对象 以 增量 d 划分为多个 子序列，然后再对子序列进行 直接插入排序； 因此在希尔排序中存在两层划分；
- 第一层划分：按照 增量 d 划分为若干个 子序列，增量 d 我们可以采取 折半 的思想进行确定，即 d = \frac{len}{2}。之后的每一次重新分组，增量 d 继续 折半：
// 第一层划分
for (int d = len / 2; d >= 1; d /= 2) {
}- 第二层划分：按照 直接插入排序 的划分方式将 子序列 划分为三部分——左侧有序、待插入元素、右侧无序。这里我们还是以 左侧有序 的 右边界 为分界线进行 顺序遍历：
// 第二层划分
for (int i = 0; i < len - d; i++) {
ElemType key = nums[i + d]; // 记录待插入元素
}4.4 插入位置查找
在 希尔排序 中，我们对 待排序对象 的插入位置进行 查找 时采用的是 顺序查找 并且在 查找 的过程中完成 移动，具体实现如下所示：
// 查找与移动
int j = i; // 待插入元素下标
while (j >= 0 && nums[j] > key) {
nums[j + d] = nums[j];
j -= d;
}之所以是从 i 这个位置向左查找，就是因为我们使用的是 左侧有序子序列 的右边界为 遍历起点，或者说是 分界线，这里就不再多赘述；
4.5 待排序对象的插入
优于 希尔排序 需要以 增量 d 对 序列 进行分组，并对各分组的元素进行排序，因此我们需要执行快速的 读取 操作，显然这与 链表 不太相符，因此 希尔排序 同样只适用于 顺序表，因此其 插入 操作同样是 赋值操作；
// 插入
nums[j + d] = key;这里之所以是 j + d ，是因为当跳出循环时有两种情况：
j < 0：此时说明j + d这个位置是 子序列 的 左边界j >= 0 && nums[j] < key：此时说明j + d就是key需要插入的空位
因此我们在跳出循环后才会在 j + d 的位置进行 插入操作；
4.6 性能分析
- 空间效率：希尔排序 仅使用了 ElemType 大小的空间来记录 待插入元素，因此其 空间复杂度 为 O(1)
- 时间效率：希尔排序 的 时间复杂度 依赖于 增量序列 的函数，而该问题涉及到数学上尚未解决的难题，因此分析比较困难。 当 N 在某个特定范围时，希尔排序 的 时间复杂度 约为 O(N^{1.3}) 最坏情况下，希尔排序 的 时间复杂度 为 O(N^2)
- 稳定性：由于 希尔排序 采用的是 分组排序 策略，因此这就会导致 相同关键字的记录被划分到不同组，此时就有可能改变它们之间的相对次序，因此 希尔排序 是一种 不稳定的排序算法
- 适用性：希尔排序 仅适用于 顺序表
4.7 算法代码
完整代码如下所示：
// 算法头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <assert.h>
typedef int ElemType;
// 插入排序——希尔排序
void ShellSort(ElemType* nums, int len);
// 插入排序——折半插入排序
void BInsertSort(ElemType* nums, int len);
// 插入排序——直接插入排序
void InsertSort(ElemType* a, int len);
// 数组打印
void Print(ElemType* arr, int len);
// 折半插入排序测试
void test();
// 算法实现文件
#include "Shell_Sort.h"
// 插入排序——希尔排序
void ShellSort(ElemType* nums, int len) {
// 第一层划分
for (int d = len / 2; d >= 1; d /= 2) {
// 第二层划分
for (int i = 0; i < len - d; i++) {
ElemType key = nums[i + d]; // 记录待插入元素
// 查找与移动
int j = i; // 待插入元素下标
while (j >= 0 && nums[j] > key) {
nums[j + d] = nums[j];
j -= d;
}
// 插入
nums[j + d] = key;
}
}
}
// 插入排序——折半插入排序
void BInsertSort(ElemType* nums, int len) {
// 按左侧有序有边界进行划分
for (int i = 0; i < len - 1; i++) {
int key = nums[i + 1]; // 待排序对象
// 折半查找
int l = 0, r = i; // 折半查找的左右指针
while (l <= r) {
int m = (r - l) / 2 + l;
// 中间值 大于 目标值，目标值位于中间值左侧
if (nums[m] > key) {
r = m - 1; // 更新右边界
}
// 中间值 小于等于 目标值，目标值位于中间值右侧
else {
l = m + 1;
}
}
// 移动
for (int j = i; j >= l; j--) {
nums[j + 1] = nums[j];
}
// 插入
nums[l] = key;
}
}
//插入排序——直接插入排序
void InsertSort(ElemType* a, int len) {
//以左侧有序对象的起点作为分界线对排序对象进行划分
for (int i = 0; i < len - 1; i++) {
//记录需要排序的元素
ElemType key = a[i + 1];
//插入位置的查找
int j = i;//记录左侧有序元素的起点
//j < 0时表示查找完左侧所有元素
//a[j] <= key时表示找到了元素需要进行插入的位置
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];//元素向后移动
j -= 1;//移动查找指针
}
//插入元素
a[j + 1] = key;
}
}
// 数组打印
void Print(ElemType* arr, int len) {
printf("元素序列：");
for (int i = 0; i < len; i++) {
printf("%d\t", arr[i]);
}
printf("\n");
}
// 折半插入排序测试
void test() {
ElemType* arr1 = (ElemType*)calloc(100000, sizeof(ElemType));
assert(arr1);
ElemType* arr2 = (ElemType*)calloc(100000, sizeof(ElemType));
assert(arr2);
ElemType* arr3 = (ElemType*)calloc(100000, sizeof(ElemType));
assert(arr3);
ElemType* arr4 = (ElemType*)calloc(10, sizeof(ElemType));
assert(arr4);
// 设置伪随机数
srand((unsigned)time(NULL));
// 生成10w个随机数
for (int i = 0; i < 100000; i++) {
arr1[i] = rand() % 100000;
arr2[i] = arr1[i];
arr3[i] = arr1[i];
if (i < 10) {
arr4[i] = rand() % 100;
}
}
// 算法健壮性测试
printf("\n排序前：");
Print(arr4, 10);
ShellSort(arr4, 10);
printf("\n排序后：");
Print(arr4, 10);
// 算法效率测试
int begin1 = clock();
InsertSort(arr1, 100000);
int end1 = clock();
double time_used1 = ((double)(end1 - begin1)) / CLOCKS_PER_SEC;
printf("\n直接插入排序总耗时：%lf 秒\n", time_used1);
int begin2 = clock();
BInsertSort(arr2, 100000);
int end2 = clock();
double time_used2 = ((double)(end2 - begin2)) / CLOCKS_PER_SEC;
printf("\n折半插入排序总耗时：%lf 秒\n", time_used2);
int begin3 = clock();
ShellSort(arr3, 100000);
int end3 = clock();
double time_used3 = ((double)(end3 - begin3)) / CLOCKS_PER_SEC;
printf("\n 希尔排序总耗时：%lf 秒\n", time_used3);
free(arr1);
arr1 = NULL;
free(arr2);
arr2 = NULL;
free(arr3);
arr3 = NULL;
free(arr4);
arr4 = NULL;
}
// 算法测试文件
#include "Shell_Sort.h"
int main() {
test();
return 0;
}下面我们就来允许一下代码，简单测试一下：
从这次的测试结果中我们可以看到，在 10w 个数据规模下，三个完全一样的数组分别通过这三种排序算法进行排序时，希尔排序 的效率远超 直接插入排序 以及 折半插入排序 的算法效率；
结语
在今天的内容中我们介绍了插入排序家族中的 王牌算法 —— 希尔排序； 希尔排序 通过引入 增量 d 将原序列 拆分 成若干个 子序列，并对 子序列 采用 直接插入排序 算法，使得 直接插入排序 能够在自己的优势区——小规模和基本有序 将自己的优势发挥到极限； 但是因为 希尔排序 过于依赖 增量序列 ，这就导致了其 时间效率 无法准确描述，在 N 位于特殊范围内时，希尔排序 的 时间复杂度 能够达到 O(N^{1.3}) 这个级别，性能远超 直接插入排序 和 折半插入排序 的 O(N^2)； 插入排序 家族中的三种排序算法到此我们已经全部介绍完。通过在 10W 这个数据规模下的 排序效率 对比，我们可以得出结论：
- 在该规模下，希尔排序效率 \gg 折半插入排序效率 >
接下来我们将会开始学习第二种内部排序算法——交换排序。在这部分内容中，我们将通过交换排序算法，尽情感受其通过直接的比较与交换来逐步消除逆序对，从而让数据一步步迈向有序的独特魅力与智慧。 互动与分享
- 点赞👍 - 您的认可是我持续创作的最大动力
- 收藏⭐ - 方便随时回顾这些重要的基础概念
- 转发↗️ - 分享给更多可能需要的朋友
- 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题
感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号