对应《算法导论》第二章
类比扑克牌，假设我们现在手里已经有了几张牌，再拿到新的一张。则需要与已拿到的对比，并插入。
特点：小规模可以，大规模效率太低
这是一个就地算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] arr = {0,5,2,4,6,1,3}; //排序数组
//key比较，如果小于前一个，则前一个后移，递推。否则不动
for (int i = 1; i < arr.length; i++) { //复杂度 o(n)
int key = arr[i]; //新值
int j = i-1; //需要对比的前一个值
//如果新值小于前值
while (key < arr[j]){ //复杂度 o(n)
arr[j+1] = arr[j];//前值后移一位
arr[j] = key;
if( (j--) == 0){ //此处实现了 j-- 并判断是否到头
break;
}
}
}
代码分析：
后一个数与前面的数一次比较，若小于前面的数，则前面的数后移一位（始终是相邻两位的比较）
已经排好序的部分为循环不变式
复杂度为 o(n^2)(最坏情况),o(n)(最好情况)
