插入排序（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]