插入排序（ insertion sort ）是一种直观的排序算法，它的工作原理非常简单：每次从未排序序列中取出一个元素，然后将它插入到已排序序列中，直到整个序列完全有序。
有序序列插入新元素
我们先来研究，如何将一个新元素插入一个有序序列？这是理解插入排序的关键所在。
- 先假设有序序列后一个位置为合适插入点，从后往前寻找正确插入点；
- 检查当前插入点，看是否满足排序条件；
- 如果前一个元素大于插入点（不满足排序条件），将其后移一位，空出来的位置作为新插入点，再次检查；
- 否则（满足排序条件），将新元素插进去；
下面这个动画很好地演示了将新元素插入有序序列的整个过程，可以结合起来理解：
下面是示例代码，结合动画和注释，相信应该不难理解：
由于我们需要从后往前遍历有序序列，因此插入操作的平均时间复杂度为 $O(n)$ 。如果待插入的元素刚好是最大值，那么我们只需将其插在序列后面，时间复杂度为 $O(1)$ 。这个动画演示了这种特例：
插入排序
掌握插入技巧后，理解插入排序就毫无难度了：
- 原序列第 0 个元素，已经天然有序了；
- 从第 1 个开始，逐个遍历每个元素，并将其插入到元素前的有序序列；
- 带所有元素插入完毕，整个序列就排好顺序了；
就像打扑克牌时，从桌上逐一拿起每张牌，并插到手中的正确位置。
下面这个动画，很好地演示了插入排序的全过程，可以逐步观看，加深理解：
插入排序示例代码如下，结合动画和注释，应该不难理解：
由于插入排序需要将 $n-1$ 个元素插入到有序序列中，因此插入排序的平均时间复杂度是 $O(n^2)$ 。如果待排序序列已经有序，插入过程无需遍历寻找插入点，则时间复杂度为 $O(n)$ 。
综上所述，插入排序最坏和平均时间复杂度都是 $O(n^2)$ ，最好时间复杂度为 $O(n)$ 。
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
小菜学编程
