插入排序
复习
- 最小生成树：贪心正确的例子
- 排序问题与稳定性：稳定性的含义
- 冒泡排序与选择排序：两种
O(n²)的简单排序
TL;DR
- 插入排序像整理扑克牌，把新牌插入已排好的部分
- 数据接近有序时，它非常快
- 最坏仍是
O(n²)，但常数较小、实现简单 - 它是稳定排序，适合小规模或近乎有序的数据
正文
有一种简单排序，虽然最坏也是 O(n²)，却在特定情况下非常好用。它就是插入排序（insertion sort）。
像整理扑克牌
想象你在整理手里的扑克牌：左边是已经理好的牌，每次从右边拿一张新牌，在左边找到合适的位置插进去。
插入排序正是如此：
- 把第一个元素看作已经排好的部分
- 取出下一个元素，在已排好的部分里从后往前比较
- 找到合适位置就插进去，比它大的元素依次后移一格
重复下去，已排好的部分越来越大，直到覆盖整个数组。
近乎有序时特别快
插入排序有一个讨喜的特点：当数据接近有序时，它非常快。
因为如果数据基本有序，每个新元素几乎不用怎么移动，就能找到自己的位置。极端情况下，如果数据已经有序，它只需从头到尾扫一遍、每次比较一次就结束，代价是 O(n)。
而最坏情况（数据完全逆序）时，每个元素都要一路移到最前面，退化成 O(n²)。
它的现实价值
虽然大 O 看起来不占优势，但在实践中，插入排序常有出人意料的用处：
- 数据规模小：
n很小时，它简单、常数小，甚至比那些“高级排序”还快 - 近乎有序：此时它的表现接近线性
- 作为子过程：很多高效排序（如快排、归并）在处理小片段时，会切回插入排序
而且它是稳定的：相等元素不会被迫互换，相对顺序得以保留。
这再次印证：大 O 描述的是趋势，而真正的工程选择，还要看常数、数据特点和实际规模。 一种“慢”算法，也可能在合适的场景里成为最佳选择。
思考题 1
插入排序为什么在数据接近有序时特别快？
思考题 2
插入排序是稳定排序吗？请说明理由。
小结
知识点
- 插入排序把元素逐个插入已排序部分
- 接近有序时接近
O(n)，最坏O(n²) - 实现简单、常数小、稳定
- 常用于小规模、近乎有序或作为子过程
参考资料
- Wikipedia(zh)：插入排序：逐个插入已排序部分的排序
- Wikipedia(zh)：排序算法：各类排序算法的比较
思考题答案（仅供参考）
思考题 1
因为数据接近有序时，每个新元素在已排序部分里几乎不用移动就能找到位置，比较和移动次数都很少。极端情况下已有序时只需扫描一遍，代价接近 O(n)。
思考题 2
是稳定的。插入时，只有当已排序部分的元素严格大于新元素时才后移，遇到相等元素会停在其后面，因此大小相等的元素不会互换，原相对顺序得以保留。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪