前言
经典的排序算法，很多人都听过，很多人也许用过，但是也有很多人，听过没见过。为什么呢？现在我们有了越来越多的框架、依赖包，我们将能用到排序的实际场景，作为业务将其封装成了函数，所以，一些人只知函数而不知其运行逻辑。
基于以上，为了让自己更好的理解函数运行逻辑，整理了一些基本排序的方法的运行规则，以及部分个人理解，希望能给大家一些帮助。
本文将讲述插入排序。
插入排序
插入排序（InsertionSort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序可以理解为日常打牌或打麻将，将摸到的无序的牌整理为有序的牌。
插入排序实现原理
- 默认第一个元素为有序序列，而第二个元素到末尾的元素为无序序列；
- 以有序序列的下一个元素为目标值，使目标值和有序序列进行遍历比较；
- 目标值和有序序列元素进行比较；
- 当目标值大于有序序列元素，则和下一个元素比较；
- 当目标值小于等于有序序列元素，则将目标值插入至此此位置；
- 重复步骤2-5；
代码
function insertionSort(array) {
let length = array.length;
let preIndex, current;
// 从第二个数开始循环
for (let i = 1; i < length; i++) {
// 当前数的前一个index开始对比
preIndex = i - 1;
// 当前需要插入的数据，用current空间参数存起来
current = array[i];
// 进入二次循环，该循环用来对比排序完成的数与当前需要插入的数据
while (preIndex >= 0 && current < array[preIndex]) {
// 因为当前值已经被抽出，它的序号比需要对比的数的最大序列大1，所以当满足条件，可以把preIndex + 1的序列的值赋值为 // preIndex
array[preIndex + 1] = array[preIndex];
// 继续循环
preIndex--;
}
array[preIndex + 1] = current; // 外层完成一次循环后，把找到的当前小于current 的前一位数替换成插入元素
}
console.log('insertionSort result:', array);
}
insertionSort([9, 1, 0, 2, 3, 8, 6, 3]);
输出值
双for循环写法
function insertionSort2(array) {
let length = array.length;
let preIndex, current;
// 从第二个数开始循环
for (let i = 1; i < length; i++) {
// 当前数的前一个index开始对比
preIndex = i;
// 当前需要插入的数据，用current空间参数存起来
current = array[i];
let twoCurrent;
// 进入二次循环，该循环用来对比排序完成的数与当前需要插入的数据
for (let j = i - 1; j >= 0; j--) {
if (array[j] > current) {
let temp = array[preIndex];
array[preIndex] = array[j];
array[j] = temp;
preIndex = j;
} else {
break;
}
}
}
console.log('insertionSort2 result:', array);
}
insertionSort2([9, 1, 0, 2, 3, 8, 6, 3]);
输出值
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)
寄语
插入排序的应用场景很多，变种包括二分法排序，基础牢固才能更好的进行优化，加油吧，各位！
思考是进步的阶梯
