问题： 排序——输入数组 {a1,a2,...,an} { a 1 , a 2 , . . . , a n } ，排序后数组为 {a′1,a′2,...,a′n} { a 1 ′ , a 2 ′ , . . . , a n ′ } ，使得 a′1≤a′2≤...≤a′n a 1 ′ ≤ a 2 ′ ≤ . . . ≤ a n ′ 。
插入排序原理如下：
假设数组中某个数 ak a k 前面的部分是已经排序好的，将这个数插入前面已经排序好的部分，使得这个数大于等于左边的数，小于等于右边的数，这时数组 {a1,a2,...,ak} { a 1 , a 2 , . . . , a k } 则是排序好的。 所以我们递归的从数组第二个数 a2 a 2 开始做插入操作，直到最后一个数 an a n ，这时整个数组就是排序好的了。
下面是排序 {5,2,4,6,1,3} { 5 , 2 , 4 , 6 , 1 , 3 } 的例子
C++代码如下：
void insertion_sort(int* array, int size) { // When i is x, means the 0~x-1 of array is sorted. for (int i = 1; i < size; i++) { int current = array[i]; int j = i-1; // Copy array[j] -> array[j+1], until find the place to insert array[i] for (; j >= 0 && array[j] > current; j--) { array[j+1] = array[j]; } array[j+1] = current; } }时间复杂度：
当输入的数组是排序好的，插入排序的时间复杂度为 O(n) O ( n ) 当输入的数组是逆序的，插入排序的时间复杂度为 1+2+...+n=O(n2) 1 + 2 + . . . + n = O ( n 2 ) 插入排序的平均时间复杂度为 O(n2) O ( n 2 ) （TODO：证明）插入排序是原址排序（基本不需要额外空间，通过交换数据的位置达到排序），而且是稳定排序（当有相同数据时，排序后它们的相对位置不变）
Ref：https://github.com/maomao9003/Introduction-of-Algorithms/blob/master/Code/Algorithms/A-02-1-InsertionSort/insertion_sort_realization.c
