直接插入排序

直接插入排序(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）