插入排序

public void insertSort(int a[]) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                }
            }
            //System.out.println(Arrays.toString(a));
        }
    }

插入排序从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左部数组依然有序。

第 j 元素是通过不断向左比较并交换来实现插入过程：当第 j 元素小于第 j - 1 元素，就将它们的位置交换，然后令 j 指针向左移动一个位置，不断进行以上操作。

插入排序的优化

 //临时变量
    int temp;

    //外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
    for (int i = 1; i < arrays.length; i++) {

        temp = arrays[i];

        //如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序]
        while (arrays[i - 1] > temp) {

            //往后退一个位置，让当前数据与之前前位进行比较
            arrays[i] = arrays[i - 1];

            //不断往前，直到退出循环
            i--;

        }

        //退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
        arrays[i] = temp;

    }