插入排序

[Geekhyt]

插入排序顾名思义，对于未排序的数据，在已排序的序列中从后往前扫描，找到相应的位置进行插入，保持已排序序列中元素一直有序。

从 i 等于 1 开始遍历，拿到当前元素 curr，与前面的元素进行比较。

如果前面的元素大于当前元素，就把前面的元素和当前元素进行交换，不断循环直到未排序序列中元素为空，排序完成。

const insertSort = function(arr) {
    const len = arr.length
    let curr, prev
    for (let i = 1; i < len; i++) {
        curr = arr[i]
        prev = i - 1
        while (prev >= 0 && arr[prev] > curr) {
            arr[prev + 1] = arr[prev]
            prev--
        }
        arr[prev + 1] = curr
    }
    return arr
}

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)
• 稳定