插入排序(insertSort)

排的是真的慢！

思路

类似于打扑克的时候整牌会按照顺序插入

创建一个自己的数组初始空数组(可以直接用原数组做到原地 pai'xu)
把原数组的第一项 push 进自己数组
拿原数组的除第一项的 item去和自己数组的每一项依次比较
如果原数组的 item 和自己的数组每一项都比过
如果原数组的 item 比自己数组每一项都大 则插入到自己数组最后
如果原数组的 item 比自己数组的第 T 项小或者相等 则自己数组从 T 开始包括 T 都往后位移一个位置 (这时第 T 项变为了 T+1) 腾出来的 T 位置插入原数组的 item
就这样原数组的 item 一直找自己数组的位置插

例如:
初始值 (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); //结果不会去重

简洁版

依次比较当前值与已排序的值，找到当前值在之前已排序的数组中的合适位置，将其插入。

let arr = [53, 2, 2, 6, 63, 312, 23, 6, 74, 6, 2, 8, 856, 85, 75, 4, 7, 8, 9, 9];

function insertSort(arr: Array<number>): Array<number> {
  if (!arr.length) return null;

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[i] < arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
}

insertSort(arr);
console.log(arr);

学到了什么

就是学到了一种新的排序思想……

未解

怎么在 insertSort 中加入去重？

插入排序(insertSort) ​

思路 ​

实现 ​

学到了什么 ​

未解 ​

插入排序(insertSort)

思路

实现

学到了什么

未解