插入排序

一、思路

二、结论

1. 在比较的过程中若要移位并不是前后两个数进行交换，而是用前面的数覆盖后面的数
2. 取出来的数最后再插入对应的位置

三、代码

public class InsertSort {
    public static void main(String[] args) {
        int[] array = new int[]{3, 9, -1, 10, 20, 5};
        int[] sore = sore(array);
        System.out.println(Arrays.toString(sore));
    }

    public static int[] sore(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 取出第一个位置的数保存在indexVal中
            int indexVal = array[i];
            // index 指向的是i的前一个数
            int index = i -1;
            // indexVal的值小于比较的值时，进行移位操作，index >= 0 是为了防止角标越界
            while (index >= 0 && indexVal < array[index]){
                array[index + 1] = array[index];
                index--;
            }
            // 由于指向的是i 的前一个数，所以在将indexVal插入会数组中时，要往后挪一位
            array[index +1] = indexVal;
        }
        return array;
    }
}