算法（9）：insertion sort，shellsort-5.4
Insertion sort
插入排序的物理动机与选择排序完全相反。选择排序关注“最少的写入次数”，而插入排序关注“利用输入数据的现有顺序来减少读取次数”。
物理上，插入排序维护一个逻辑边界：指针
i从左向右移动，将数组分割为左侧已排序区（[0, i)）和右侧未处理区（[i, N)）。每一轮，算法取出未处理区的第一个元素a[i]，然后试图在已排序区为它找到正确的位置。1. 物理操作过程（正确版本）
取数：将
a[i]的值保存到临时变量中（该槽位在逻辑上变为“空洞”）。右移：指针
j从i-1开始向左遍历已排序区。对于每个a[j]，如果它大于临时保存的值，就执行a[j+1] = a[j]（将较大的元素向右复制一个位置）。这填补了空洞，但在它原来位置产生了一个新的空洞。插入：当遇到一个不大于临时值的
a[j]时，停止右移，将临时变量存入j+1位置。关键物理动作：这里是引用赋值（写入），而不是“交换”。排序算法在内存中表现为：在连续的内存空间里，把一连串的引用地址整体向右平移了一格。单次平移的成本与交换相同（一次写入），但插入排序经常需要连续进行多次平移才能完成一次插入。
2. 性能来源：逆序对（Inversions）
插入排序的物理工作量完全取决于数组中逆序对的数量。
定义：一对元素
(a[i], a[j])，其中i < j且a[i] > a[j]。物理上，这意味着在最终排序结果中，这两个元素的相对顺序需要被改变。物理对应：每执行一次
a[j+1] = a[j]的右移操作，实际上就是消除了一个或几个逆序对（把较大的元素向右推）。总移动次数= 初始数组的逆序对总数。
三种边界情况：
最好情况（已升序）：逆序对为 0。内部
j循环检查一次后立即停止，不发生任何平移。比较次数为N-1，写入次数为 0。最坏情况（降序）：逆序对数量约为
N²/2。每个新元素都必须一直平移到数组最左端，平移总数约为N²/2。平均情况（随机）：大约一半的逆序对存在，平移总数约为
N²/4。3. 与选择排序的物理对比
选择排序：无论输入如何，扫描全部未排序区（读取固定），写入固定 N 次（交换）。对输入顺序不敏感。
插入排序：只扫描已排序区，但扫描长度取决于找到正确位置的速度（读取可变，找到第一个逆序者即开始插入），写入次数等于逆序对数（写入可变）。对输入顺序高度敏感。
当输入数据具有“局部有序性”（如实时数据流、已排序数组追加新元素）时，逆序对数量接近线性，插入排序的物理效率远高于选择排序。因为它能提前停止，不浪费循环去扫描已知有序的部分。这就是插入排序在“小规模数据”和“近乎有序数据”场景下被广泛使用的原因。
Q：我好像有点明白了，之所以说它快，是因为对于插入排序算法来说，左边的所有都已经排序好了，那么只要你在i左边第一个不是逆序，就全部不是逆序，所以停止超级快。
A：理解完全正确。
物理原因就是：左侧
[0, i-1]是有序的，因此a[i-1]是左侧区间里的最大值。当你把a[i]和a[i-1]比较时：
如果
a[i]大于等于a[i-1]，那么由于左侧是有序的，a[i]必然大于等于左侧所有元素。它的正确位置就是原地不动，内层循环不需要继续向左检查，直接停止。只有当
a[i] < a[i-1]时，才需要继续向左移动，寻找更小的插入位置。这个机制决定了插入排序的停止条件依赖于局部有序性。而选择排序做不到这一点，因为它每轮必须扫描整个未排序区来找最小值，没有“提前停止”这个退出路径。你抓住的正是两种算法在物理循环结构上的本质区别。
shellsort
希尔排序是为了解决插入排序的一个物理限制：插入排序每次只能把元素移动1 个位置。当一个很小的元素出现在数组右端时，插入排序需要把它一步步向左移动 N 次，才能到达正确位置。
希尔排序的策略是：允许元素一次移动多个位置（步长为
h），从而快速消除远距离的逆序对。1. 核心物理动作：
h-排序希尔排序不是改变插入排序的比较逻辑，而是改变它的步长（
stride）。
标准插入排序：比较
a[j]和a[j-1]，步长为 1。希尔排序：比较
a[j]和a[j-h]，步长为h。当步长为
h时，数组在物理上被分成了h条独立的链。每条链中的元素索引相差h（例如链 0：0, h, 2h...）。对每条链执行一次标准插入排序，完成后称为“h-有序”。h-有序不要求整个数组完全有序，只要求对任意索引i（i >= h），都有a[i] >= a[i-h]。2. 为什么用递减的
h序列希尔排序会依次使用递减的
h值（例如 40 → 13 → 4 → 1）。
大
h时：每条链很短（N/h个元素），执行插入排序很快。但元素移动的幅度很大（一次移动h个位置），能迅速把极小的元素从右端送到左端附近，消除大量远距离逆序对。
h递减后：数组仍然保留之前h值下的有序性质，不会因为切换h而被破坏。这意味着当h接近 1 时，数组已经接近全局有序，远距离逆序对已经很少。此时执行标准插入排序（h=1），因为左侧有序度很高，j循环能很快停止（也就是你刚才理解的“提前停止”机制），整体移动次数接近线性。3.
h序列的选择（PPT 中提供的）PPT 提供了
3x+1序列（1, 4, 13, 40, 121...），是计算简单且性能稳定的选择。物理上，
h的选择涉及一个数学性质：相邻的h值之间不能有太大倍数关系，且最好互质。否则，不同h阶段的排序效果会互相抵消（例如用2, 4, 8...只会分别排序奇偶位，无法交错融合），排序效率会大幅下降。4. 性能特征
希尔排序的时间复杂度不固定，取决于
h序列的选择。
使用
3x+1序列时，最坏情况下的比较次数约为O(N^(3/2))。相比于插入排序的
O(N²)，这是一个从平方级别到超平方级别的质变。PPT 表格中的数据可以验证这一点：对于约 80,000 个元素的数组，希尔排序的比较次数约为插入排序的十分之一甚至更低。
总结物理机制：希尔排序通过改变步长，在不增加额外内存空间的情况下，允许元素在数组中跳跃式移动。它利用大
h阶段消除长距离无序，利用小h阶段利用已建立的部分有序性快速完成最终排序。它没有新数据结构，只修改了插入排序循环中的索引偏移量，这个简单的改动就突破了平方级别的时间界。
Q：我感到这是一个很神奇的算法，因为我试着画了一下，我们假设现在有i，i-1和i-h，i-h-1。然后根据希尔排序，你可以得到i大于i-h，i-1大于i-h-1，当然这里的大小是按照该地址内的内容来说的。那么你会发现这个方法并没有要求i-1位置的数据要小于i的。这种排序实际上把一段数组分成了很多有序切片。非常有趣的是，这种有序的切片并不在内存上连续的，而是间隔相同距离，也就是h。
A：非常精准，而且你画出来的那个逻辑链，正是希尔排序在物理内存上的真实布局。你观察到的“不要求i-1位置的数据小于i”，是希尔排序与标准插入排序在认知上的根本分水岭。
1. 你画的“有序切片”物理上是什么样的？
你画的
i, i-h以及i-1, i-h-1，对应在数组内存中是两条完全独立的逻辑链：
链 A：
0, h, 2h, 3h...（你画的i-h和i属于这条链）链 B：
1, h+1, 2h+1...（你画的i-h-1和i-1属于这条链）当算法进行
h-排序时，它是在物理上交错但逻辑上隔离的这h条链上分别执行插入排序。你在纸面上看到的i-1和i在物理内存地址上相邻，但在希尔排序的这一轮逻辑中，它们毫无关系——它们属于不同的子序列，不需要满足有序关系。2. 为什么“不连续”反而成为了优点？
标准插入排序强制要求物理连续的内存块整体有序（
a[0] < a[1] < a[2]...）。为了维持这个全局有序，你每插入一个新元素，必须把一串连续的元素整体向右移动。希尔排序放弃了“物理连续整体有序”这一约束，只要求“相隔
h的逻辑链内部有序”。这个让步带来了一个巨大的物理收益：元素可以只在自己的逻辑链内部跳跃移动。在h-排序中，一个较小的元素可以不越过相邻的物理内存，直接跨过h个位置移动到自己链内的正确位置。这种跨步移动在物理上只涉及几次赋值，而在标准插入排序中，这需要反复搬运中间的每一个元素。3. 为什么“不连续”最终能导向“连续”？
h-排序结束后，数组呈现“全局近似有序”的状态。虽然在细粒度上（相邻位置）仍然可能有逆序，但任何元素离它最终正确位置的距离都不太远了。当
h降到 1 时（即最后一遍标准插入排序），虽然它依然要求物理连续的内存块整体有序，但由于之前的h-排序已经消除了绝大多数远距离逆序对，最后的插入排序不需要移动很远的距离就能完成排序。这正是你之前理解的“插入排序快是因为能提前停止”——希尔排序通过前期的大跨步移动，把“提前停止”发生的时间点提前到了最后一遍排序的早期阶段。4. 总结你画的图
你画的
i > i-h和i-1 > i-h-1，揭示了希尔排序在内存中的真实状态：它在逻辑上将数组划分为若干独立的子序列，分别排序，从而破坏原始序列中长距离元素的物理邻接依赖，为后续的全局有序打下基础。这个理解已经达到了希尔排序在物理层面的核心。
Q：帮我看看这个怎么证明？我感觉不一定啊，就像我们刚才说的，i不一定大于i-1。万一在h-sorted以后破坏原本相隔的g-sorted呢？
A：这是一个非常敏锐的观察。你直觉上觉得“不一定”，是因为你在物理层面看到了一个事实：h-排序时交换的是一对相隔h的元素，它们完全可能跨越g的间隔。如果跨过了，那么原先在g间隔上保持的大小关系确实可能被破坏。你的直觉是对的——这个命题的证明确实不显然，而且它恰好是希尔排序证明中最微妙的一步。
这个命题在物理上为什么成立？
我们用一个“位置追踪”的思路来验证它：
假设数组经过
g-排序后，满足性质：对于任意索引i（i + g < N），都有a[i] ≤ a[i+g]。现在我们对这个数组进行
h-排序。h-排序的本质是：对每个模h的同余类内部的元素进行排序（按值从小到大排列）。关键物理观察：
h-排序只会移动位于同一个模h同余类内部的元素。也就是说，一个元素在排序后的位置，与它原先位置的模h值相同。现在取任意两个索引
i和i+g。在h-排序后，位置i被来自某个索引p的元素占据，且p ≡ i (mod h)。位置i+g被来自某个索引q的元素占据，且q ≡ i+g (mod h)。我们需要证明：最终位置
i的值 ≤ 最终位置i+g的值。由于
g不一定是h的倍数，直接比较p和q的关系比较困难。但我们可以借助一个更强的中间结论：对于任意两个值，如果它们在原始数组中满足
x ≤ y，且x所在的原始位置p_x和y所在的原始位置p_y满足某种“模h顺序”关系，那么在h-排序后，x仍然不会出现在y的右边。在
h-排序中，每个同余类内部的元素按值排序。这意味着：如果x ≤ y，且x和y属于同一个模h类，那么x最终的位置一定在y的左边。如果它们不属于同一个模
h类，那么它们之间的相对顺序不受h-排序的直接约束。但g-排序的性质会约束那些跨越不同模h类的元素对。此命题的严格证明通常采用“反证法 + 追踪最小元素”或使用“偏序（Partial Order）”的语言。在算法文献（如 Sedgewick 本人）中，这个证明常被略去或提及为“非显然但成立”，因为它确实超出了算法入门课的范围。
如果你现在不需要写出这个证明，可以这样理解它在物理上的保障：
h-排序不是在乱序地移动元素，它是在每个模h的类内部进行有序排列。这种操作不会把某个类内较大的元素交换到另一个类内较小的元素前面，从而破坏了g间隔上的全局有序性。g-排序建立的是跨类的全局约束，h-排序执行的是类内排序，两者叠加后，跨类的约束不会被破坏。如果你确实需要完整的数学证明，我可以把它的关键步骤（使用“0-1 原理”和“格点路径”的方法）展开给你看。
Q：可我感觉PPT上就有反例啊，例如这里第一个序列中的m和s，它是一个横跨七的sorted7七排列，然后再经过一个sorted3以后，m和s就不是隔7了。
M O L E E X A S P R T
A E L E O P M S X R T
A：首先，我先直接回你刚才的疑问：你认为M和S在 3-sort 后不再相隔 7，但命题“保持 g-sorted”并不是指“原本相隔 g 的那两个具体元素仍然保持相隔 g”，而是指“在排序后的新数组中，任意相隔 g 的两个位置上的值，左边的依然小于等于右边的”。
现在，我用你PPT上的数据来证实这一点，你就明白为什么它“微妙但成立”了：
在
3-sort之前（7-sorted）：M O L E E X A S P R T
此时相隔 7 的几对是：
位置 0（M）≤ 位置 7（S） ✅
位置 1（O）≤ 位置 8（P） ✅
位置 2（L）≤ 位置 9（R） ✅
位置 3（E）≤ 位置 10（T）✅
在
3-sort之后：A E L E O P M S X R T
你看似把M和S打乱了（它们现在在位置 6 和 7，不是严格隔7）。但我们要检查新数组的相隔 7 的几对：
位置 0（A）≤ 位置 7（S） ✅
位置 1（E）≤ 位置 8（X） ✅
位置 2（L）≤ 位置 9（R） ✅
位置 3（E）≤ 位置 10（T）✅
结果：依然全部满足左边 ≤ 右边。
为什么这个命题在物理上是成立的？（解决你的“不一定”直觉）
你直觉觉得不一定，是因为你以为
h-排序会打乱已排序的链。但物理上，h-排序只做了一件事：把每个模h的链内部进行排序。
原始
g-排序建立的约束是：对于任意i，a[i] ≤ a[i+g]。
h-排序移动元素时，是按值大小在同一条模h链内部重新排列。关键物理事实：
g-排序的约束，其实等价于说：任意两条模h链之间，已经建立了一种“错位且一致”的大小关系。当你在每条链内部重新排序后，这种跨链的大小关系不会出现冲突，因为如果某个元素被移到了更左边（更小），它在左边遇到的那些跨链元素只会更小或相等；如果被移到了右边，它在右边遇到的那些跨链元素只会更大或相等。换句话说：
g-排序已经确定了所有链之间的“相对大小界”。h-排序只是在每根链内部调整了顺序（把小的放前面），这不会破坏已经固定的链间相对界。这个命题确实比通常的排序命题更微妙，因为它涉及到两个不同步长的排序之间的叠加不变性。你脑海中“不一定”的怀疑，恰好说明了这个命题的分量——它虽然成立，但需要你从“位置约束”而非“元素追踪”的角度去看待它。