插入排序算法

????????插入排序是一种简单直观的排序算法，其工作原理是通过构建有序序列，从后向前扫描，找到相应位置并插入。直接插入排序是插入排序的一种，它每次将一个待排序的记录按其关键字大小插入到前面已经排序的子序列中的适当位置，直到全部记录插入完成为止。

????????具体来说，直接插入排序首先将第一个元素视为已排序序列，然后从第二个元素开始，在已排序序列中从后向前扫描。如果该元素（已排序）大于新元素，则将该元素移到下一位置。重复此步骤，直到找到已排序的元素小于或等于新元素的位置。这时，将新元素插入到该位置后。这个过程会一直持续到所有元素都已排序。

????????需要注意的是，虽然插入排序的时间复杂度为O(n^2)，但其空间复杂度为O(1)，因此其在数据量较小或者部分有序的情况下仍然十分有效。

核心思想：

? ? ? ? 首先，将第一个值固定下来，依次判断后面的值(临时保存下来后面会用到)，是否(顺序输出)小于前面的数，如果小于前面的数，就将该位置的数字的前一个数，赋值给后一个数(后移）；，然后此时当前判断位置的前一个位置的就是该数字的真正位置。依次循环(元素 - 1次)该操作~

核心代码：?

????????tips：当待插入的数小于已排序部分的元素时，需要将已排序部分的元素后移一位，为待插入的数腾出空间。通过不断自减insertIndex，可以找到待插入的数应该插入的位置。

while (insertIndex >= 0 && arrays[insertIndex] > insertVal) {
                arrays[insertIndex + 1] = arrays[insertIndex];
                insertIndex--;
            }
            //当退出while循环时，说明插入的位置找到，insertIndex + 1
            arrays[insertIndex + 1] = insertVal;

推导过程：

public class SortInsert {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
//        int[] arrays = {101, 34, 119, 4};
        System.out.println("排序前：" + Arrays.toString(arrays));

        int insertVal = arrays[1];
        int insertIndex = 1 - 1;

        while(insertIndex >= 0 && insertVal < arrays[insertIndex]){
            arrays[insertIndex + 1] = arrays[insertIndex];
            insertIndex--;
        }
        arrays[insertIndex + 1] = insertVal;
        System.out.println("排序后：" + Arrays.toString(arrays));

        insertVal = arrays[2];
        insertIndex = 2 - 1;
        while(insertIndex >= 0 && insertVal < arrays[insertIndex]){
            arrays[insertIndex + 1] = arrays[insertIndex];
            insertIndex--;
        }
        arrays[insertIndex + 1] = insertVal;
        System.out.println("排序后：" + Arrays.toString(arrays));

        insertVal = arrays[3];
        insertIndex = 3 - 1;
        while(insertIndex >= 0 && insertVal < arrays[insertIndex]){
            arrays[insertIndex + 1] = arrays[insertIndex];
            insertIndex--;
        }
        arrays[insertIndex + 1] = insertVal;
        System.out.println("排序后：" + Arrays.toString(arrays));

        insertVal = arrays[4];
        insertIndex = 4 - 1;
        while(insertIndex >= 0 && insertVal < arrays[insertIndex]){
            arrays[insertIndex + 1] = arrays[insertIndex];
            insertIndex--;
        }
        arrays[insertIndex + 1] = insertVal;
        System.out.println("排序后：" + Arrays.toString(arrays));

        insertVal = arrays[5];
        insertIndex = 5 - 1;
        while(insertIndex >= 0 && insertVal < arrays[insertIndex]){
            arrays[insertIndex + 1] = arrays[insertIndex];
            insertIndex--;
        }
        arrays[insertIndex + 1] = insertVal;
        System.out.println("排序后：" + Arrays.toString(arrays));
    }
}

?简写后：

public class InsertSort {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
//        int[] arrays = {101, 34, 119, 4};
        System.out.println("排序前：" + Arrays.toString(arrays));
        for (int i = 1; i < arrays.length; i++) {
            //定义待插入的数
            int insertVal = arrays[i];
            int insertIndex = i - 1; //即arr[1]的前面这个数的下标
            //给insertVal 找到插入的位置
            /**说明：
             * 1. insertIndex >= 0 保证在给insertVal 找插入的位置，不越界
             * 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
             * 3. 就需要将 arr[insertIndex] 后移
             */
            while (insertIndex >= 0 && arrays[insertIndex] > insertVal) {
                arrays[insertIndex + 1] = arrays[insertIndex];
                insertIndex--;
            }
            //当退出while循环时，说明插入的位置找到，insertIndex + 1
            if(insertIndex + 1 != i) { //如果找到的位置不是自身的位置
                arrays[insertIndex + 1] = insertVal;
            }
            System.out.println("第" + i + "轮：" + Arrays.toString(arrays));
        }
        System.out.println("排序后：" + Arrays.toString(arrays));
    }
}