直接插入排序

概念

直接插入排序顾名思义就是不停的将元素插入到一个有序的元素中。
可以把整体的元素，划分为有序序列和无序序列

• 取出无序序列的一个元素
• 在有序中找到合适的位置
• 将此元素放到有序元素中
  重复上方过程，直到没有无序的元素

步骤

举例有一组数据 6 5 4 3 2 1，利用直接插入排序算法，排序为升序。
有序的元素 【6】（有序序列只有一个元素时必定有序，所以初始就用第一个元素作为有序序列），无序序列【5，4，3，2，1】，

第一轮：
选出无序序列第一个元素5
从有序序列第一个元素（也可以最后一个元素）开始寻找合适的位置，因为5<6,所以索引0是合适的位置
将6后移，5放入位置0，得到有序序列【5，6】，无序序列【4，3，2，1】

第二轮：
选出无序序列第一个元素4
从有序序列第一个元素（也可以最后一个元素）开始寻找合适的位置，因为4<5,所以索引0是合适的位置
将5,6后移，4放入位置0，得到有序序列【4，5，6】，无序序列【3，2，1】

第三轮：
选出无序序列第一个元素3
从有序序列第一个元素（也可以最后一个元素）开始寻找合适的位置，因为3<4,所以索引0是合适的位置
将4，5，6后移，3放入位置0，得到有序序列【4，5，6】，无序序列【2，1】

第四轮：
选出无序序列第一个元素2
从有序序列第一个元素（也可以最后一个元素）开始寻找合适的位置，因为3<4,所以索引0是合适的位置
将3，4，5，6后移，2放入位置0，得到有序序列【2，3，4，5，6】，无序序列【1】

第五轮：
选出无序序列第一个元素1
从有序序列第一个元素（也可以最后一个元素）开始寻找合适的位置，因为3<4,所以索引0是合适的位置
将2，3，4，5，6后移，1放入位置0，得到有序序列【1，2，3，4，5，6】，无序序列【】

点此链接，可以查看在线效果图

Java代码

package sort.insert;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ShaoYJ
 * @date 2022/10/7 周五
 * @desc  得到升序的排序结果
 */
public class InsertSort {
    public static void main(String[] args) {

          Integer[] arr = scanNum();
//        Integer[] arr = {3,2,1};


        System.out.println("排序前:" + Arrays.toString(arr));
        sort(arr);
        System.out.print("排序后:" + Arrays.toString(arr));

    }

    public static Integer[] scanNum(){
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        System.out.print("输入一串数字，空格分开，以#结束:");
        while (!sc.hasNext("#")) {
            int a = sc.nextInt();
            list.add(a);
        }
//       list 转 Integer : 提供首地址即可
        Integer[] arr = list.toArray(new Integer[0]);
        return arr;
    }


    public static void sort(Integer[] arr){

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                //  将j到i-1的都后移一个位置
                if(arr[i] < arr[j]){
                    Integer temp = arr[i];
                    moveArr(arr,j,i);
                    arr[j] = temp;
                    break;
                }
            }
        }
    }

    public static void moveArr(Integer[] arr, int pre,int post){
        for (int j = post-1; j >=pre; j--) {
            arr[j+1] = arr[j];
        }
    }
}