思路分析
插入排序是将整个区间被分 有序区间和无序区间。每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入
我们这里使用bound来作为无序区间的第一个元素，需要将这个元素和前面的每一个元素依次进行比较，此处排出来的顺序应该为升序，也就是将bound元素放到合适的地方即可
此处令cur为bound的前一个元素，如果cur与bound比较，bound小与粗人，那么就将cur往后移一位（bound位置的元素事先存起来，以保证不被覆盖），然后将cur减一，再与之前存好的bound元素进行比较，直到放到合适的位置（bound元素不再小于cur的元素），就停止比较，以上过程就是一次比较的过程，重复上面的步骤，就可以完成整个数组的排序。
图解
代码示例
代码语言：javascript复制 //插入排序------
public static void insertSort(int[] array){
for (int bound = 1; bound < array.length; bound ){
int v = array[bound];
int cur = bound - 1;//已排好序列的最后一个元素
for (; cur >= 0; cur--){
//循环和前面已排好序的元素一次比较
if (array[cur] < v){
array[cur 1] = array[cur];
}else {
break;
}
}
array[cur 1] = v;
}
}两个特性
1.数据量少的时候，速度快 2.数据接近有序的时候，速度快
性能分析
时间复杂度： 最好：O(N) {数据有序} 平均：O(N^2) 最坏：O(N^2) {数组逆序}
空间复杂度： O(1)
稳定性： 稳定排序
