插入排序

插入排序

减治，将序列分为两部分，有序前缀和无序后缀，迭代时在前缀中在合适位置插入。

• ! 对于向量，插入需 $O(n)$ 时间，二分查找需 $O(\log n)$ 时间；对于列表，顺序查找需 $O(n)$ 时间，插入需 $O(1)$ 时间。总的来讲，查找加插入总是需要 $O(n)$ 时间。 时间复杂度最好 $O(n)$，最坏 $O(n^2)$，输入敏感