Quick Sort
快速排序
排序核心时间 平均 O(n log n)空间 O(log n)
选一个基准，小的摆左边、大的摆右边，再递归两边。原地、缓存友好。
动画
7
2
9
4
1
8
5
3
快速排序：选基准，小的在左，大的在右。
1 / 38
- 默认
讲解
实践中最快的通用比较排序之一，标准库常以它为内核。
- 01选 a[hi] 为 pivot。
- 02扫描区间，小于 pivot 的与左侧指针交换。
- 03最后把 pivot 换到分界点，它已就位。
- 04对左右子区间递归。
易错点
- 已有序 + 固定取末端基准会退化成 O(n²)，应随机或三数取中。
- 等于 pivot 的元素处理不当会造成不平衡。
代码
function quickSort(a, lo = class="text-accent">0, hi = a.length - class="text-accent">1) {
if (lo >= hi) return a;
const p = partition(a, lo, hi);
quickSort(a, lo, p - class="text-accent">1);
quickSort(a, p + class="text-accent">1, hi);
return a;
}
function partition(a, lo, hi) {
const pivot = a[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
}
[a[i], a[hi]] = [a[hi], a[i]];
return i;
}