排序算法系列 07：快速排序——面试必问，工程必用
快速排序大概是排序算法里"地位最高"的一个。面试高频考、工程广泛用、各种语言标准库里都能看到它的影子。
为什么？因为它平均性能极好，空间开销又小。虽然最坏情况可能退化到 O(n²)，但经过简单优化后，实际场景中这种情况几乎不会发生。
核心思想
选一个元素当"基准"，把比它小的扔左边，比它大的扔右边。这样基准就到了最终正确的位置。然后递归处理左右两部分。
原始：5, 2, 9, 1, 7
选 5 做基准：
左边（比 5 小）：2, 1
基准：5
右边（比 5 大）：9, 7
递归处理左边 → 1, 2
递归处理右边 → 7, 9
最终：1, 2, 5, 7, 9
每次分区（partition）都让一个元素归位。递归下去，所有元素都归位了。
和归并排序的区别
两个都是分治，但顺序相反：
- 归并排序：先拆后治——拆的时候不做任何比较，排序工作在合并时完成
- 快速排序：先治后拆——分区的时候就在排序，分完之后不需要合并
所以快排不需要额外的合并数组，空间开销更小。
简单版本（好理解）
这个版本会创建额外数组，不是原地排序，但最容易看懂：
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
console.log(quickSort([5, 2, 9, 1, 7]));
// [1, 2, 5, 7, 9]
逻辑一目了然：选基准、分两堆、递归、拼起来。
原地分区版本（实际常用）
真正工程里用的是原地版本——不创建新数组，直接在原数组上操作：
function quickSortInPlace(arr) {
const result = [...arr];
function sort(left, right) {
if (left >= right) return;
const pivotIndex = partition(result, left, right);
sort(left, pivotIndex - 1);
sort(pivotIndex + 1, right);
}
sort(0, result.length - 1);
return result;
}
function partition(arr, left, right) {
const pivot = arr[right]; // 取最后一个元素做基准
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
console.log(quickSortInPlace([5, 2, 9, 1, 7]));
// [1, 2, 5, 7, 9]
partition 做的事情：遍历一遍，把比基准小的都换到左边，最后把基准放到中间。返回基准的最终位置。
变量 i 可以理解为"小于基准的区域的右边界"。每发现一个比基准小的元素，就把它换到这个边界处，然后边界右移一位。
复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好 | O(n log n) |
| 平均 | O(n log n) |
| 最坏 | O(n²) |
最坏情况发生在每次选的基准都是当前区间的最大或最小值——这样每次分区只能排除一个元素，退化成 O(n²)。比如对已排序数组用第一个元素做基准，就会中招。
空间复杂度：主要是递归调用栈，平均 O(log n)，最坏 O(n)。
稳定性：不稳定。分区时元素会跨距离交换。
怎么避免最坏情况？
实际工程中都会做优化：
- 随机选基准：不固定取第一个或最后一个，而是随机选一个。这样极端退化的概率趋近于零
- 三数取中：取头、尾、中间三个数的中位数做基准，效果很好
- 小数组切插入排序：递归到一定深度，子数组很小时切到插入排序
- Introsort 策略：递归深度超过阈值时切到堆排序，彻底避免
O(n²)
C++ STL 的 std::sort 用的就是 Introsort（快排 + 堆排 + 插入排序的混合体）。
快排为什么实际跑得快？
从复杂度看，快排和归并都是 O(n log n)。但快排通常更快，原因是：
- 原地操作：不需要额外数组，缓存友好性好
- 分区操作顺序访问内存：CPU 缓存命中率高
- 常数因子小：相比归并少了大量的数组创建和复制
这也是为什么大多数语言标准库的默认排序底层都以快排为骨架。
总结一下
快排的精髓：选基准、做分区、递归处理。三步走，简单粗暴但有效。
它最大的弱点是最坏情况，但加上随机化或三数取中后，实际场景中几乎不可能触发。
下一篇来看堆排序——另一个 O(n log n) 的选手，它的特点是时间复杂度永远稳定，不会退化。
系列导航