一、快速排序的核心思想（分治法）
一句话总结：
“挖坑填数 + 分而治之” —— 选择一个基准值（pivot），将数组分成两部分，左边都比基准小，右边都比基准大，然后递归处理左右两部分。
二、快速排序的步骤拆解（配图示）
1. 原始数组示例：
数组: [10, 80, 30, 90, 40, 50, 70]
↑i ↑j
pivot = 10（选第一个元素）
2. 步骤详解（以第一个元素为基准）：
步骤1：选择基准（pivot）
通常选第一个元素（
10）作为基准。目标：把比
10小的数移到左边，比10大的数移到右边。
步骤2：分区（Partition）
初始化指针：
i = left（起点），j = right（终点）。操作流程：
从右向左找第一个 小于 pivot 的数（
j向左移动）：j初始指向70：70 > 10→j--（j移动到50）j指向50：50 > 10→j--（j移动到40）j指向40：40 > 10→j--（j移动到90）j指向90：90 > 10→j--（j移动到30）j指向30：30 > 10→j--（j移动到80）j指向80：80 > 10→j--（j移动到10，即i的位置）此时
i == j，循环终止，没有找到任何小于10的元素。这意味着10已经是当前子数组的最小值，无需移动。
放置基准值
将
pivot（10）和arr[i]（也是10）交换，数组保持不变：数组: [10, 80, 30, 90, 40, 50, 70]
- 分区后的子数组
左子数组：
[10]右子数组：
[80, 30, 90, 40, 50, 70]
递归右子数组
[80, 30, 90, 40, 50, 70]，选80为基准：数组: [80, 30, 90, 40, 50, 70] ↑i ↑j pivot = 80（选第一个元素）j从右向左找<80的数：70 < 80→ 停止，j指向70（索引5）。
i从左向右找>80的数：80 == 80→i++指向30（30 < 80，继续）（索引1）。i指向90（90 > 80）→ 停止（索引2）。
交换
90和70→[80, 30, 70, 40, 50, 90]。此时指针位置：
i仍在2（现在指向70）。j仍在5（现在指向90）。
继续移动
j和i：j从 90左移，指向50（50 < 80）→ 停止。i从 70右移，指向 40（40 < 80）→ 继续移动。i从 40右移，指向 50（50 < 80）→ 继续移动。i从 50右移，指向 90（90 > 80）→ 停止。此时
i和j的所在索引关系：i = 5，j = 4→i > j，循环终止。
放置基准值，将
pivot（80）与arr[j]（50，索引4）交换：交换前: [80, 30, 70, 40, 50, 90] 交换后: [50, 30, 70, 40, 80, 90]
- 后续依次类推，最终排序结果：
[10, 30, 40, 50, 70, 80, 90]
三、快速排序的代码实现（Python/Java）
Python版本（递归）：
def quick_sort(arr, left, right):
if left >= right:
return
pivot = arr[left] # 选第一个元素为基准
i, j = left, right
while i < j:
while i < j and arr[j] >= pivot: # 从右找小的
j -= 1
while i < j and arr[i] <= pivot: # 从左找大的
i += 1
arr[i], arr[j] = arr[j], arr[i] # 交换
arr[left], arr[i] = arr[i], arr[left] # 基准归位
quick_sort(arr, left, i - 1) # 递归左子数组
quick_sort(arr, i + 1, right) # 递归右子数组
# 调用示例：
arr = [10, 80, 30, 90, 40, 50, 70]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # 输出 [10, 30, 40, 50, 70, 80, 90]Java版本（递归）：
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
arr[left] = arr[i]; arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}四、快速排序的特性
| 特性 | 说明 |
|---|---|
| 时间复杂度 | - 平均：O(n log n) （每次分区接近均分） - 最坏：O(n²) （数组已有序或逆序） |
| 空间复杂度 | - 平均：O(log n) （递归栈深度） - 最坏：O(n) |
| 稳定性 | 不稳定（交换可能改变相同元素的顺序） |
| 适用场景 | 大规模无序数据（内排序） |
| 优化策略 | - 随机选择基准值 - 三数取中法选基准 - 小数组时切换为插入排序 |
五、快速排序的“生活类比”
想象你在整理书架：
选基准：随便挑一本书（比如《算法导论》）作为基准。
分区：
左边放比它薄的书，右边放比它厚的书。
你让两个助手分别从书架两端开始找书交换位置。
递归：对左右两堆书重复这个过程，直到每堆只剩一本书。
六、与其他排序算法的对比
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用，大规模无序数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 外部排序、链表排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 实时系统（空间受限） |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学或小规模数据 |
七、考试常见问题
1. 快速排序的最坏情况是什么？如何避免？
最坏情况：数组已有序或逆序，每次分区只能减少一个元素（退化成冒泡排序）。
避免方法：随机选基准 或 使用“三数取中法”（选头、中、尾的中位数）。
2. 快速排序为什么不稳定？
例子：
[3a, 2, 3b, 1]（3a和3b是相同值）。
选3a为基准，分区后可能变为[1, 2, 3b, 3a]，3a和3b顺序颠倒。
3. 快速排序和归并排序的区别？
分治策略：
快排：先分区后递归（分区复杂，合并简单）。
归并：先递归后合并（分区简单，合并复杂）。
空间：快排是原地排序（空间更优），归并需要额外空间。
掌握快速排序的关键是理解分区过程和递归思想。试着在白纸上画几次分区步骤，你会豁然开朗！ 🚀