插入排序(insertSort) #

例如:
初始值 (5) [3, 2, 1, 4, 5]


数组 []
我和你的每一项去比 3

数组 [3]
我和你的每一项去比 2

数组 (2) [2, 3]
我和你的每一项去比 1

数组 (3) [1, 2, 3]
我和你的每一项去比 4

数组 (4) [1, 2, 3, 4]
我和你的每一项去比 5


排序后 (5) [1, 2, 3, 4, 5]

//宏观逻辑
function sort(elements) {
  // 创建一个自己的数组
  var res = [];

  // 遍历原数组
  elements.forEach((item) => {
    //传入自己创建的数组 和原数组的每一位去比较
    compare(res, item);

    console.log("自己的数组", res);
    console.log("自己数组item和原数组的这一项去比", item);
  });

  return res;
}

//比较逻辑
//传入值为自己创建的数组 和原数组的item
//这里传入的arr为上面自己造的res 栈地址是一样的 所以这个函数里操作arr 就是在改自己造的数组
function compare(arr, x) {
  //自己创建的数组的length
  var len = arr.length;

  // 开关
  var temp = false;

  //遍历自己创建的数组
  for (var i = 0; i < len; i++) {
    //如果第一次进来就直接插进去 退出拿原数组第二个来比 要不然undefined怎么比？
    if (len == 0) {
      arr.push(x);
      break;
    }

    //如果原数组的item 小于等于 自己创的数组的某一项
    if (x <= arr[i]) {
      //从后循环自己创建的数组到大于等于原数组的那个值的下标结束
      for (var j = len; j > i; j--) {
        //自己创建的数组从 大于原数组的那个值的下标哪里都往后推一项
        arr[j] = arr[j - 1];
      }

      //并且把原数组item插入进入
      arr[i] = x;

      //打开开关
      temp = true;

      //结束 循环 因为已经插入数值 不能在比了
      break;
    }
  }

  //如果自己创建的数组里的每一项 都比原数组的item小 就把他添加到自己创建数组的最后去
  !temp && arr.push(x);
}

//测试代码……

let a = [3, 2, 1, 4, 5];
// let a = Array(10).fill(1).map(() => {
// return Math.floor(Math.random() * (Math.floor(1000) - Math.ceil(0)) + Math.ceil(0))
// })
console.log("初始值", a);
console.time();
let b = sort(a);
console.timeEnd();

console.log(b === a); //false
console.log("排序后", b); //结果不会去重