直接插入排序-Java

概念：

直接插入排序是将一条记录插入到已排好序的有序列表中，从而得到一个新的、记录数量增1的有序列表

算法步骤：

1. 设待排序的数组为r[1...n], 单独的一个r[1]是一个有序的数组
2. 循环n-1次，每次使用顺序查找法，查找ri在已排好序的序列r[1...i-1]中的插入位置，然后将r[i]插入表长为i-1的有序序列r[1...i-1],直到将r[n]插入表长为n-1的有序序列r[1...n-1],最后得到一格表长为n的有序序列

例子：
a[] = {2, 1, 5, 3, 6, 4, 9, 8, 7}

1. 首先a[1] = {2}是有序的序列，a[2...9]是无序的，要插入到a[1]序列中
比较 a[1]<a[2]然后a[1]后退一格到a[2]的位置，a[2]插入到a[1]前面
有序数组变为：a[1...2] = {1,2};   无序数组为a[3...9] = { 5, 3, 6, 4, 9, 8, 7}

2. 第二轮：a[1...2]和a[3]；先a[2]<a[3]；a[3]直接插入a[2]后面
有序列表a[1...3]  = {1,2,5}； 无序数组为a[4...9] = {3, 6, 4, 9, 8, 7}

3. 第三轮：a[1...3]和a[4]; 先a[3]>a[4]；tem = a[4] 然后a[3]往后移一格到a[4]的位置；
继续 a[2]<tem；然后tem插入到a[2]后面的位置, 也就是a[3]的位置
有序数组为：a[1...4] = {1,2,3,5}； 无序数组为a[5...9] = {6, 4, 9, 8, 7}
4. 接下来都是这样

代码：

public class DirectInsertSort {
    public static void main(String[] args) {
        int a[] = {2, 1, 5, 3, 6, 4, 9, 8, 7};
        int tem;
        for (int i = 1; i < a.length; i++) {
            if (a[i] < a[i - 1]) {
                tem = a[i];
                for (int j = i; j > 0; j--) {
                    if (j>0&&tem < a[j - 1]) {
                        a[j] = a[j - 1];
                    } else {
                        a[j] = tem;
                        break;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}