快速排序 (Quick Sort)
由 Tony Hoare 在 1960 年提出的高效排序算法，采用分治思想，平均时间复杂度 O(n log n)，是实践中最常用的排序算法之一。
定义
快速排序是一种分治算法：通过选择一个基准元素（pivot），将数组分为两部分（小于 pivot 和大于等于 pivot），然后递归地对两部分进行排序。
核心思想
快速排序的核心思路可以结合 二叉树的前序遍历 来理解：
在二叉树遍历的前序位置将一个元素排好位置，然后递归地将剩下的元素排好位置。
算法框架：
void quickSort(int[] nums, int lo, int hi) {
if (lo >= hi) return;
// 前序位置：通过 partition 将 nums[p] 放到正确位置
int p = partition(nums, lo, hi);
// 递归排序左右子数组
quickSort(nums, lo, p - 1);
quickSort(nums, p + 1, hi);
}
关键操作：partition
partition 函数是快速排序的核心，负责：
- 选择一个基准元素（pivot）
- 通过交换操作将数组分为两部分：
- 左部分：所有元素 ≤ pivot
- 右部分：所有元素 > pivot
- 返回 pivot 的最终位置
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 平均情况 | O(n log n) | 每次 partition 将数组分成两半，递归深度 log n |
| 最坏情况 | O(n²) | 数组已有序或逆序，每次 partition 只减少一个元素 |
| 最好情况 | O(n log n) | 每次 partition 都均匀分割数组 |
优化方法（避免最坏情况）：
- 三数取中法：从 lo、mid、hi 三个位置取中位数作为 pivot
- 随机选 pivot：随机选择 pivot，期望时间复杂度 O(n log n)
- 切换到插入排序：当子数组规模较小时（如 ≤ 10），切换到插入排序
空间复杂度
| 实现方式 | 空间复杂度 | 说明 |
|---|---|---|
| 递归实现 | O(log n) | 递归调用栈的深度（平均情况） |
| 最坏情况 | O(n) | 递归深度达到 n（数组有序时） |
| 迭代实现 | O(log n) | 使用显式栈，可视为原地排序 |
排序稳定性
快速排序是不稳定排序。
原因：partition 过程中的交换操作可能改变相同元素的相对位置。
示例：
原数组: [5a, 3, 5b, 2] (5a 和 5b 是值相同但原始位置不同的两个元素)
快速排序后: [2, 3, 5b, 5a] (5a 和 5b 的相对位置改变了)
算法特点
| 特点 | 说明 |
|---|---|
| 高效性 | 平均 O(n log n)，实践中非常快（常数因子小） |
| 原地排序 | 递归实现需要 O(log n) 栈空间，可视为原地；迭代实现真正原地 |
| 不稳定 | 交换操作导致相同元素相对位置改变 |
| 分治思想 | 将问题分解为子问题，分别解决（类似二叉树前序遍历） |
| 计算机思维 | 突破 O(n²) 的排序算法，离人类直觉较远，但效率高 |
与其他排序算法对比
| 维度 | 快速排序 | 归并排序 | 堆排序 | 插入排序 |
|---|---|---|---|---|
| 平均时间复杂度 | O(n log n) | O(n log n) | O(n log n) | O(n²) |
| 最坏时间复杂度 | O(n²) | O(n log n) | O(n log n) | O(n²) |
| 空间复杂度 | O(log n) | O(n) | O(1) | O(1) |
| 稳定性 | 不稳定 | 稳定 | 不稳定 | 稳定 |
| 是否原地 | 近似原地 | 否 | 是 | 是 |
| 实际性能 | 非常快 | 较快 | 较慢 | 慢（大规模） |
应用场景
- 通用排序：快速排序是许多编程语言标准库排序函数的基础（如 C 的
qsort、Python 的list.sort底层混合算法） - 大规模数据：平均 O(n log n) 适合大规模数据排序
- 内存受限：递归实现只需 O(log n) 额外空间
- 不是稳定排序的场景：如果需求稳定排序，应选择归并排序
变种算法
- 随机化快速排序：随机选择 pivot，避免最坏情况
- 三路快速排序：将数组分为 < pivot、= pivot、> pivot 三部分，适合有大量重复元素的数组
- 内省排序（IntroSort）：结合快速排序、堆排序、插入排序，C++ 的
std::sort使用此算法
相关概念
- 排序算法：快速排序是 O(n log n) 排序算法的代表
- 分治算法：快速排序的核心思想
- 二叉树：快速排序的思维模式来源（前序遍历）
- 前序遍历：二叉树前序遍历的应用
- DFS：深度优先搜索，与快排递归结构类似
- 递归：快速排序的实现方式
- partition：分区操作，快速排序的核心步骤
注意事项
- 内容不完整：当前概念页基于通用知识和部分摘要内容，完整内容待原始网页补充后更新
- 最坏情况优化：实际应用中应使用三数取中法或随机化避免 O(n²)
- 小数组优化：子数组规模小时切换到插入排序可提升性能
- 稳定性问题：如果需要稳定排序，应选择归并排序而非快速排序
总结
快速排序是计算机思维的典型代表：通过分治思想突破 O(n²) 的时间复杂度，虽然难以直观理解，但掌握其核心（partition + 递归）是理解高效算法的关键一步。实际应用中需注意最坏情况优化和稳定性问题。