专题进阶 · 排序算法推荐总顺序 · 第 29 / 148 课

把间隔插入排序拆成多条子序列,理解增量序列为何影响成本。

先学会这些,再进入本课 插入排序
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 排序算法

希尔排序Shell Sort

先按较大间隔做插入排序,再逐步缩小间隔;性能依赖增量序列。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

把间隔插入排序拆成多条子序列,理解增量序列为何影响成本。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

逆序数组中的小元素要向左移动很多次。能否先让它跨较远距离,再做精细调整?

02一步步得到方法

一个 gap 对应多条交错子序列

gap=3 时,下标 0,3,6,… 是一条子序列,1,4,7,… 是另一条。对每条子序列做插入排序后,数组是 gap-有序,而不是整体有序。不同子序列之间仍可能逆序。

随后缩小 gap,重复间隔插入。最后必须取 gap=1,此时就是普通插入排序,因此保证最终有序。前面的大步调整让小元素较快到达左侧,可能减少最后阶段的移动。

沿用插入排序的 key 思想

先保存 key=a[i],将同一子序列里比 key 大的元素每次右移 gap 个位置,直到找到插入点。判断 j>=gap 防止访问负下标;不能直接照搬 j>0。

本课使用 n//2 不断减半的简单增量。不同增量序列有不同理论界,不能把希尔排序统一写成 O(n log n)。本序列最坏时间可达 O(n²),实际效果需按输入和增量讨论。

把间隔排序理解为多条子序列

间隔 gap=3 时,下标0、3、6构成一条子序列,下标1、4、7构成另一条。每条都执行插入排序,让远处逆序提前跨越较大距离,随后逐渐缩小间隔。

最后必须包含 gap=1,才能保证全局有序。不同间隔序列的性能和理论界不同,不能用一个序列的界描述所有 Shell 排序;远距离移动也通常破坏稳定性。

03把一个小例子完全算清楚

[8,5,3,1],间隔依次为 2、1。

步骤计算与状态为什么这样做
gap=2,i=2比较 3 与 8,得 [3,5,8,1]子序列下标 0、2 有序
gap=2,i=3比较 1 与 5,得 [3,1,8,5]子序列下标 1、3 有序
gap=1插入 1、8、5,得 [1,3,5,8]现在才完成整体排序

窄屏可左右滑动表格,阅读完整计算与理由。

大间隔阶段建立的是局部顺序;最后一轮连接这些子序列。

04为什么这个方法成立

  1. 固定 gap 时,每次插入保持当前子序列前缀有序。
  2. 所有位置处理完后,整个数组 gap-有序。
  3. 最终 gap=1 覆盖完整数组,因而升序正确;前面各轮不会丢失元素。

05把推导翻译成代码

Python · 可独立运行的教学实现

def shell_sort(values):
    a = list(values)
    gap = len(a) // 2
    while gap:
        for i in range(gap, len(a)):
            key, j = a[i], i
            while j >= gap and a[j-gap] > key:
                a[j] = a[j-gap]
                j -= gap
            a[j] = key
        gap //= 2
    return a

逐个理解关键决定

j -= gap
只沿当前子序列回退。
gap //= 2
整数减半保证最后到 1,再到 0 退出。

06时间、空间与实现范围

本减半增量的保守最坏界 O(n²),不能套用其他增量序列的界。

核心辅助空间 O(1),返回副本的本实现额外 O(n);通常不稳定。

07改变条件,检查哪里会出错

gap>1 时有序就提前结束

只能证明各子序列有序,必须执行 gap=1。

间隔变小就自动保持稳定

远距离移动会跨过相同键,稳定性没有保证。

遗漏最终间隔1

较大间隔内各自有序并不推出整个数组有序,最后一次普通插入阶段不可省略。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

gap=2 的 [1,4,3,5] 是否整体有序?

需要一点提示

分别看偶数和奇数下标。

查看解析与答案

两条子序列分别为 [1,3]、[4,5],都已排序,但整体仍有 4>3。

练习 2 · 边界与辨析

n=9 的间隔是什么?

需要一点提示

反复整除 2。

查看解析与答案

4、2、1。

练习 3 · 变式与迁移

只执行 gap=1 会得到什么算法?

需要一点提示

比较代码内层。

查看解析与答案

普通插入排序,失去大间隔预处理。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 排序

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。