插入排序
思路：
将数组分成两部分：有序部分和无序部分，不断的从无序部分中拿出元素插入到有序部分中，在这个过程中使有序部分一直保持有序，直至无序部分中的元素全部插入有序部分
具体实现代码：
function Insertion(arr) {
let len = arr.length;
let preIndex, current;
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && current < arr[preIndex]) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
var arr = [9, 3, 8, 5, 2, 7, 0, 6, 1, 4];
console.log(Insertion(arr));
代码分析：
一共两层循环，外循环和内循环，有序部分最开始为第一个值arr[0]，外层循环的目的是拿到无序部分中的第一个元素（下标为i,值为current），内层循环的目的是为了将current与有序部分中的值（arr[preIndex]）对比，如果比它小（假设我们的排序是从小到大排序），我们就让有序部分中的这个值（arr[preIndex]）往后挪一位（代码中就是：arr[preIndex + 1] = arr[preIndex]），我一开始没想明白，按照冒泡排序的写法应该是替换位置，但是这里不是替换位置而是直接覆盖后面一位的位置，这样就会导致最后那个丢失，其实没有丢失我们保存起来了--current，最后我们再把找到的最终位置给他替换成current，这样就实现了每次内循环我们都把current 插入到了对应顺序的位置。
