import java.util.Arrays;

/**
 * @author WanJl
 * @version 1.0
 * @title Demo06
 * @description 数组排序-插入排序
 * @create 2026/7/16
 */
public class Demo06 {
    /*
        插入排序
        是三种基础排序中最实用的一种，也是使用最广泛的一种O(n2)排序算法，他的思想非常符合人整理东西的习惯。
        把数组分为“已排序”和“未排序”两部分，每次从未排序部分 取一个元素，插入到已排序部分的正确位置。
        就类似于 打扑克 时，抓牌然后 插入到手中已排序好的牌中正确的位置。
        核心思想：
            把数组视为“已排序”（前部分）和未排序（后部分）。每次从未排序部分中拿取第1个元素，
            从后往前在已排序部分中找到合适的位置（比较）并插入
     */
    public static void main(String[] args) {
        /*
            插入排序
            把数组分为两部分：已排序、未排序
            每次取未排序的第1个元素插入到已排序的正确位置
         */

        int[] arr={1,456,782,5,8,4,598,1,46,68,465,74};
        //我们要从第2个元素开始，到长度减1，这个区间，暂时假定为未排序区间
        //从第2个元素开始，假设 arr[0]已经是已排序部分
        for (int i = 1; i <arr.length; i++) {
            //获取当前要插入的元素，未排序的第1个
            int current=arr[i];
            //已排序部分的最后一个索引值
            int j=i-1;
            //从后往前扫描已经排序部分，寻找插入位置
            //如果已排序的元素大于current，就向后移动一位。
            while (j>=0&&arr[j]>current){
                arr[j+1]=arr[j];
                j--;
            }
            //这个时候 j+1 就是current应该插入到的位置
            arr[j+1]=current;
            System.out.println("第"+(i)+"轮插入后："+ Arrays.toString(arr));
        }
    }
}