思想
插入排序的主要思想是，每次取待排序的数组中的第一个元素，去和已经排好序的数组进行比较，插入到合适的位置。 所以，插入排序将数组分为了两个部分，一个部分是已经排好序的，另一个部分是待排序数列。
举例
第一次，选择第一个元素作为已排序数组，然后将第二个元素与已排序的数组的第一个元素进行比较，确定位置。 接着，第三个元素与已排序的两个元素进行比较，确定位置。 因此，按照这种思想，总共要进行n-1次取待排序数组的第一个元素的操作。
再思考，取到了待排序的一个元素，怎么样去确定他在已排序数组中的位置呢？下面举例进行说明
例如要对 4 3 1 2 进行升序的插入排序操作，过程如下
代码
/// 插入排序
public void insertSort(int [] input){
for(int i =1; i < input.length; i++){
int insertIndex = 0;
// 找到插入位置
while(insertIndex < i && input[insertIndex]<=input[i]){
insertIndex++;
}
// 插入位置后的数整体后移
if( insertIndex < i){
int temp = input[i];
while( i > insertIndex ){
input[i] = input[i-1];
i--;
}
input[insertIndex] = temp;
}
}
}
代码二：
package test;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
InsertSort insertSort = new InsertSort();
int [] a = {25 , 11, 45, 26, 12, 78};
insertSort.insersort(a);
System.out.println(Arrays.toString(a));
}
public void insersort(int [] a){
if (a == null || a.length ==0) {
return;
}
for(int i =1;i<a.length;i++){
int j;
int current = a[i];
for(j = i-1;j>=0;j--){
if (current < a[j]) {
a[j + 1] = a[j];
}else{
break;
}
}
a[j + 1] = current;
}
}
}
时间复杂度分析
很明显，外循环是n-1次。 当input[i]的值小于所有的已经排好序的数组元素的值的时候，内循环需要移动所有的input[0] – input[i-1]。 因此，第二个元素移动1次，第三个元素移动两次，第n个元素移动n-1次，这时，时间复杂度是1+2+3+。。。+n-1,时间复杂度是O(n2)。 而平均情况下，不需要一定i-1次，只需要移动(i-1)/2,时间复杂度也是O(n2)。
时间复杂度
O(1) 很明显
