一、快速排序基本思想
想象你有一堆杂乱的书需要按编号排列。快速排序的做法是：
1️⃣ 随便选一本书作为"基准书"
2️⃣ 把比它小的放左边，比它大的放右边
3️⃣ 对左右两堆书重复这个过程
二、代码逐行解析
1. 随机数生成
int getRand(int min, int max) {return (rand() % (max - min + 1)) + min;
}
作用：生成[min,max]范围内的随机数
类比：闭着眼睛从书堆里随机摸一本书
2. 核心排序逻辑
void quick_sort(int arr[], int low, int high) {if(low >= high) return; // 终止条件：只剩一本书时不需要整理// 🎯 随机选基准书int t_id = getRand(low, high);int tmp = arr[t_id];// 📌 初始化两个"整理员"int i = low-1; // 左整理员（从最左边开始往右走）int j = high+1; // 右整理员（从最右边开始往左走）while(i < j) {// 👉 右整理员找小书while(arr[--j] > tmp); // 一直往左走，直到找到比基准小的书// 👈 左整理员找大书while(arr[++i] < tmp); // 一直往右走，直到找到比基准大的书if(i < j) swap(arr[i], arr[j]); // 交换两本放错位置的书}// ✂️ 分割成左右两堆继续整理quick_sort(arr, low, j); // 整理左边小书堆quick_sort(arr, j+1, high); // 整理右边大书堆
}
三、动态演示
假设要排序数组 [3,1,4,2,5]，随机选中3作为基准：
步骤1️⃣：整理员开始工作
初始状态：i=-1, j=5
[3,1,4,2,5]↑ ↑右整理员j找到2（比3小） → j=3
左整理员i找到4（比3大） → i=2
交换后：[3,1,2,4,5]继续循环：
右整理员j移动到1 → j=1
左整理员i移动到4 → i=3
此时i>j，循环结束
步骤2️⃣：分割区间
分割点j=1 → 左区间[0,1]，右区间[2,4]
继续递归处理左右区间
四、关键点解释
为什么要随机选基准？
如果总是选第一个元素，遇到已排序数组时效率会退化成O(n²)。随机选择能避免最坏情况。
i和j的移动顺序
--j先移动再判断：避免死循环++i先移动再判断：保证每次循环都有进展
循环终止条件
当i和j相遇或交叉时（i >= j），说明分区完成
五、存在的问题
当所有元素相同时（如全2），每次只能确定一个元素的位置，时间复杂度退化为O(n²)。解决方法：
+ 使用三路快排，将数组分为 <、=、> 三部分
+ 遇到重复元素时直接跳过中间区域
六、性能对比
| 情况 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 普通快排 | O(nlogn) | O(n²) |
| 三路快排 | O(nlogn) | O(nlogn) |
逐步解释：
普通的快速排序在最坏情况下（例如所有元素完全相同）仍然会出现 O(n²) 的时间复杂度。以下是详细分析：
一、问题根源
当数组中所有元素相同时，代码的分区逻辑会失效：
-
每次分区只能确定一个元素的位置
假设数组为[2,2,2,2,2]：- 随机选择基准后，
i和j会在首尾相遇 - 分区后左区间为整个数组，右区间为空
- 每次递归只能排除一个元素（基准本身）
- 随机选择基准后，
-
递归深度变为 O(n)
导致总操作次数为：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 → O(n²)
二、代码验证
以全为 2 的数组 [2,2,2,2,2] 为例：
-
第一次分区
i从low-1=-1开始右移，直到i=4（越界）j从high+1=5开始左移，直到j=0- 分区后：左区间
[0,0]，右区间[1,4]
-
递归右区间
[1,4]
重复上述过程，每次只能排除一个元素。
三、解决方法
使用 三路快速排序 优化重复元素处理：
- 将数组分为三部分
< pivot、= pivot、> pivot
- 跳过重复元素区域
递归时只需处理<和>的部分。
四、三路快排核心代码
void quick_sort(int arr[], int low, int high) {if (low >= high) return;// 随机选择基准并交换到low位置int t_id = getRand(low, high);swap(arr[low], arr[t_id]);int pivot = arr[low];// 三路分割初始化int lt = low; // 最后一个小于pivot的位置 (less than)int gt = high; // 第一个大于pivot的位置 (greater than)int i = low + 1; // 当前遍历指针while (i <= gt) {if (arr[i] < pivot) {swap(arr[i], arr[lt]);lt++;i++;} else if (arr[i] > pivot) {swap(arr[i], arr[gt]);gt--;} else {i++;}}// 递归处理左右区域quick_sort(arr, low, lt - 1); // 处理 < 部分quick_sort(arr, gt + 1, high); // 处理 > 部分
}
五、复杂度对比
| 情况 | 原代码（双路快排） | 三路快排 |
|---|---|---|
| 普通数组 | O(n log n) | O(n log n) |
| 全相同元素 | O(n²) | O(n) |
六、总结
- 原代码问题：随机化基准无法解决全相同元素的极端情况，时间复杂度仍可能为 O(n²)。
- 终极解决方案：通过三路快排跳过重复元素区域，将最坏情况复杂度优化至 O(n)。