排序

先准备一个数组：

let ary = [];
for (let i = 100; i > 0; i--) {
  ary.push(Math.floor(Math.random() * 100))
}
console.log(ary.length)

下面介绍各种排序的思想和代码。

sort排序：

　　在数组的一些方法这篇文章中也有介绍 sort 方法

console.time("b")
ary.sort((a, b) => a - b) //a为前一项，b为后一项，所以可以进行[{n:3},{n:2},{n:1},...]的排序
console.log(ary);
console.timeEnd("b")

1.判断插入（我最喜欢，简单易懂）

Array.prototype._sort = function () {
  const _this = [...this];
  let ary = [];
  _this.forEach((item, index) => {
    if (ary.length <= 2) { // 省略前两次不必要的循环
      ary.push(item)
    } else {
      const leftAry = [],
        rightAry = [];
      for (let i = 0; i < ary.length; i++) {
        if (ary[i] <= item) { // 做判断，拆成两个数组
          leftAry.push(ary[i])
        } else {
          rightAry.push(ary[i])
        }
      }
      ary = [...leftAry, item, ...rightAry] // 插入新值
    }
  })
  return ary
}
console.log(ary._sort())

以下方法可供参考，打开思路

2.冒泡排序：

核心原理：建立循环，让第 i 位和 i + 1 位进行对比、判断、换位

console.time("a")
for (let j = 0; j < ary.length - 1; j++) { //length - 1 ,因为要i和i+1项对比，不-1，最后一个i+1为undefined
  let onOff = true;
  for (let i = 0; i < ary.length - 1 - j; i++) { //每一次循环都能找到最大值，所以-j，减少没必要的对比。
    if (ary[i] > ary[i + 1]) {
      let a = ary[i];
      ary[i] = ary[i + 1];
      ary[i + 1] = a;
      onOff = false
    }
  }
  if (onOff) { //如果小循环已经是从小到大排序了，onOff就永远为true。
    break; //当不再进入小循环的时候，跳出（结束）大循环
  }
}
console.log(ary);
console.timeEnd("a")

3.插入排序：

插入排序跟整理扑克牌是一样的，即每次拿到一个数，按大小顺序将其插入到有序的数组中。

首先初始化第一个元素为有序数列，取出一个无序数列中的元素按大小顺序插入有序数组中。

console.time("c")
function insertSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    // 将要插入的数
    let temp = arr[i];
    // 有序数列
    for (var j = i - 1; j >= 0; j--) {
      // 要插入的数与有序数列一一比较
      if (temp < arr[j]) {
        arr[i] = arr[j]
        arr[j] = temp;
        i--;
      }
    }
  }
  return arr;
}
console.log(insertSort(ary))
console.timeEnd("c")

4.快速排序：

先取出一个数作为基准

然后把大于这个数的放到它右边，小于等于这个数的放到左边

再对左右区间重复第二步，直到各区间只有一个数

console.time("d")
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  // 基准位置（理论上可任意选取）
  var idx = arr.length - 1;
  // 基准值
  var num = arr[idx];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length - 1; i++) {
    if (arr[i] <= num) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  // 会先将左边的排序好再开始对右边进行排序
  return quickSort(left).concat([num], quickSort(right));
}
console.log(quickSort(ary))
console.timeEnd("d")

5.希尔排序：

希尔排序也叫递减增量排序算法，是插入排序的升级版。

先将无序数组分割成若干子序列，子序列是相隔特定增量的子序列，对每个子序列进行插入排序

然后再选择一个更小的增量，再将之前排序后的数组按这个增量分割成多个子序列

不断选择更小的增量，直到增量为1时，再对序列进行一次插入排序，使序列最终成为有序序列

console.time("e")
function shellSort(arr) {
  var gap = Math.floor(arr.length / 2);
  while (gap > 0) {
    for (var i = gap; i < arr.length; i++) {
      var temp = arr[i];
      for (var j = i; j - gap >= 0 && arr[j - gap] > temp; j = j - gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}
console.log(shellSort(ary))
console.timeEnd("e")

6.选择排序：

在未排序的数组中找到最小元素，存放到数组起始位置

从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾

重复第二步，直到所有元素排序完毕好处：不占用额外的内存空间，坏处：时间复杂度为O(n ^ 2)，所以数据规模越小越好

console.time("f")
function selectSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var minIdx = i;
    // 找到未排序序列中的最小值
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    // 将最小值放到已排序序列的后面
    var temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
  }
  return arr;
}
console.log(selectSort(ary))
console.timeEnd("f")

总结：在数据量不是非常庞大的情况下，不是很容易比较到底哪个算法更快，每次结果都有细微的差异，综合来看，用 sort 就完了。

排序