SOURCE

/**
 * 参考文档：https://www.cnblogs.com/cc-freiheit/p/10983395.html
 * 描述：是一种描述简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排列数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 实现逻辑
 * 一般来说，插入排序都采用in-place（原位操作，即不允许移动）在数组上实现
 * （1）从第一个元素开始，该元素可以认为已经被排序
 * （2）取出下一个元素，在已经排序的元素序列中从后向前扫描
 * （3）如果该元素（已排序）大于新元素，将该元素移到下一位置
 * （4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * （5）将新元素插入到该位置后
 * （6）重复步骤2~5
 */

function Insertion(arr) {
    let len = arr.length
    let preIndex, current
    for (let i = 1; i < len; i++) {
        preIndex = i - 1
        current = arr[i]
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex]
            preIndex--
        }
        arr[preIndex + 1] = current
    }
    return arr
}

console.log(Insertion([5, 1, 27, 4]))