JavaScript 之快速排序

Question

快速排序，简称 快排，是最常见的算法之一。桶排序 虽然快，但是空间消耗大，冒泡排序 利用的空间较为合理但是 O(n²)，显然在数据量较大时不够快。快速排序 算是从两者取长补短的算法。

原理

以升序为例：

1. 在数据中选一个作为 基准数。（一般习惯选择中间的数，但选择其他数也可以）
2. 将所有的数据进行遍历（除基准数外），小于等于基数的放到一个临时数组 arr1，大于放到一个临时数组 arr2。
3. 若只有两个数则将小的放前面，大的放后面；若 arr1 或 arr2 只有 0~1 个则当前数组退出。
4. 将 arr1，arr2 执行步骤 1、2、3。（即递归实现）

图示

实现

function sort(arr) {
  // 设置递归出口
  if (arr.length <= 1) return arr
  // 设置基数，并将基数移出
  let base = Math.floor(arr.length / 2)
  let baseValue = arr.splice(base, 1)[0]
  // 临时数组。1）小于等于基数放入 arr1；2）大于放入基数放入 arr2
  let arr1 = []
  let arr2 = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] <= baseValue) {
      arr1.push(arr[i])
    } else {
      arr2.push(arr[i])
    }
  }
  // 递归
  return sort(arr1).concat([baseValue], sort(arr2))
}

let array = [4, 9, 3, 6, 21, 5, 0, 30, 2, 14]
console.log(sort(array)) // [0, 2, 3, 4, 5, 6, 9, 14, 21, 30]

时间复杂度

快速排序的平均时间复杂度为 O(nlogn)，快速排序的时间复杂度计算较为复杂。

有兴趣的同学可参考：如何证明快速排序法的平均复杂度为 O(nlogn)？

可以看到的是 快速排序 的时间复杂度是介于 桶排序 O(n) 和 冒泡排序 O(n^2) 之间的：O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)。