# 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` | 每次移动配一次比较，另外每轮收尾还有一次"失败"的比较             |

## 二、代码

```cpp
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 的位置
    }
}
```

要点：

1. `key`必须存储在别处，否则在`a[i]`搬移过程中会被覆盖掉导致出错
2. 把`key`拿出来后，`a[j] > key`一直往后挪，实际上就是在`a[0..i-1]`里给`key`腾位置`j`最后停在「第一个 ≤ key 的元素」上，所以插入点是`j + 1`
3. 遇到相等元素立刻停止，保证稳定性