排序算法之插入排序

把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

public static void insetSort(int[] array) {
    
    for (int i = 1; i < array.length; i++) {
        // i之前的是已经排好序的
        int temp = array[i];
        // 从i-1开始往前找位置
        int j = i - 1;
        
        //因为前面的已经是有序了。所以从后往前找，只要找到比当前值小的就可以插入
        //因为要插入，所以i之前的值往后移
        while(j>=0&&array[j]>temp) {
            array[j+1] = array[j];
            j--;
        }
        array[j + 1] = temp;
        System.out.println("第"+i+"次" + Arrays.toString(array));
    }
    System.out.println("insetSort:" + Arrays.toString(array));
}

原始数组 [2, 1, 5, 4, 3]

第一次循环，i=1,j=0,temp=1;2比1大，进入while循环，把1的位置赋给0的位置 ,j--后，j=-1,跳出while循环.此时array[1] = 2了，然后赋值array[0] = temp,也就是原来array[1]的值，此时数组就变成了[1,2,5,4,3]

第二次循环
i = 2 ,因为 5比前面的数都要大，所以不会进入while循环，此时j+1其实就是i,数组顺序依然不变[1,2,5,4,3]

第三次循环
i = 3 ,j=2, temp =4,因为5比4大，进入while循环，直到找到一个比4小的数。此时j=2;while第一次后数组变成[1,2,5,5,3],j--后，j=1,此时2比4小，跳出while循环，此时temp插入j+1也就是2的位置。执行完后数组变成[1, 2, 4, 5, 3]

第四次循环
此时i=4,j=3，temp=3, 5>3,进入while循环,执行赋值操作后数组变成[1, 2, 4, 5, 5]，j--,j=2后
4>3依然成立，继续执行赋值操作，此时数组变成[1, 2, 4, 4, 5],j--后j=1,因为2<3,所以跳出while循环，此时插入j+1也就是2的位置，插入后数组变成[1, 2, 3, 4, 5]
至此，排序完成

执行结果
第1次[1, 2, 5, 4, 3]
第2次[1, 2, 5, 4, 3]
第3次[1, 2, 4, 5, 3]
第4次[1, 2, 3, 4, 5]