14.5.3 插入类排序

插入类排序的核心像整理扑克牌：手里前几张已经有序，新拿到一张牌，就从后往前找它的位置，把比它大的牌后移，然后插进去。

直接插入排序的工作方式

直接插入排序把序列分成两部分：

• 左边：已经排好的有序区。
• 右边：尚未处理的待排序区。

第 $i$ 趟取出待排序区第一个元素 temp，从有序区末尾向前比较。若有序区元素比 temp 大，就向后移动一格；遇到不大于 temp 的元素，temp 插在它后面。

以课程中的序列 57, 68, 59, 52 为例：

步骤	待插入元素	比较过程	插入后结果
初始	57	第一个元素默认有序	57, 68, 59, 52
第 1 趟	68	68 > 57，不移动	57, 68, 59, 52
第 2 趟	59	59 < 68，68 后移；59 > 57，插入中间	57, 59, 68, 52
第 3 趟	52	52 依次小于 68、59、57，三者后移	52, 57, 59, 68

这个过程里的辅助空间只有一个 temp，用于暂存待插入元素，所以空间复杂度是 $O(1)$。

为什么直接插入排序稳定

直接插入排序在比较时通常只移动“比 temp 大”的元素。若遇到相等关键字，不继续越过它，temp 会插在已有相等元素之后。因此相等关键字的原始次序不会改变。

排序前：21a, 35, 21b
处理 21b 时，遇到 21a 相等，不越过 21a
排序后：21a, 21b, 35

这也是课程里说它属于稳定排序的原因。

复杂度为什么是这样

直接插入排序的代价来自两个动作：向前比较、向后移动。

初始状态	比较/移动特点	时间复杂度
已经有序或基本有序	每个元素只需和前一个比较，很少移动	最好约 $O(n)$
随机序列	平均会向前找一段距离	平均 $O(n^2)$
逆序	每个新元素都要移到最前面	最坏 $O(n^2)$

这就是为什么题干出现“基本有序”时，直接插入排序是强候选。它不需要像选择排序那样每趟扫描剩余所有元素，也不需要额外数组。

希尔排序：为什么会出现

直接插入的弱点是：远处的小元素只能一格一格往前挪。如果一个很小的元素在序列末尾，它要经过很多次移动才能到前面。

希尔排序的改进思路是先按较大的增量分组，在组内做插入排序，让元素先“大步”接近最终位置；然后逐渐缩小增量，最后增量为 1 时再做一次直接插入。

flowchart TD
  A["原序列"] --> B["按增量 d 分组"]
  B --> C["每组做插入排序"]
  C --> D["缩小增量"]
  D --> E{"d = 1?"}
  E -- 否 --> B
  E -- 是 --> F["完成一次整体直接插入"]

希尔排序为什么不稳定？因为它按增量分组时会发生“隔空移动”。相等关键字可能被分到不同组，在不同趟排序中跨越彼此，原始相对次序可能改变。

折半插入排序的定位

有些教材还讲折半插入排序：既然左边有序，可以用二分查找确定插入位置。它减少的是比较次数，但确定位置后仍然要移动元素，因此移动次数没有根本下降。

算法	改进点	没解决的问题	稳定性
直接插入	实现简单，基本有序时快	逆序时移动多	稳定
折半插入	用二分减少查找位置的比较次数	元素仍要后移	稳定
希尔排序	让远距离元素先快速接近最终位置	增量选择影响性能	不稳定

计数排序的课堂补充

字幕里在讲插入排序考题时补充了一个场景：若关键字都在 0 到 9 之间，可以统计每个值出现多少次，再按次数输出。这就是计数排序思想。

例如 1000 个关键字都在 0..9 之间：

值	0	1	2	...	9
出现次数	$c_0$	$c_1$	$c_2$	...	$c_9$

输出时写 $c_0$ 个 0、$c_1$ 个 1、……即可。它能快，是因为没有做两两比较；它受限，是因为关键字范围必须足够小，否则计数数组会很大。

考试判断

• “基本有序的记录排序”优先选直接插入，最好情况接近 $O(n)$。
• “属于插入类但不稳定”指希尔排序。
• “折半插入减少什么”答比较次数，不是移动次数。
• “关键字范围小，如 0 到 9”可能考计数排序或基数排序思想，不要机械选择插入排序。

单选

对一个已经基本有序的记录序列进行内部排序，若希望算法简单且效率较高，通常优先考虑哪种排序？

A直接插入排序B简单选择排序C堆排序D快速排序

本节小结

插入类排序的本质是“维护有序区”。直接插入简单、稳定、对基本有序数据特别有利；希尔排序用增量分组解决远距离移动慢的问题，但用不稳定性换取了更好的平均表现。