核心思想：把一个数插入有序的数组中，end代表被比较值的下标，如果
不符合条件end的值会覆盖后一个值并且向前走，有合适的值就就会插入end的的后面
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { //单趟 int end = i; int tmp = a[end + 1];//保存要排序的值 while (end >= 0) { if (a[end] > tmp) //排升序用>， 降序用< { a[end + 1] = a[end]; end -= 1; } else { break; } } a[end + 1] = tmp; } }
插入排序有很强的适应性，因为后面要插入时，前面已经是一个有序的数列，挪动数据的次数取决于要查如数据的大小，在很大程度上能减少消耗。时间复杂度：在逆序的时候挪动数据次数从1加到n - 1，是等差数列之和，所以是n^2这个量级。插入排序是一个稳定的排序，如果被比较的数据等于要插入的数据，就会把要插入的数据插入被比较的数据后面。
