SOURCE

// 插入排序
/**
 * 分为已排序，未排序两个队列
 * 未排序第一个跟已排序最后一个比较
 * 大于则排已排序后面，小于则继续跟前面比
 * 重复上一步，直到排完，插入到最前面
 * [3],[2, 4, 5, 1]
 * [2,3],[4, 5, 1]
 * [2,3,4],[ 5, 1]
 * [2,3,4,5],[1]
 * 
 * [5,2,3,4,1]
 * [5],[2,3,4,1]
 * [2,5][3,4,1]
 * [2,3,5][4,1]
 * [2,3,4,5][1]
 * [1,2,3,4,5]
 */

function insertionSort (arr) {
  var tempArr = [arr[0]];
  var len = arr.length;
  for (let i = 1; i < len; i++) {
    var val = arr[i];
    for (let j = tempArr.length - 1; j >= 0; j--) {
      var tempVal = tempArr[j];
      if(val > tempVal){
        tempArr.push(val);
        break;
      }
    }
    if(val<tempArr[0]){
        tempArr.unshift(val);
    }
    
  }
  return tempArr;
}
var arr = insertionSort([3, 2, 4, 5, 1]);
console.log(arr);