插入排序
通过构建有序序列，未排序的数列，在已排好序数列，从后向前扫描，找到相应的位置并插入。
代码
js
// 插入排序
function insertionSort(arr) {
// 外层循环控制趟数，n 个 数 需要 n-1趟
for (let i = 1; i < arr.length; i++) { // 从第二个数开始插入，第一个数默认为排好序的
let preIndex = i - 1 // 记录前一个值的索引（有大量的前一个值 后移的操作）
let cur = arr[i] // 当前需要被插入的值（表示未排好序序列）
// 内层循环不能确定比较次数，倒着遍历前面已经排好序的数组，进行移位操作
while (preIndex >= 0 && arr[preIndex] > cur) { // 移位操作
arr[preIndex + 1] = arr[preIndex] // 前一个值后移
preIndex-- // 倒着遍历
}
// 发现前一个比自己小的时候，说明找到自己该插入的位置了，插入这个值
arr[preIndex + 1] = cur
}
}
/*
插入排序，未排好序的数列，从后向前扫描已经排好序的数组，在指定位置上插入
开销都在替换上了，因为如果前面一坨排好序的，需要再首位插入，所有的数都要后移一位
假设有 n 个数 也需要走n-1趟
内层的循环优化了，插入的时候是 未排好序的向排好序的数组里插，不能确定比较次数
*/
let arr = [10, 7, 9, 11, 22, 33, 4, 2]
insertionSort(arr)
console.log(arr); //
/*
[
2, 4, 7, 9,
10, 11, 22, 33
]
*/