快速排序算法
⚠️ 内容不完整：原始网页为动态加载，仅成功提取开头部分，完整内容待补充
一句话总结
快速排序的核心思路需要结合 二叉树的前序遍历 来理解：在二叉树遍历的前序位置将一个元素排好位置，然后递归地将剩下的元素排好位置。
核心要点
1. 算法思路（基于二叉树遍历）
快速排序的思维模式与二叉树前序遍历类似：
- 前序位置：将一个元素排好位置（对应 partition 操作）
- 递归过程：然后递归地将剩下的元素排好位置
核心思想：把一个元素排好序，然后把剩下元素排好序，就能把整个数组排好序。
2. 关键函数：partition
快速排序的核心是 partition 函数：
let p = partition(nums, lo, hi)
这个函数负责：
- 选择一个基准元素（pivot）
- 将数组分为两部分：小于 pivot 的和大于等于 pivot 的
- 返回 pivot 的最终位置
3. 递归结构
快速排序是一个典型的分治算法：
- 调用 partition 确定 pivot 位置
- 递归排序 pivot 左边的子数组
- 递归排序 pivot 右边的子数组
4. 算法可视化
文章提供了交互式可视化面板，可直观观察快排的递归过程和排序效果。
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 平均情况 | O(N log N) | 每次 partition 将数组分成两半，递归深度 log N |
| 最坏情况 | O(N²) | 数组已有序或逆序，每次 partition 只减少一个元素 |
| 空间复杂度 | O(log N) | 递归调用栈的深度（平均情况） |
注意：由于内容不完整，以上时间复杂度分析基于快速排序的通用知识，待完整内容获取后补充验证。
代码实现
算法框架（待补充完整代码）
// 快速排序主函数
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 函数（待补充完整实现）
int partition(int[] nums, int lo, int hi) {
// 选择基准元素并进行分区
// 返回基准元素的最终位置
}
⚠️ 完整代码实现待原始内容补充后更新
对比分析
| 维度 | 快速排序 | 选择排序 | 插入排序 | 希尔排序 |
|---|---|---|---|---|
| 时间复杂度（平均） | O(N log N) | O(N²) | O(N²) | O(N^1.3) |
| 时间复杂度（最坏） | O(N²) | O(N²) | O(N²) | O(N²) |
| 空间复杂度 | O(log N) | O(1) | O(1) | O(1) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 | 不稳定 |
| 排序方式 | 原地排序 | 原地排序 | 原地排序 | 原地排序 |
| 算法思想 | 分治 | 选择极值 | 插入构建有序 | 分组插入 |
算法特点
高效算法的特点：
- 越是效率高的算法，离计算机思维越近，未经训练的人就越难理解
- 快速排序突破 O(N²) 的排序算法，属于"不是人类能想出来的"算法
- 容易理解和推导的排序算法复杂度全都是 O(N²)，而突破 O(N²) 的排序算法都需要特殊的思维方式
相关概念
- 排序算法：排序算法评估指标与分类
- 二叉树：快速排序思维模式的来源
- DFS：深度优先搜索，与快排递归结构类似
- 分治算法：将问题分解为子问题，分别解决后合并
- 递归：函数调用自身的编程技巧
- partition：分区操作，快速排序的核心
相关实体
- labuladong：算法学习平台 labuladong.online 作者
总结
快速排序展示了计算机思维与人类思维的差异：通过结合二叉树前序遍历的思维模式，实现了突破 O(N²) 的高效排序。虽然难以直观理解，但掌握其核心思想（partition + 递归）是理解分治算法的重要一步。
待补充内容
由于原始网页动态加载，以下内容待完整获取后补充：
- 完整的 partition 函数实现
- 快速排序的完整代码
- 详细的递归过程分析
- 最坏情况优化（如三数取中法）
- 快速排序的稳定性分析
- LeetCode 相关题目