排序与查找
插入排序
插入排序正是大多数人整理手中扑克牌的方式：在左侧留一段整齐的已排序牌，然后拿起下一张，把它往左滑过所有比它大的牌，落到它该在的位置。重复，直到未排序的那堆牌没了。任何时刻，左半部分都是完全有序的；你只是一张一张地把它扩大。
从机制上看，你从左到右扫过数组。对每个新元素，把它和身后那些已排序的元素比较，把太大的那些各往右挪一格，腾出一个空位让新元素落进去。真正干活的就是这个挪动，而挪动的多少完全取决于数据本来有多乱。
在近乎有序的数据上，它表现极好：每个元素几乎不用动，代价趋近 O(n)——最好情况（已经有序）正好是 O(n)。但平均情况、以及最坏情况（完全逆序）下，元素要走很远，代价是 O(n^2)。它原地排序，额外空间 O(1)，而且稳定（相等的键保持原来的先后顺序）。对小规模或几乎有序的输入，它很难被超越，所以现实中的排序库会在子数组很小时退回用它。
void insertionSort(std::vector<int>& a) {
for (int i = 1; i < (int)a.size(); ++i) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger ones right
a[j + 1] = a[j];
--j;
}
a[j + 1] = key; // drop key into the gap
}
}把 key 暂存一旁，较大的元素右移，给它腾出位置。
稳定 + 原地 + 自适应（对近乎有序的数据很快），这三点兼得很少见。这正是 Timsort 和许多 std::sort 实现在子数组缩小到某个小阈值之下时改用插入排序的原因。
又称
另见