/**
 * 插入排序
 */
public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {2,4,7,5,3,6,8,9,1};
        insertionSort(arr);
    }
    /**
     * 插入排序的原理:
     * 将待排序数组看成两部分: 有序数组和无序数组，初始时，第一次可以将第一张看成有序数组，其余作为无序数组
     *  无序数组插入到有序数组中，遍历无序数组（无序数组个数就是需要插入的次数）
     *      将有序数组的右侧第一张和 无序的第一张，
     *         如果 从有序的右侧起: 获取无序的元素小于于有序的元素的第一个元素的索引，有序的这些元素向右移动一位
     *                           同时当前的索引值+1的位置就是 插入的元素
     */
    public static void insertionSort(int[] arr){
        //外层为 要插入的元素
        for (int i=1;i<arr.length;i++){
            //有序位置的最后一个元素
            int tmp = arr[i];
            //获取要插入的元素的位置
            int j = i - 1;
            //从右侧起，获取第一个比要插入的元素小的元素的索引，索引右侧的值 右移一位
            while (j>=0 && arr[j]  > tmp){
                arr[j+1] = arr[j];
                //arr[j] = tmp;
                j--;
            }
            arr[j+1] = tmp;
            System.out.println(Arrays.toString(arr));
        }
    }
}