1，算法简介
插入排序的工作原理就是将未排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入。插入排序通常采用占位的形式，空间复杂度为O(1),因此，在从后向前扫描的过程中，需要反复的把已排序的元素逐步向后挪位，为新插入元素提供插入的位置。
2，算法描述
1）从第一个元素开始，该元素可以被认为已经被排序
2）取出下一个元素，在已经排好序的序列中从后往前扫描
3）直到找到小于或者等于该元素的位置
4）将该位置后面的所有已排序的元素从后往前依次移一位
5)将该元素插入到该位置
6)重复步骤2~5
理解步骤看注释
//插入排序 O(n*n)
function MySort3(arr) {
var len = arr.length;
//此处i = 1，从第二个元素开始匹配，默认第一个元素已经排序，此处跟下面while循环的 j>=0 保留一个就行，另一个没有意义
for (var i = 1; i < len; i++) {
var current = arr[i];//记录当前需要插入排序的元素，避免下面while循环被覆盖
// 以arr[i]为分界线，前面的是已经排序的，后面是未排序的
var j = i - 1; //最开始while循环之前 j 是默认已排序的元素中的 最后一个的索引，此处每次for循环会重新定义j
while (j >= 0 && arr[j] > current) { //在已排序好的队列中从后向前匹配
arr[j + 1] = arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置
j--;
}
// 直到while循环不满足条件才会执行
arr[j + 1] = current;
}
return arr
}
let arr3 = [5, 7, 9, 3, 4, 5, 6, 1, 2, 3, 7, 5, 4, 1, 2]
console.log('插入排序：', MySort3(arr3))