上一页我们看到：希尔排序的框架是固定的——按间隔分组做插入排序，间隔逐轮缩小到 1。但间隔每轮取多少、怎么缩小，框架并没有规定。这个自由度，正是本节要解决的问题。

这棵思维导图列出评判增量序列好坏的四个维度，从左到右逐条展开，先看根再看分支。

上一页我们说要给序列「减少混乱」，但混乱怎么量化？想想排队：前面的人比后面高，大家看着就别扭。这种「该在后面的却在前面」的组合，就是衡量乱程度的基本单位。

以小数组为例逐步找出所有逆序对

上一页我们数过逆序对，它就是数组「乱的程度」。那排序到底在干什么？答案很干净：就是在消灭逆序对。而插入排序每交换一次，恰好只消掉一个。

从上往下读：每趟增量削减一批逆序对，越往下剩余越少，最后一趟几乎不用干活。

用归并排序在 O(n log n) 内数出逆序对，量化序列好坏。

归并时三处计数相加：左半内部、右半内部、跨越中线的逆序对；右半元素落位时，左半剩余个数一次性统计，避免逐对比较。

上一页我们看完了几种经典的增量序列，但你可能好奇：为什么 3h+1 这样的序列特别受推崇？这要从一个看似无关的老问题说起——邮票怎么贴，才能恰好凑出某个邮资。

用 3 分和 4 分邮票凑出 14 分，一步步看组合如何构造出来。

前面算过：1、5、12、19 这组邮票面值，在限额内几乎每个金额都能凑出——面值组合的“覆盖能力”是设计出来的。增量序列也一样：h 取哪些值，决定了哪些间隔的逆序对能被提前消掉。

两者都为希尔排序造增量序列，但出发点完全不同：一个凭几何直觉，一个靠计数证明。

邮资问题给了我们灵感：只用 2 的幂的倍数，硬币系统才「顺畅」。希尔排序的序列也一样挑剔——有一个著名定理（Pratt，1971）告诉我们什么样的序列能把界压到 O(N^{3/2})。

定理K的证明拆成四步：每步只依赖前一步的观察，逐层逼近结论。

左上顺主干：定理K条件如何一路转化为逆序对被高效削减；右下分支展示条件被破坏时的最坏结局。

关于希尔排序增量序列的条件，下列说法正确的是？

• ✓逆序对数是插入排序成本的可视化账本
• ✓希尔排序每轮大幅消解逆序对，后续轮变轻松
• ✓邮资问题引出「可达增量序列」的设计约束
• ✓定理K保证：相邻增量互素时计数下界更优
• ✓好序列=每轮消得多，且轮间留有长程交换能力

三个问题，先自己想五分钟，再看参考答案。