插入排序

caution

插入排序在面试中出现的频率是较高的，需要重视！

排序的效果图

解法

当前解法为升序

function insertionSort(arr){
    const len = arr.length;

    // 注意，i 从 1 开始
    for(let i = 1; i < len; i++){
        let preIndex = i - 1;
        let current = arr[i];

        // 位置i之前，是已排好序的数字，while的作用是找到一个坑位，给当前数字current插入
        while(preIndex >= 0 && arr[preIndex] > current){
            arr[preIndex+1] = arr[preIndex]; // 对大于current的值，往后移一位，给current的插入腾出位置
            preIndex--;
        }
        arr[preIndex+1] = current;
    }

    return arr;
}