public class Test {

    public static void main(String[] args) {
        int[] arr = new int[]{5,2,4,6,7,1,3};
        insertionSort(arr);
    }


    public static void insertionSort(int[] arr){
        System.out.println("原始數組："+ Arrays.toString(arr));
        //獲取數組長度
        int len = arr.length;
        // 循環 len-1 次，進行數組排序。第一次將數組的第一個元素視為已排序的部分，
        // 每次將未排序部分的第一個元素插入到已排序的部分。
        for(int i = 1 ; i< len ; i++){
            //目標元素，未排序部分的第一個元素，即當前循環中要插入排序的元素
            int target  = arr[i];
            //已排序元素中的最后一個元素的下標
            int j = i-1;

            // 循環已排序的部分的數組，找到目標元素應該存放的下標
            while (j>= 0 && arr[j] > target ){
                // 如果插入元素小于當前元素，則將當前元素后移一位
                arr[j+1] = arr[j];
                // 當前已排序的數據比較元素的下標前移一位
                j--;
            }
            //將目標元素插入到正確的位置
            arr[j+1] = target;
            // 打印每趟排序完成后的數組狀態，以便查看排序進度
            System.out.println("第"+i+"趟排序完成的數組："+ Arrays.toString(arr));

        }
        System.out.println("排序完成的數組："+ Arrays.toString(arr));

    }
}