SOURCE

// 思路
// 外层循环记录当前值 里层循环以当前值前一位开始
// 从后往前遍历 遇到比当前值大的 就往后移一位
// 直到前面的已经排好序 比当前值小 又因为大的往后移了
// 中间就出现空缺 就将当前值插到此处

function fn(list) {
    // 从第二个元素开始遍历 默认前面的已排序
    for (let j = 1; j < list.length; j++) {
        let current = list[j] // 记录当前值
        let pre = j - 1 // 前一个元素索引
        //  将当前元素与已排序部分的元素比较 找到合适的位置插入
        while (pre >= 0 && list[pre] > current) {
            list[pre + 1] = list[pre] // pre位置的值往后移
            pre-- // 往前移
        }
        // 此时小于current的没动 大于current的都往后移了一位
        // 中间空了 将current插到此处
        // 注意 此时pre因为最后pre-- 在目标位置前一位
        list[pre + 1] = current
    }
}

// 验证
let list = [4, 3, 2, 10, 12, 1, 5, 6]
fn(list)
console.log('插入排序：' + list) // [1,2,3,4,5,6,10,12]