插入排序

1. 原理
   （1）默认数组中第1个数字已经排好序
   （2）取出下一个数字，在已经排好序的序列中遍历
   （3）把取出的元素放在排好序数字中的合适位置
   （4）重复2~3

就像排队一样，每次抽一个学生出来，然后插入到已经排好的学生当中。

2. 举例
   假如升序排序。

[10, 8, 9, 47, 3]

第一轮：最开始10是排好的数字，然后从8开始与10比较，那么8就插入到10的前面。

[8, 10, 9, 47, 3]

第二轮：8和10已经属于排好位置的数字，拿9和前面的数字比较，9比10小，然后再向前比较，9比8大，所以9插在8和10之间。

[8, 9, 10, 47, 3]

以此类推。

3. 代码
   JS版本 (对排好序的数字，从前向后比较)

function insertSort(arr) {
    for(let i=1; i < arr.length; i++) { //  默认第一个数字已经排好序，从第二个数字开始比较
        for(let j = 0; j < i; j++) {    //  这个是遍历已经排好序的部分
            if(arr[i] < arr[j]) {
                // 如果arr[i]小于当前已经拍好的数字，则直接插入，后面的数字不需要再比较了
                //  否则，j++来找到比arr[i]大的数字
                arr.splice(j, 0, arr[i]);   // 在数组中下标为j这个位置删除0个元素，插入元素arr[i], 改变了arr数组
                arr.splice(i+1, 1); //  删除之前被比较的数字，由于上行代码改变了arr，所以之前的元素位置是i+1
                break;
            }
        }
    }
    return arr;
}

普通版本（对排好序的数字，从后向前比较）

function insertSort(arr) {
    for(let i=1; i < arr.length; i++) { //  默认第一个数字已经排好序，从第二个数字开始比较
        let temp = arr[i];  //  用temp记录当前被比较的元素
        for(var j = i; j > 0 && arr[j-1] > temp; j--) { // 这个循环是为了找到temp在排序好元素中合适的位置，然后把之后的元素向后移动。
            arr[j] = arr[j-1]
        }
        // 移动完后，把temp放入那个合适的位置
        arr[j] = temp;
    }
    return arr;
}

参考：https://zhuanlan.zhihu.com/p/45638675