直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1 的有序表。
这个有点像我们平时玩扑克牌整理牌的过程。随机抽取8张扑克牌，需要按照从小到大的序列排列，我们一般会从第二张牌开始不断的与之前的牌进行比较，直接将扑克牌插入到合适的位置。
图1 直接插入排序
如图1 所示，
第一轮排序：4, 6 均与比之前的数字大，位置变。当i指正遍历到0的位置，与之前的数字进行比较，0数字最小直接插入到第一位，1,4,6后移一位。
第二轮排序：当i遍历到3的位置。3比4,6小，比0，1大。插入到1的后一位，4,6后移。后续步骤以此类推。
代码实现
//直接插入排序
public static int[] insertSort(int[] a) {
int i, j;
//第一位不需要排序，从i=1开始
for (i=1; i<a.length; i++) {
int temp = a[i];
for (j=i-1; j>=0 && temp<a[j]; j--) {
a[j+1] = a[j]; //记录后移
}
a[j+1] = temp; //插入到正确位置
}
return a;
}
public static void main(String[] args) {
int[] a = {1, 4 , 6, 0, 3, 2, 5, 9};
int[] b = insertSort(a);
System.out.print("Select sort:\n");
for(int i=0; i<a.length; i++) {
System.out.print(b[i] + ", ");
}
}
运行结果：
Select sort:
1, 4, 6, 6, 6, 6, 6, 9,
时间复杂度 O（n^2）
