概念
插入排序(insertion Sort) 是一种简单直观且稳定的排序算法
如果一个有序的数据序列，再这中间插入一个数据，使得插入之后的数据序列仍然有序，就需要用到插入排序算法，适用于少量的数据排序。
插入排序算法将要排序的数组分成两部分，第一部分这个数组的有序序列，第二部份就是未排序的序列，将第二部分的数据逐个放入第一部分序列当中，最后形成有序的序列。
插入排序(copy过来的).jpg
原理
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
插入排序步骤.jpg
时间复杂度： 如果是正序的，时间复杂度是O(n),若不是，则为O(n²)
算法稳定性：将无序区域的某个值插入到有序区域，不会影响原先两个相同值的前后位置，所以为稳定排序。
算法实现
直接插入
// 将大的数往后调
function insertionSort(arr) {
// 判断是否是数组，不是则抛出错误
if(!Array.isArray(arr)) {
throw new Error('传入的不是数组')
}
const len = arr.length;
// 判断长度是否小于等于1，是则直接返回
if(len <= 1) {
return arr;
}
/*
*/
let current;
// 从索引为1的值开始，第0个为有序的
for (let i = 1; i < len; i++) {
current = arr[i];
let ind = i;
// 索引大于0，且之前的值比current要小，则将索引为ind-1的值赋值给索引为ind的值
while(ind > 0 && current < arr[ind-1]) {
arr[ind] = arr[ind-1];
ind--;
}
// 判断ind和i相不相等，相等则不需要赋值
if(ind !== i) {
arr[ind] = current
}
}
return arr
}
