public class StraightInsertionSort {
    public static void main(String[] args){
        //定义一个待排元素数组
        Integer[] arr = {5,2,7,3,9,10,8,6,1,4};
        insertSort(arr);
        System.out.println("最终排序结果为"+Arrays.toString(arr));
    }
    //假设从小到大排序
    public static void insertSort(Integer[] arr){
        //寻找元素arr[i]合适的插入位置，i是当前元素
        for (int i = 1; i < arr.length; i++) {
            //记录待排元素的值
            int temp = arr[i];
            int position = i;
            //j是从i-1开始向前移动的，并且每次与arr[i]判断大小
            for (int j = i-1; j >= 0 ; j--) {
                //如果temp小于arr[j]，就说明temp当前至少要插入到arr[j]的前面
                if(temp < arr[j]){
                    //记录后移
                    arr[j+1] = arr[j];
                    position = j;
                }else {
                    break;
                }
            }
            //插入到正确位置
            arr[position]=temp;
            //输出每一步排序的结果
            System.out.println("第"+i+"轮排序结果为"+Arrays.toString(arr));
        }
    }
}