排序算法汇总

ZiHao...大约 2 分钟

归并排序

排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序采用的是分治思想。

分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

const mergeSort = (arr) => {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let middle = Math.floor(len / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
};
//
const merge = (left, right) => {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
};
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time("归并排序耗时");
console.log("arr :", mergeSort(arr));
console.timeEnd("归并排序耗时"); // 大约 8ms

快速排序

快速排序的特点就是快，而且效率高！它是处理大数据最快的排序算法之一。

思想

先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
左右分别用一个空数组去存储比较后的数据。
最后递归执行上述操作，直到数组长度 <= 1;

缺点：需要另外声明两个数组，浪费了内存空间资源。

const quickSort = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  // 取基准点的值
  const valArr = arr.splice(middle, 1);
  const middleIndexval = valArr[0];
  const left = [];
  const right = [];
  // 遍历数组
  for (let val of arr) {
    if (val < middleIndexval) {
      left.push(val);
    } else {
      right.push(val);
    }
  }
  return quickSort(left).concat(middleIndexval, quickSort(right));
};
const array2 = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time("快速排序");
console.log("quickSort1 ", quickSort(array2));
console.timeEnd("快速排序"); // 8ms 在数据量比较大的情况下，