>[success] # 插入排序 [不错的文章先读一下](https://juejin.im/post/6844904167778041869#heading-0) ~~~ 1.引用书里的话来说，插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。 接着， 它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确 排序， 接着和第三项比较（它是该插入到第一、第二还是第三的位置呢），以此类推。 2.通俗的理解'插入排序'和'选择排序' 在整体思路方面差不多，首先'插入排序'也是将整个排序分成两个区间， 分别是'排序区间'和'未排序区间',每次会从'未排序区间'中取值去以排序区间中比较，比较后将这个值插入到 '以排序区间' 3.'插入排序'和'选择排序' 做个比较理解，'插入'是从'未排序区间'取值在'以排序区间去比较'，'选择'是从'未排序区间' 依次找到最小值放到'以排序区间' 4.如图红色区域就是'已排序区间'，黄色就是'未排序'区间，依次从黄色区域取值去红色区域比较，并且将值插入到 合适的红色区域 ~~~   >[info] ## 代码实现 * 通用方法 ~~~ // 生成随机数数组 function randomArray(max, min, len) { let randomNum = 0 const array = [] for (let i = 0; i < len; i++) { randomNum = Math.floor((Math.random() * (max - min + 1)) + min) array.push(randomNum) } return array } const array = randomArray(1, 10, 5) const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0 }; function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; } ~~~ >[danger] ##### 代码效果 ~~~ 1.这里默认将第一个元素作为'已排序'区间中的内容，这样方便后续逻辑 2.通过过动态图来理解下面插入算法中的while逻辑，首先是吧整个数组分成两个区域 '已排序区域' 一个是 '为排序区域'，第一层for是从为排序区域取出一个，'已排序区域'就是 从当前这个值往后都是以排序区域，因此while 的判断循环j 是从取点位置开始的，注意 动图插入的那个动作，如果你比我小我就把你往后移动，如果你比我大我就到大了位置， 整个while 就结束了，这个值就到了j的位置 ~~~ ~~~ // 插入排序 function insertionSort(array, compareFn = defaultCompare) { const { length } = array; let temp; for (let i = 1; i < length; i++) { let j = i; temp = array[i]; while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) { array[j] = array[j - 1]; j--; } array[j] = temp; } return array; }; insertionSort(array) console.log(array) ~~~