插入排序是一种N的平方复杂度的排序算法。 在处理小批次的数据时很好用。 插入排序的思路就是，找一个分割线，将这个分割线不断的向后移动，同时保证分割线前面的元素都是排好序的。这样移动到末尾时就讲全部的元素排好序了。
根据数学归纳法来看： 1.在仅一个元素时，是有序的 2.我们不断的对索引位N（大于1）的元素与前面的元素比较找到他所应该在的位置插入进去。这样就可以保证在下一次移动N时0到N-1 的元素都是有序的 3.一直当N==数组长度时结束循环
这样就可以将元素排序，并且没有使用多余的缓存数组。
代码如下：
//升序 public static void insertDecSort(int[] ints){ for(int i = 1;i<ints.length;i++){ int index = i-1; int target = ints[i]; while(target < ints[index]&&index>=0){ ints[index+1] = ints[index]; index--; } ints[index+1] = target; } } //降序 public static void insertSortDec(int[] ints){ int j = 1; while (j<ints.length){//终止 int key = ints[j]; int i = j-1; while (i>=0&&ints[i]<key) { ints[i + 1] = ints[i]; i--; } ints[i+1] = key; j++; } }