前言

插入排序（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 次比较。
• 
  

二、正确性与循环不变式

证明插入排序正确，标准做法是验证循环不变式在三个时刻成立：

1. 
   
2. 初始化：i = 1 时，区间 [0, 1) 只有一个元素，天然有序。
3. 
   
4. 保持：假设进入第 i 轮前 [0, i) 有序。内层循环把所有大于key的元素右移一格，直到a[j-1] <= key，此时 [0, j) 的元素都不大于key，[j+1, i] 的元素都大于key（它们是被右移过来的），把key放到 j 位置后，[0, i+1) 有序。
5. 
   
6. 终止：i 走到 n 时，[0, n) 即整个数组有序。
7. 
   

这个证明里唯一需要小心的是内层循环的终止条件。当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 泛型基础版

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

template <typename T>
void insertion_sort(std::vector<T>& 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::vector<int> 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 二分插入版

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

template <typename T>
void binary_insertion_sort(std::vector<T>& 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_cast<std::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::vector<int> 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 带哨兵的版本

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

void insertion_sort_sentinel(std::vector<int>& 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 > 0
a[j] = a[j - 1];
--j;
}
a[j] = key;
}
}

int main() {
std::vector<int> 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]这两个位置天然有序。

五、复杂度与适用场景

把这些和别的排序放在一起看：

工程上的常见组合是「快速排序 + 小区间插入排序」：快排递归到区间长度小于某个阈值时停止，改用插入排序收尾。阈值取多少由实现决定，标准库源码里能看到具体数字，但那是实现细节，不是标准规定。

常见坑点

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::sort

std::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²)，每一次移动如果都是深拷贝，代价会被放大很多倍。移动语义在这里不是微优化，而是数量级上的差别。

总结

插入排序是理解「增量式构造」的最好入口：每一步都只处理一个新元素，把已有结构维护好。它的复杂度不漂亮，但常数小、无额外空间、稳定、能在线处理，这些性质让它在标准库的排序实现里始终占着一个位置。写它的时候只要盯住三件事——边界j > 0、比较用严格大于、移动用赋值而不是交换——正确性和效率就都有保障。