算法学习：插入排序
chrome v8的 Array.sort 函数实现中（710行），当数组的长度小于等于22时，使用的就是插入排序，大于22使用的是快速排序。
场景
插入排序是一种非常简单的算法，最适合大部分已经被排好序的数据。在开始之前，通过可视化演示算法如何运作一个好主意。你可以参考前面的动画来了解插入排序的工作原理。
当输入的数组已经大部分被排好序时，插入排序的效果最佳。
问题分解
- 数组分成2部分
- 有序部分：第一个元素
[ arr[0] ] - 其它元素：
arr.slice(1)
- 有序部分：第一个元素
- 实现一个
insert方法：将一个元素，插入到一个有序的数组中去 - 组合
1/2部分，实现插入排序
分步实现
var arr = [4, 2, 1, 3];
// 1. 将一个元素，插入到一个有序的数组中去
function insert(el, arr) {
// el: 3; arr: [1,2,3,5,6]
var idx = -1;
for (var i = 0; i < arr.length; i++) {
var cur = arr[i];
if (el < cur) {
idx = i;
break;
}
}
if (idx === -1) {
arr.push(el);
} else {
arr.splice(idx, 0, el);
}
}
// 2. 两个数组，一个有数，一个无序，按插入排序的方式进行排序
function isort(ordered, unordered) {
// target: ordered
for (var i = 0; i < unordered.length; i++) {
var cur = unordered[i];
insert(cur, ordered);
}
return ordered;
}
// 3. 将一个数组进行拆分成两个数组，一个为arr[arr[0]], 另一个为其它
function iisort(arr) {
var ordered = [arr[0]];
var unordered = arr.slice(1);
return isort(ordered, unordered);
}
console.log(iisort([4, 2, 1, 3, 12, 1, 2, 5]));
// [1, 1, 2, 2, 3, 4, 5, 12];参考
https://www.cnblogs.com/echolun/p/12644008.html
https://juejin.cn/post/6844903842866266125
https://segmentfault.com/a/1190000015489767