Insertion Sort 插入排序 · InsertionSort.cpp
插入排序也很简单，每次拿到一个数据就从头找到一个位置插入进去
前i个元素每一轮都是有序的，所以第i轮结束时前i+1个也有序，一路推到整个数组。
一、复杂度与特性
| 项目 | 值 | 说明 |
|---|---|---|
| 时间（最好） | O(n) | 已有序时，每个元素只跟左边一个元素比一次，while立刻退出 |
| 时间（平均 / 最坏） | O(n²) | 最坏时数组逆序，每个元素都要一路挪到最前面 |
| 空间 | O(1) | 原地排序 |
| 稳定性 | 稳定 | 条件是严格a[j] > key，遇到相等的就停手，同值元素不会互相跨过 |
| 移动次数 | 逆序对数inv | 一次a[j+1] = a[j]算一次移动 |
| 比较次数 | ≈inv + n-1 | 每次移动配一次比较，另外每轮收尾还有一次"失败"的比较 |
二、代码
void insertion_sort(std::vector<int> &a)
{
const int n = static_cast<int>(a.size());
for (int i = 1; i < n; ++i)
{
const int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) // 比 key 大的统统往右让位
{
a[j + 1] = a[j];
--j;
}
a[j + 1] = key; // 空出来的位置就是 key 的位置
}
}要点：
key必须存储在别处，否则在a[i]搬移过程中会被覆盖掉导致出错- 把
key拿出来后，a[j] > key一直往后挪，实际上就是在a[0..i-1]里给key腾位置j最后停在「第一个 ≤ key 的元素」上，所以插入点是j + 1 - 遇到相等元素立刻停止，保证稳定性
附件下载
- InsertionSort.cpp（765 B · 29 行）
- InsertionSort.md（2 KB · 42 行）