插入排序

插入排序是一个简单的排序算法，算法主要通过在左边维持一个有序的子数组，然后不断的将右边的元素按照顺序插入到左边有序的子数组中，直到所有的元素都插入完成。最好的情况是当数组已经有序时，时间复杂度是O(N)，最坏的情况是当数组是反序时，时间复杂度是O(N^2)，平均时间复杂度是O(N^2)。

算法主要思路是

1. 从数组第二个元素开始，按照顺序插入到当前元素左边已经有序的子数组中。
2. 第一轮，左边的子数组只有一个元素，只要和当前元素比较，交换位置即可。
3. 第二轮，左边的子数组有两个上一轮已排好序的两个元素，需要将当前元素插入到两个元素中合适的位置。
4. ....
5. 直到所有的元素都插入，数组就排序完成。

比如数组[4, 2, 1, 3, 7, 6, 5]插入排序过程如下

插入排序代码实现如下。

插入排序也是一种效率比较低的排序算法，一般适用于对效率要求不高或者数据规模较小的排序。