1.1 插入排序

我们要学的第一个算法，是插入排序。它不是最快的排序，甚至可能是你学的几种排序里最慢的之一。但我特意把它放在第一节，是因为它最接近人本能的排序方式，而且它是理解"循环不变量"（1.9 节会专门讲）这个概念最好的入门例子。

1.牌桌上的直觉

你打过扑克牌吧？每摸一张新牌，你会把它插到手里已经排好序的牌里，让手里的牌始终保持有序。具体怎么插？你从右往左，把手里那些比新牌大的牌一张张往右挪，腾出一个空位，把新牌放进去。再来一张，重复。等所有牌都摸完，手里的牌就全排好了。

插入排序干的就是这件事，只不过牌换成了数组里的数。

设数组 $A[1..n]$ ，我们维护一个想法：数组左边是已经排好序的"手牌"，右边是还没摸的"牌堆"。每一轮，从牌堆最上面（右边第一个）摸一张，插到手牌的正确位置。

2.算法过程

来看具体的伪代码。下标从 1 开始（1.9 节会讲为什么从 1 开始更方便）：

INSERTION-SORT(A, n)          // A[1..n] 待排序
for j = 2 to n:               // 从第2张开始，第1张本身视为已排好的手牌
    key = A[j]                // 摸起第 j 张
    i = j - 1                 // 从手牌最右端开始往左看
    while i > 0 and A[i] > key:   // 只要左边的牌比 key 大
        A[i+1] = A[i]         // 就把它往右挪一格
        i = i - 1             // 继续往左看
    A[i+1] = key              // 腾出的空位放 key

举个例子，数组 [5, 2, 4, 6, 1, 3]：

$j=2$ ，摸起 2。手牌 [5]，5>2 往右挪，插进去 → [2, 5, | 4, 6, 1, 3]
$j=3$ ，摸起 4。5>4 往右挪，2<4 停，插进去 → [2, 4, 5, | 6, 1, 3]
$j=4$ ，摸起 6。5<6 直接停，不动 → [2, 4, 5, 6, | 1, 3]
$j=5$ ，摸起 1。一路往右挪到底 → [1, 2, 4, 5, 6, | 3]
$j=6$ ，摸起 3。挪到 2 后面 → [1, 2, 3, 4, 5, 6]

（我用 | 标出"已排序的手牌"和"未摸的牌堆"之间的分界线，它随着 $j$ 右移一路推进。）

3.它为什么对：循环不变量

怎么相信这玩意儿真的能把数组排好？这里我先给你直觉，严格的循环不变量证明留到 1.9 节，到时候我们会拿着这套语言把插入排序当范例重新证一遍。现在先抓住核心：

算法全程维持着一个不变的性质—— $A[1..j-1]$ 这一段始终是有序的。一开始 $j=2$ ， $A[1..1]$ 只有一个元素，天经地义有序。每一轮，我们摸起 $A[j]$ ，在内层 while 里把所有比它大的往右挪、比它小的留在左边，最后把 $key$ 放进空位——这一通操作下来， $A[1..j]$ 也变有序了。于是"有序段"从 $A[1..1]$ 一路长到 $A[1..n]$ ，循环结束时 $j=n+1$ ，整个数组有序，完事。

这个"不变的性质"就叫循环不变量。它是证明迭代算法正确的标准武器，现在你先有个感觉，1.9 节会系统讲。

4.复杂度分析

算法快不快？数一数基本操作（比较和移动）的次数。

外层 for 跑了 $n-1$ 轮。关键是内层 while，它取决于当前这张牌要往左挪多远。

最好情况：数组本来就有序。每轮 while 一次比较就跳出（ $A[j-1]<key$ 直接成立），内层只执行 1 次。总共约 $n-1$ 次比较，复杂度 $O(n)$ 。很快。
最坏情况：数组是逆序的。每摸一张牌都得挪到最左边，第 $j$ 轮内层比较 $j-1$ 次。总共 $\sum_{j=2}^{n}(j-1)=\frac{n(n-1)}{2}$ ，复杂度 $O(n^2)$ 。很慢。
平均情况：随机输入下，新牌平均要往左挪一半，总比较次数约为最坏的一半，渐进复杂度仍是 $O(n^2)$ 。

所以插入排序的复杂度是 $O(n^2)$ （看最坏/平均）。这个 $O(n^2)$ 意味着： $n$ 翻 10 倍，时间翻 100 倍。一万个元素还行，十万个就明显吃力了。

1.8 节会专门教你怎么严格地数这些操作、怎么从 $O(n^2)$ 这种结论里读出"规模大了会怎样"，这里先有个手感。

5.既然这么慢，为什么还要学

你可能会问：后面归并排序、堆排序都是 $O(n\log n)$ ，快得多，插入排序这种 $O(n^2)$ 的还有什么用？这正是我想提醒你别小看它的地方：

第一，它在小规模、近乎有序的数据上非常快。 注意它的最好情况是 $O(n)$ ——当数据几乎有序时，内层 while 几乎不执行，它比那些 $O(n\log n)$ 的算法更快（因为常数小）。实际上，很多工业级排序库（比如 C++ 的 std::sort、Python 的 Timsort）在小数据段上，都会切回插入排序。"大材小用"的分治排序在小数据上的常数开销，反而比插入排序高。

第二，它是原地、稳定的。 "原地"是说它只用 $O(1)$ 的额外空间；"稳定"是指相等的元素排序后相对顺序不变——这俩性质在工程里有时很重要。

第三，它是学习循环不变量的最佳教具。 1.9 节你会再来这里报到。

6.练习

Q1. 给定数组 [8, 3, 5, 1, 9, 2]，手动模拟插入排序，写出每轮 j 之后数组的状态（用 | 标出已排序段）。

|8,3,5,1,9,2 → 3,8|5,1,9,2 → 3,5,8|1,9,2 → 1,3,5,8|9,2 → 1,3,5,8,9|2 → 1,2,3,5,8,9。每轮把 | 右边第一个元素插到左边有序段的正确位置。

Q2. 什么样的输入会让插入排序跑出最好情况 $O(n)$ ？什么样的会跑出最坏情况 $O(n^2)$ ？

最好情况是输入已经升序：每张牌都不用往左挪，内层 while 一次就跳出。最坏情况是输入完全逆序（降序）：每张牌都得挪到最左边，第 $j$ 轮挪 $j-1$ 次，总和 $\frac{n(n-1)}{2}$ 次， $O(n^2)$ 。

Q3.（思考题） 为什么实际工程里的混合排序算法（如 Timsort、introsort）在小数据段会切回插入排序？

因为插入排序虽然渐进复杂度是 $O(n^2)$ ，但常数极小、没有递归开销。当 $n$ 很小时， $O(n^2)$ 的"平方惩罚"还没显现，而它省下的递归/分治的常数开销反而让它更快。复杂度的 $O$ 记号看的是"规模很大时的趋势"，小规模时常数和递归开销的影响可能压倒渐进阶——这正是 1.8 节要讲"渐近分析"时反复强调的边界。

7.小结

插入排序用最贴近直觉的"理牌"方式，把排序这件事拆解得清清楚楚。它不快（ $O(n^2)$ ），但在小规模和近乎有序时是利器，更是理解循环不变量的入口。下一篇我们看一个真正快起来的排序——归并排序，它会第一次让你尝到 $O(n\log n)$ 和"分治"的甜头。