基本思路：将一个记录插入到已经排好序的有序表中，得到一个新的记录数加1的有序表。通过对未排序的数据执行逐个插入至合适位置而完成排序工作。
步骤：
（1）将整个待排序序列划分为有序区和无序区，初始化有序区为待排序记录序列中的第一个，无序区包括所有剩余的待排序记录；
（2）无序区的第一个记录插入到有序区的合适位置，无序区减一个记录，有序区加一个记录；
（3）不断重复（2），直至无序区没有记录为止。
直接插入排序图解
代码如下：
public class Insertion_Sort {
public static void main(String[] args){
long startTime=System.nanoTime(); //获取开始时间
int[] st = {1,3,2,5,4,4,4,4,4,4,5,5,5,5,5,5,5,1,1,1,1,2,2,2,3,4,5,7,3,2,2,24,54};
sort1(st);
// sort2(st);
long endTime=System.nanoTime(); //获取结束时间
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
System.out.println(Arrays.toString(st));
}
//程序运行时间： 20128ms
public static void sort1(int[] a){
for(int i = 1; i < a.length; i++){ //从第2个数字开始排序。第一个数组作为有序数组
for(int j = i-1; j >= 0; j--,i--){
if(a[i] < a[j]){ //如果当前数字小于有序数组的最后一位，则往前移动
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}else{
break;
}
}
}
}
//程序运行时间：11711ms
public static void sort2(int[] b){
int i , j , key;
for(i=1;i<b.length;i++){
key = b[i];
for(j = i-1; j>=0; j--){
if(b[j]>key){
b[j+1]=b[j];
}else{
break;
}
}
b[j+1] = key;
}
}
}
