插入排序（Insertion sort）

1. 什么是插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。

简略来说插入排序的工作形式像许多人排序一手扑克牌。开始时，咱们的左手为空并且桌子上的牌面向下。而后，咱们每次从桌子上拿走一张牌并将它插入左手中正确的地位。为了找到一张牌的正确地位，咱们从右到左将它与已在手中的每张牌进行比拟。

2. 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最初一个元素当成是未排序序列。

从头到尾顺次扫描未排序序列，将扫描到的每个元素插入有序序列的适当地位。

3. 动图演示

4. 代码实现

public static void main(String[] args) {int[] arr = {5,3,1,4,2,7,8,6,10,9};

        for (int i = 0,j = i; i < arr.length - 1; j = ++i) {
            // 默认 0 下标是有序的，获取从 0 开始的下一个元素
            int temp = arr[i + 1];
            // 如果下一位元素是比上一位小的
            while (temp < arr[j]){
                // 把上一位寄存在下一位中，这个时候就会笼罩下一位的值，不过咱们曾经存在 temp 中
                arr[j + 1] = arr[j];
                // 当 j == 0 的时候则阐明曾经到头
                if(j -- == 0){break;}
            }
            // 把最小的值写入以后地位
            arr[j + 1] = temp;
        }

        System.out.println(Arrays.toString(arr));
    }

另一种写法：

    public static void main(String[] args) {int[] arr = {5,3,1,4,2,7,8,6,10,9};

        // 从下标为 1 的元素开始抉择适合的地位插入，因为下标为 0 的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从曾经排序的序列最左边的开始比拟，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {arr[j] = tmp;
            }

        }
        System.out.println(Arrays.toString(arr));
    }

5. 输入后果

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]