插入排序

插入排序的基本思想是：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素为新元素，在已经排序的元素序列中从后向前扫描
3. 如果已排序元素大于新元素，将已排序元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2～5 遍历整个序列

public class MyTest {
    public static int[] mySort(int[] arr){
        for(int i = 1; i <arr.length;i++){
            int key = arr[i]; // 定义待插入的新元素
            int j = i - 1; // 定义已排序中第一个与新元素比较的元素
            while (j >=0 && arr[j] > key){ // 已排序的元素比新元素大，将已排序的元素向后移一位
                arr[j + 1] = arr[j]; // 将j向后移动一位，就是将j+1的值赋给j
                j--; // j向前移动一位，再次与待插入的元素比较
            }
            arr[j+1] = key; //  当arr[j] <= key时，找到要插入的位置
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {5,2,4,6,1,3};
        System.out.println(Arrays.toString(mySort(arr)));
    }
}