首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元 素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到 合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元 素为空，算法结束。
虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n2)，但是如果我们希望把性能 优化做到极致，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间，我们只是讲了最 基础的一种。如果你对插入排序的优化感兴趣，可以自行学习一下希尔排序。
const insertionSort = function(arr, len) {
if (n <= 1) return;
for (let i = 1; i < len; ++i) {
let value = arr[i];
let j = i - 1;
for(; j >= 0; --j) {
if (arr[j] > value) {
arr[j + 1] = arr[j]; // 数据移动
} else {
break;
}
}
arr[j + 1] = value; // 插入数据
}
}
const insertionSort = function(arr, len) {
for (let i = 1; i <= len; ++i) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}基本的知识都讲完了，我们来看开篇的问题:冒泡排序和插入排序的时间复杂度都是 O(n2)，都是 原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢? 我们前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固 定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据 的逆序度。 但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。我们来看这段操作:
冒泡排序中数据的交换操作:
if (a[j] > a[j+1]) { // 交换
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}插入排序中数据的移动操作:
if (a[j] > value) {
a[j + 1] = a[j]
} else {
break;
} 我们把执行一个赋值语句的时间粗略地计为单位时间(unit_time)，然后分别用冒泡排序和插入排 序对同一个逆序度是 K 的数组进行排序。用冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语 句，所以交换操作总耗时就是 3*K单位时间。而插入排序中数据移动操作只需要 K个单位时间。 这个只是我们非常理论的分析，为了实验，针对上面的冒泡排序和插入排序的 Java 代码，我写了 一个性能对比测试程序，随机生成 10000 个数组，每个数组中包含 200 个数据，然后在我的机器上 分别用冒泡和插入排序算法来排序，冒泡排序算法大约 700ms 才能执行完成，而插入排序只需要 100ms 左右就能搞定!