插入排序

插入排序逐个扩展有序前缀。每轮取出下一个值，把前缀中比它大的元素右移，再把这个值放入空位。它是稳定的原地比较排序，最坏时间复杂度为 O(n²)，输入已有序时为 O(n)。接近有序的输入通常需要较少的移动。

整理手中的扑克牌就是这个过程：拿到一张牌，越过比它大的牌，把它插入合适的位置。已经排好的牌保持有序，只需为新牌腾出位置。

插入排序如何工作

外层循环的 i 从 1 到 n - 1。每轮开始时，arr[0..i - 1] 已有序，arr[i] 是待插入的值。先执行 key = arr[i] 保存它，这个位置就成为逻辑上的空位。

内层循环从 j = i - 1 向左扫描。当 j >= 0 且 arr[j] > key 时，执行 arr[j + 1] = arr[j]，把较大元素右移一格，再递减 j。遇到小于或等于 key 的值，或越过左边界后，扫描结束，把 key 写入 arr[j + 1]。

每轮都把一个值插入有序前缀，且没有破坏前缀的顺序。因此循环结束后，整个数组都有序。

插入排序逐步演示

默认输入为 [38, 12, 56, 7, 41, 23, 19]。

第 1 轮，i = 1，取出 key = 12，有序前缀是 [38]。38 > 12，把 38 右移，j 变成 -1。将 12 放到下标 0，得到 [12, 38, 56, 7, 41, 23, 19]。

第 2 轮，i = 2，取出 key = 56。比较 38 和 56，38 更小，扫描结束，不需要右移。56 回到原位置。本轮比较一次，没有移位。

第 3 轮，i = 3，取出 key = 7。56、38、12 都大于 7，依次右移。j 到达 -1 后，把 7 放到下标 0，得到 [7, 12, 38, 56, 41, 23, 19]。

第 4 轮只右移 56，插入 41，得到 [7, 12, 38, 41, 56, 23, 19]。第 5 轮右移 56、41、38，把 23 放到下标 2，得到 [7, 12, 23, 38, 41, 56, 19]。第 6 轮右移 56、41、38、23，把 19 放到下标 2，结果为 [7, 12, 19, 23, 38, 41, 56]。

动画把位置 i 的值提到数组上方，表示已保存的 key。j 向左扫描，每次右移都把空位向左传一格。扫描结束后，key 落入 j + 1。

时间与空间复杂度

额外空间为 O(1)。课程展示的是移位版本：保存一个 key，反复执行 arr[j + 1] = arr[j]，最后插入；不是通过相邻交换完成插入的版本。

最好情况来自循环条件 while j >= 0 and arr[j] > key。输入已有序时，每轮的第一个值比较就不满足条件，总共只比较 n - 1 次。一般情况下，运行时间是 Θ(n + I)，其中 I 是输入的逆序对数：每个逆序对对应一次移位。只有 I = O(n) 时才能保证线性时间；笼统地说“接近有序”还不够。逆序输入则让每个 key 都穿过整个前缀，工作量增长为 O(n²)。

这种对输入顺序的适应能力，让插入排序适合短数组和接近有序的片段，也使它成为一些混合排序算法的组成部分。

边界情况

• 空数组或一个元素：外层循环不执行。
• 已有序：每轮第一次值比较后停止，总共 n - 1 次比较，时间复杂度为 O(n)。
• 所有值相等：arr[j] > key 从不成立，没有移位，时间复杂度也是 O(n)。
• 存在重复值：遇到与 key 相等的元素时停止扫描，不让 key 越过它。因此相等元素保持原顺序，排序稳定。

常见错误

• 把 > 写成 >=：相等元素也会右移，key 会越过它们，稳定性随之丢失。
• 把 key 放到 arr[j]：循环结束后，j 指向无需移动的元素，或等于 -1。空位是 j + 1。
• 没有先保存 key：第一次右移就会覆盖待插入的值。
• 移位方向写反：应执行 arr[j + 1] = arr[j]，让较大元素向右移动，为 key 留出空位。