插入排序

特点：从第二个元素开始，依次和左边的元素比较，如果比左边小，则插入到左边，整体向右移动，保证左边的排序是正常的

public class InsertSort {

    public static void main(String[] args) {
        //插入排序
        //思路：从第一项开始，逐个和前一个比较，如果小则插入到前面，能够保证左侧元素都是已经排好序的
        int[] arr = {4,3,7,2,8,1,9};
        
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && (arr[j] < arr[j-1]); j--) {
                //交换位置，插入到前面
                int temp  = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}