前言
快速排序，简称 快排，是最常见的算法之一。桶排序 虽然快，但是空间消耗大，冒泡排序 利用的空间较为合理但是 O(n²)，显然在数据量较大时不够快。快速排序 算是从两者取长补短的算法。
正文
原理
以升序为例：
- 在数据中选一个作为
基准数。（一般习惯选择中间的数，但选择其他数也可以） - 将所有的数据进行遍历（除基准数外），小于等于基数的放到一个临时数组
arr1，大于放到一个临时数组arr2。 - 若只有两个数则将小的放前面，大的放后面；若
arr1或arr2只有0~1个则当前数组退出。 - 将
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)。
