插入排序--直接插入排序

2018-09-19

思路：

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

public static void main(String[] args) {
        int arr[] = {3, 5, 7, 2, 4, 9, 1, 6, 10, 8};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
    }

    private static void insertSort(int[] arr) {

        for (int i=1; i<arr.length; i++){
            int j=i;
            int index = arr[i];//待插入元素
            while (j>0 && index <arr[j-1]){//通过循环，逐个后移一位找到要插入的位置
                arr[j] = arr[--j];
            }
            arr[j] = index;
        }
    }