一、原理
每一步将一个待排序的记录，按其关键码值得大小插入前面已经排序的文件中适当的位置上，直到全部插入完为止。
二、代码实现
package com.jdk8.SortTest;
public class InsertSort {
public static void doInsertSort(int[] arrays){
int i,j;
for(i=1;i<arrays.length;i++){
int temp = arrays[i];//temp为存储的临时变量
//查找temp插入到该有序列表的具体位置
for(j =i-1;j>=0 && arrays[j]>temp;j--){
arrays[j+1] = arrays[j];//移动元素
}
arrays[j+1] = temp;//插入到具体的位置
}
System.out.println();
}
public static void display(int[] arrays){
for(int i = 0;i < arrays.length;i++){
System.out.print(" " + arrays[i] + " ");
}
}
public static void main(String[] args){
int[] arrays = {3,9,63,93,72,15,27,86};
System.out.println("排序前的数据为：");
display(arrays);
doInsertSort(arrays);
System.out.println("排序后的数据为：");
display(arrays);
}
}
运行结果如下:
排序前的数据为：
3 9 63 93 72 15 27 86
排序后的数据为：
3 9 15 27 63 72 86 93
三、复杂度分析
3.1、时间复杂度分析
最好情况（原本就是有序的）
比较次数：Cmin=n-1
移动次数：Mmin=0
最差情况（逆序）
比较次数：Cmax=1+2+3+4+……+n-1=(n-1)n/2
移动次数：Mmax=1+2+3+……+n-1=(n-1)n/2
若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为 n^2/4。因此，直接插入排序的时间复杂度为 o(n^2)。
3.2、空间复杂度
插入排序的临时变量所占用的空间不随处理数据n的大小改变而改变，即空间复杂度为O(1)。
四、稳定性
插入排序是稳定排序。