前言插入排序insertion sort是排序算法里最接近人手整理扑克牌的一种左手已经拿了一叠排好的牌右手每摸一张就从右往左比过去插到合适的位置。它的最坏时间复杂度是 O(n²)因此经常被当成「教学用的玩具」一带而过。但在真实代码里它并没有过时——多数标准库的排序实现在区间缩短到十几个元素时会切换成插入排序原因有两个小数组上它的常数因子很小而且对「几乎已经有序」的输入它的比较次数会退化到 O(n)。初学者对它的误解主要有两个。一是把插入排序和冒泡排序混为一谈两者都是 O(n²)但插入排序的移动是「整段后移一次写入」冒泡是「相邻两两交换」元素移动的次数差一个常数因子而且插入排序在近乎有序的数据上优势明显。二是认为「二分插入排序」能把它优化成 O(n log n)——二分只能把比较次数降到 O(n log n)移动元素仍然是 O(n²)整体复杂度没有变。本文从算法过程、循环不变式、几种常见变体讲到完整实现所有复杂度都按标准语义推算不给出任何未经测量的耗时数字。一、算法过程插入排序维护一个不变式下标区间 [0, i) 已经有序。每一轮把a[i]取出来在 [0, i) 里从后往前找位置比它大的元素依次后移一格最后把取出的值写进空出来的位置。i 从 1 走到 n-1结束后整个区间有序。用扑克牌打比方key是右手刚摸到的牌j是左手从右往左移动的手指凡是比key大的牌都往右挪一格直到遇到一张不大于key的牌就把key插在它右边。这个过程有三个值得注意的性质稳定性内层循环的条件写a[j-1] key严格大于遇到相等元素就停下等于把key放在相等元素的右边相对顺序不变所以是稳定排序。写成就会把相等元素放到左边稳定性被破坏。在线性不需要事先知道全部数据来一个处理一个适合流式场景。自适应输入越接近有序内层循环走的步数越少完全有序时内层一次都不执行总共 n-1 次比较。二、正确性与循环不变式证明插入排序正确标准做法是验证循环不变式在三个时刻成立初始化i 1 时区间 [0, 1) 只有一个元素天然有序。保持假设进入第 i 轮前 [0, i) 有序。内层循环把所有大于key的元素右移一格直到a[j-1] key此时 [0, j) 的元素都不大于key[j1, i] 的元素都大于key它们是被右移过来的把key放到 j 位置后[0, i1) 有序。终止i 走到 n 时[0, n) 即整个数组有序。这个证明里唯一需要小心的是内层循环的终止条件。当j减到 0 时a[j-1]会越界所以循环条件必须写成j 0 a[j-1] key——短路求值保证j 0时不会去读a[-1]。顺序不能反写成a[j-1] key j 0在 j 为 0 时就已经越界了。三、几种变体3.1 基础版逐个后移最直接的实现用一个临时变量保存待插入值内层用赋值完成「后移」避免相邻交换带来的三次写入。3.2 哨兵版去掉j 0判断内层循环每次都要判断j 0在数据量大时可以先把数组最小值换到a[0]作为哨兵。因为a[0]是全局最小任何key都不小于它内层循环一定会在j 0之前停下来于是判断可以省掉一个。代价是先花 O(n) 找一次最小值。这个优化在现代编译器上未必带来可测量的收益——分支预测对j 0这种高度规律的判断通常处理得很好。这里讲它主要是为了说明「哨兵」这种手法本身而不是推荐无条件使用。3.3 二分插入减少比较不减少移动既然 [0, i) 已经有序找插入位置就可以用二分查找把每轮的比较次数从 O(i) 降到 O(log i)总比较次数从 O(n²) 降到 O(n log n)。但元素后移仍然要移动 O(i) 个位置总移动次数还是 O(n²)。所以二分插入排序的整体复杂度仍是 O(n²)只是在「比较代价远高于移动代价」的类型上才有意义比如比较两个长字符串、而元素本身是指针。用std::upper_bound找位置还能顺带保证稳定性upper_bound返回第一个大于key的位置相等元素会被排在key前面正好符合稳定排序的要求如果用lower_bound相等元素会被排到后面稳定性被破坏。3.4 链表版对std::list做插入排序找位置只能顺序扫描移动则是改指针代价是 O(1)。整体仍是 O(n²) 次比较但没有元素搬移。实际工程里更常见的做法是直接把链表转成std::vector排序再转回去或者用归并排序——std::list::sort用的就是归并。四、完整示例4.1 泛型基础版// 适用于 C17#include cstddef#include iostream#include utility#include vectortemplate typename Tvoid insertion_sort(std::vectorT a) {for (std::size_t i 1; i a.size(); i) {T key std::move(a[i]); // 取出待插入元素std::size_t j i;while (j 0 a[j - 1] key) { // 严格大于保证稳定a[j] std::move(a[j - 1]); // 后移一格--j;}a[j] std::move(key); // 写入空位}}int main() {std::vectorint data{5, 2, 9, 1, 5, 6};insertion_sort(data);for (int v : data) std::cout v ;std::cout \n;return 0;}这段代码用移动而不是拷贝对std::string这类类型能少一次深拷贝。key在循环中始终持有完整值被移动的是a[i]和后面那些要后移的元素逻辑上不会读到已移走的值。4.2 二分插入版// 适用于 C17#include algorithm#include cstddef#include iostream#include iterator#include utility#include vectortemplate typename Tvoid binary_insertion_sort(std::vectorT a) {for (std::size_t i 1; i a.size(); i) {T key std::move(a[i]);auto first a.begin();auto last a.begin() static_caststd::ptrdiff_t(i);// upper_bound第一个大于 key 的位置保证相等元素的相对顺序auto pos std::upper_bound(first, last, key);// 把 [pos, last) 整体右移一格再从后往前搬避免覆盖std::move_backward(pos, last, last 1);*pos std::move(key);}}int main() {std::vectorint data{4, 4, 1, 3, 9, 3};binary_insertion_sort(data);for (int v : data) std::cout v ;std::cout \n;return 0;}std::move_backward的第三个参数是目标区间的末尾它从后往前搬正好适合这种「整体右移」的场合。如果误用std::move源区间和目标区间重叠时会互相覆盖。4.3 带哨兵的版本// 适用于 C17#include cstddef#include iostream#include utility#include vectorvoid insertion_sort_sentinel(std::vectorint a) {if (a.size() 2) return;// 先把最小值换到 a[0] 作为哨兵std::size_t min_index 0;for (std::size_t i 1; i a.size(); i) {if (a[i] a[min_index]) min_index i;}std::swap(a[0], a[min_index]);for (std::size_t i 2; i a.size(); i) {int key a[i];std::size_t j i;while (a[j - 1] key) { // 不再需要 j 0a[j] a[j - 1];--j;}a[j] key;}}int main() {std::vectorint data{7, 3, 8, 1, 3, 9, 2};insertion_sort_sentinel(data);for (int v : data) std::cout v ;std::cout \n;return 0;}i从 2 开始是安全的a[0]已经是全局最小所以[0, 1]这两个位置天然有序。五、复杂度与适用场景指标最好平均最坏说明比较次数n-1O(n²)O(n²)完全有序时每轮只比较一次移动次数0O(n²)O(n²)完全有序时一次都不移动额外空间O(1)O(1)O(1)只用一个临时变量稳定性稳定稳定稳定条件必须是严格大于把这些和别的排序放在一起看算法平均时间额外空间稳定适合的场景插入排序O(n²)O(1)是小数组、近乎有序、在线处理冒泡排序O(n²)O(1)是教学演示选择排序O(n²)O(1)否移动代价极高、比较便宜归并排序O(n log n)O(n)是要求稳定、可接受额外空间快速排序O(n log n) 平均O(log n)否通用场景最坏 O(n²)工程上的常见组合是「快速排序 小区间插入排序」快排递归到区间长度小于某个阈值时停止改用插入排序收尾。阈值取多少由实现决定标准库源码里能看到具体数字但那是实现细节不是标准规定。常见坑点1. 比较写成大于等于破坏稳定性❌while (j 0 a[j - 1] key)✅while (j 0 a[j - 1] key)用时相等的元素也会被后移key被插到相等元素的前面相对顺序改变。同时它还多做了一次无意义的移动。2. 循环条件顺序写反导致越界❌while (a[j - 1] key j 0)✅while (j 0 a[j - 1] key)从左到右求值并短路。把a[j-1]放在前面j 0时就已经读取了a[-1]这是未定义行为不是「碰巧能跑」。3. 用相邻交换代替整体后移❌while (j 0 a[j-1] a[j]) { std::swap(a[j-1], a[j]); --j; }✅ 先存key循环里只做a[j] a[j-1]最后一次写入key一次swap是三次赋值整体后移只需要一次赋值。数据量大时这个常数差别会累积起来。更重要的是交换版本在每轮都要重新读取a[j]逻辑上更绕。4. 以为二分插入排序是 O(n log n)❌ 「把查找换成二分插入排序就变成 O(n log n) 了」 ✅ 二分只降低比较次数元素移动仍是 O(n²)总复杂度不变复杂度由最贵的那一步决定。这里最贵的是移动不是比较。5. 对链表用下标访问❌for (std::size_t i 1; i lst.size(); i) { auto key lst[i]; ... }✅ 用迭代器遍历或用std::list::sortstd::list没有operator[]这段代码根本编译不过。即便换成std::next每次定位也是 O(n)整体会退化到 O(n³)。6. 在大型随机数据上单独使用插入排序❌ 对十万条记录直接调用插入排序 ✅ 用std::sort或者「快排 小区间插入」的组合O(n²) 在十万量级上是百亿次操作的数量级不是换个编译选项能救回来的。插入排序的定位是「小规模」和「近乎有序」不是通用排序。7. 自定义比较器不满足严格弱序❌[](int a, int b) { return a b; }传给std::upper_bound✅[](int a, int b) { return a b; }用于降序且保证严格upper_bound要求区间按比较器有序而比较器必须是严格弱序strict weak ordering。不满足非自反性行为未定义。8. 忽略元素类型的移动代价❌ 对一个存放大对象的std::vector用拷贝版插入排序 ✅ 用std::move完成搬移或改为排序索引/指针插入排序的移动次数是 O(n²)每一次移动如果都是深拷贝代价会被放大很多倍。移动语义在这里不是微优化而是数量级上的差别。总结要点结论核心思想维护前缀有序每轮把一个元素插入正确位置循环不变式进入第 i 轮前区间 [0, i) 有序时间复杂度最好 O(n)平均与最坏 O(n²)空间复杂度O(1)只需一个临时变量稳定性条件写严格大于时稳定二分优化只减少比较不减少移动适用场景小数组、近乎有序、在线处理、作为快排的收尾插入排序是理解「增量式构造」的最好入口每一步都只处理一个新元素把已有结构维护好。它的复杂度不漂亮但常数小、无额外空间、稳定、能在线处理这些性质让它在标准库的排序实现里始终占着一个位置。写它的时候只要盯住三件事——边界j 0、比较用严格大于、移动用赋值而不是交换——正确性和效率就都有保障。 前言插入排序insertion sort是排序算法里最接近人手整理扑克牌的一种左手已经拿了一叠排好的牌右手每摸一张就从右往左比过去插到合适的位置。它的最坏时间复杂度是 O(n²)因此经常被当成「教学用的玩具」一带而过。但在真实代码里它并没有过时——多数标准库的排序实现在区间缩短到十几个元素时会切换成插入排序原因有两个小数组上它的常数因子很小而且对「几乎已经有序」的输入它的比较次数会退化到 O(n)。初学者对它的误解主要有两个。一是把插入排序和冒泡排序混为一谈两者都是 O(n²)但插入排序的移动是「整段后移一次写入」冒泡是「相邻两两交换」元素移动的次数差一个常数因子而且插入排序在近乎有序的数据上优势明显。二是认为「二分插入排序」能把它优化成 O(n log n)——二分只能把比较次数降到 O(n log n)移动元素仍然是 O(n²)整体复杂度没有变。本文从算法过程、循环不变式、几种常见变体讲到完整实现所有复杂度都按标准语义推算不给出任何未经测量的耗时数字。一、算法过程插入排序维护一个不变式下标区间 [0, i) 已经有序。每一轮把a[i]取出来在 [0, i) 里从后往前找位置比它大的元素依次后移一格最后把取出的值写进空出来的位置。i 从 1 走到 n-1结束后整个区间有序。用扑克牌打比方key是右手刚摸到的牌j是左手从右往左移动的手指凡是比key大的牌都往右挪一格直到遇到一张不大于key的牌就把key插在它右边。这个过程有三个值得注意的性质稳定性内层循环的条件写a[j-1] key严格大于遇到相等元素就停下等于把key放在相等元素的右边相对顺序不变所以是稳定排序。写成就会把相等元素放到左边稳定性被破坏。在线性不需要事先知道全部数据来一个处理一个适合流式场景。自适应输入越接近有序内层循环走的步数越少完全有序时内层一次都不执行总共 n-1 次比较。二、正确性与循环不变式证明插入排序正确标准做法是验证循环不变式在三个时刻成立初始化i 1 时区间 [0, 1) 只有一个元素天然有序。保持假设进入第 i 轮前 [0, i) 有序。内层循环把所有大于key的元素右移一格直到a[j-1] key此时 [0, j) 的元素都不大于key[j1, i] 的元素都大于key它们是被右移过来的把key放到 j 位置后[0, i1) 有序。终止i 走到 n 时[0, n) 即整个数组有序。这个证明里唯一需要小心的是内层循环的终止条件。当j减到 0 时a[j-1]会越界所以循环条件必须写成j 0 a[j-1] key——短路求值保证j 0时不会去读a[-1]。顺序不能反写成a[j-1] key j 0在 j 为 0 时就已经越界了。三、几种变体3.1 基础版逐个后移最直接的实现用一个临时变量保存待插入值内层用赋值完成「后移」避免相邻交换带来的三次写入。3.2 哨兵版去掉j 0判断内层循环每次都要判断j 0在数据量大时可以先把数组最小值换到a[0]作为哨兵。因为a[0]是全局最小任何key都不小于它内层循环一定会在j 0之前停下来于是判断可以省掉一个。代价是先花 O(n) 找一次最小值。这个优化在现代编译器上未必带来可测量的收益——分支预测对j 0这种高度规律的判断通常处理得很好。这里讲它主要是为了说明「哨兵」这种手法本身而不是推荐无条件使用。3.3 二分插入减少比较不减少移动既然 [0, i) 已经有序找插入位置就可以用二分查找把每轮的比较次数从 O(i) 降到 O(log i)总比较次数从 O(n²) 降到 O(n log n)。但元素后移仍然要移动 O(i) 个位置总移动次数还是 O(n²)。所以二分插入排序的整体复杂度仍是 O(n²)只是在「比较代价远高于移动代价」的类型上才有意义比如比较两个长字符串、而元素本身是指针。用std::upper_bound找位置还能顺带保证稳定性upper_bound返回第一个大于key的位置相等元素会被排在key前面正好符合稳定排序的要求如果用lower_bound相等元素会被排到后面稳定性被破坏。3.4 链表版对std::list做插入排序找位置只能顺序扫描移动则是改指针代价是 O(1)。整体仍是 O(n²) 次比较但没有元素搬移。实际工程里更常见的做法是直接把链表转成std::vector排序再转回去或者用归并排序——std::list::sort用的就是归并。四、完整示例4.1 泛型基础版// 适用于 C17#include cstddef#include iostream#include utility#include vectortemplate typename Tvoid insertion_sort(std::vectorT a) {for (std::size_t i 1; i a.size(); i) {T key std::move(a[i]); // 取出待插入元素std::size_t j i;while (j 0 a[j - 1] key) { // 严格大于保证稳定a[j] std::move(a[j - 1]); // 后移一格--j;}a[j] std::move(key); // 写入空位}}int main() {std::vectorint data{5, 2, 9, 1, 5, 6};insertion_sort(data);for (int v : data) std::cout v ;std::cout \n;return 0;}这段代码用移动而不是拷贝对std::string这类类型能少一次深拷贝。key在循环中始终持有完整值被移动的是a[i]和后面那些要后移的元素逻辑上不会读到已移走的值。4.2 二分插入版// 适用于 C17#include algorithm#include cstddef#include iostream#include iterator#include utility#include vectortemplate typename Tvoid binary_insertion_sort(std::vectorT a) {for (std::size_t i 1; i a.size(); i) {T key std::move(a[i]);auto first a.begin();auto last a.begin() static_caststd::ptrdiff_t(i);// upper_bound第一个大于 key 的位置保证相等元素的相对顺序auto pos std::upper_bound(first, last, key);// 把 [pos, last) 整体右移一格再从后往前搬避免覆盖std::move_backward(pos, last, last 1);*pos std::move(key);}}int main() {std::vectorint data{4, 4, 1, 3, 9, 3};binary_insertion_sort(data);for (int v : data) std::cout v ;std::cout \n;return 0;}std::move_backward的第三个参数是目标区间的末尾它从后往前搬正好适合这种「整体右移」的场合。如果误用std::move源区间和目标区间重叠时会互相覆盖。4.3 带哨兵的版本// 适用于 C17#include cstddef#include iostream#include utility#include vectorvoid insertion_sort_sentinel(std::vectorint a) {if (a.size() 2) return;// 先把最小值换到 a[0] 作为哨兵std::size_t min_index 0;for (std::size_t i 1; i a.size(); i) {if (a[i] a[min_index]) min_index i;}std::swap(a[0], a[min_index]);for (std::size_t i 2; i a.size(); i) {int key a[i];std::size_t j i;while (a[j - 1] key) { // 不再需要 j 0a[j] a[j - 1];--j;}a[j] key;}}int main() {std::vectorint data{7, 3, 8, 1, 3, 9, 2};insertion_sort_sentinel(data);for (int v : data) std::cout v ;std::cout \n;return 0;}i从 2 开始是安全的a[0]已经是全局最小所以[0, 1]这两个位置天然有序。五、复杂度与适用场景指标最好平均最坏说明比较次数n-1O(n²)O(n²)完全有序时每轮只比较一次移动次数0O(n²)O(n²)完全有序时一次都不移动额外空间O(1)O(1)O(1)只用一个临时变量稳定性稳定稳定稳定条件必须是严格大于把这些和别的排序放在一起看算法平均时间额外空间稳定适合的场景插入排序O(n²)O(1)是小数组、近乎有序、在线处理冒泡排序O(n²)O(1)是教学演示选择排序O(n²)O(1)否移动代价极高、比较便宜归并排序O(n log n)O(n)是要求稳定、可接受额外空间快速排序O(n log n) 平均O(log n)否通用场景最坏 O(n²)工程上的常见组合是「快速排序 小区间插入排序」快排递归到区间长度小于某个阈值时停止改用插入排序收尾。阈值取多少由实现决定标准库源码里能看到具体数字但那是实现细节不是标准规定。常见坑点1. 比较写成大于等于破坏稳定性❌while (j 0 a[j - 1] key)✅while (j 0 a[j - 1] key)用时相等的元素也会被后移key被插到相等元素的前面相对顺序改变。同时它还多做了一次无意义的移动。2. 循环条件顺序写反导致越界❌while (a[j - 1] key j 0)✅while (j 0 a[j - 1] key)从左到右求值并短路。把a[j-1]放在前面j 0时就已经读取了a[-1]这是未定义行为不是「碰巧能跑」。3. 用相邻交换代替整体后移❌while (j 0 a[j-1] a[j]) { std::swap(a[j-1], a[j]); --j; }✅ 先存key循环里只做a[j] a[j-1]最后一次写入key一次swap是三次赋值整体后移只需要一次赋值。数据量大时这个常数差别会累积起来。更重要的是交换版本在每轮都要重新读取a[j]逻辑上更绕。4. 以为二分插入排序是 O(n log n)❌ 「把查找换成二分插入排序就变成 O(n log n) 了」 ✅ 二分只降低比较次数元素移动仍是 O(n²)总复杂度不变复杂度由最贵的那一步决定。这里最贵的是移动不是比较。5. 对链表用下标访问❌for (std::size_t i 1; i lst.size(); i) { auto key lst[i]; ... }✅ 用迭代器遍历或用std::list::sortstd::list没有operator[]这段代码根本编译不过。即便换成std::next每次定位也是 O(n)整体会退化到 O(n³)。6. 在大型随机数据上单独使用插入排序❌ 对十万条记录直接调用插入排序 ✅ 用std::sort或者「快排 小区间插入」的组合O(n²) 在十万量级上是百亿次操作的数量级不是换个编译选项能救回来的。插入排序的定位是「小规模」和「近乎有序」不是通用排序。7. 自定义比较器不满足严格弱序❌[](int a, int b) { return a b; }传给std::upper_bound✅[](int a, int b) { return a b; }用于降序且保证严格upper_bound要求区间按比较器有序而比较器必须是严格弱序strict weak ordering。不满足非自反性行为未定义。8. 忽略元素类型的移动代价❌ 对一个存放大对象的std::vector用拷贝版插入排序 ✅ 用std::move完成搬移或改为排序索引/指针插入排序的移动次数是 O(n²)每一次移动如果都是深拷贝代价会被放大很多倍。移动语义在这里不是微优化而是数量级上的差别。总结要点结论核心思想维护前缀有序每轮把一个元素插入正确位置循环不变式进入第 i 轮前区间 [0, i) 有序时间复杂度最好 O(n)平均与最坏 O(n²)空间复杂度O(1)只需一个临时变量稳定性条件写严格大于时稳定二分优化只减少比较不减少移动适用场景小数组、近乎有序、在线处理、作为快排的收尾插入排序是理解「增量式构造」的最好入口每一步都只处理一个新元素把已有结构维护好。它的复杂度不漂亮但常数小、无额外空间、稳定、能在线处理这些性质让它在标准库的排序实现里始终占着一个位置。写它的时候只要盯住三件事——边界j 0、比较用严格大于、移动用赋值而不是交换——正确性和效率就都有保障。