什么是快速排序（quickSort）？

主要分成两部分实现，分区、递归操作。

  • 分区

从数组中任意选择一个 “基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基本后面。

  • 递归

递归地对基准前后的子数组进行分区。

算法步骤

  1. 首先获取数组的第一个值（作为基准）
  2. 遍历当前数组，从第二个值开始，比基准元素小的 push 到 left 数组，比基准元素大的 push 到 right 数组。
  3. 分别对 left 和 right 数组进行快速排序（递归）
  4. 直到当前进行快排的数组长度为 1
  5. 开始合并，返回排列好的数组
  6. 完成排序

动画演示链接

https://visualgo.net/zh/sorting

快速排序 - 图1

示意图

快速排序 - 图2

代码实现

  • 时间复杂度：O (n * logn)

  • 空间复杂度：O (1) ```javascript Array.prototype.quickSort = function () { const rec = (arr) => {

    1.   if (arr.length <= 1) return arr;
    3.   const mid = arr[0];
    4.   const left = [];
    5.   const right = [];
    7.   for (let i = 1; i < arr.length; i++) {
    8.       if (arr[i] < mid) {
    9.           left.push(arr[i]);
    10.       } else {
    11.           right.push(arr[i]);
    12.       }
    13.   }
    15.   return [...rec(left), mid, ...rec(right)];

    };

    const res = rec(this);

    res.forEach((n, i) => {

    1.   this[i] = n;

    }); };

const arr = [5, 4, 3, 2, 1];

arr.quickSort(); // [1, 2, 3, 4, 5] ```

上方代码中递归的复杂度是 O (logn)，只要是涉及到分成两半的都是 logn 。分区操作的时间复杂度为 O (n)，因为循环遍历了 arr 数组。所以整体的时间复杂度为 O (n * logn)。空间复杂度为 O (1)，因为没有线性增长的变量。