随机快速排序
算法原理
随机快速排序（Randomized Quicksort）是一种基于快速排序的排序算法，它在快速排序的基础上，通过引入随机化来减少最坏情况的发生。
随机快速排序的基本思想是：在快速排序的过程中，随机选取一个元素作为枢轴（pivot），然后将数组分成两个子数组，左边的子数组中的元素都小于等于枢轴，右边的子数组中的元素都大于等于枢轴。然后对两个子数组分别递归地进行快速排序。
核心思想
- 随机选择pivot并进行分区
- 将数组分为三部分：< pivot | = pivot | > pivot
- 递归处理左右两部分
完整实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void quickSort(vector<int>& nums, int l, int r){
if(l >= r){
return;
}
// 随机选择pivot
int x = l + rand() % (r - l + 1);
int pivot = nums[x];
// 三路分区: < pivot | = pivot | > pivot
// [l, a-1] : 小于pivot的元素
// [a, b] : 等于pivot的元素
// [b+1, r] : 大于pivot的元素
int i = l; // 当前位置检查
int a = l; // 指向第一个不小于pivot的元素
int b = r; // 指向第一个不大于pivot的元素
while(i <= b){ // 荷兰国旗法优化
if(nums[i] < pivot){
swap(nums[i++], nums[a++]);
}else if(nums[i] > pivot){
swap(nums[i], nums[b--]);
}else{
i++;
}
}
// 递归排序左右两部分
quickSort(nums, l, a - 1);
quickSort(nums, b + 1, r);
}
算法特点
时间复杂度
- 期望：$O(n log n)$
- 最坏：$O(n²)$（但概率极低）
- 最好：$O(n log n)$
空间复杂度
- $O(log n)$（递归栈空间）
优势
- 平均性能优秀：期望时间复杂度$O(n log n)$
- 原地排序：只需要$O(log n)$额外空间
- 随机化保证：避免最坏情况，性能稳定
- 实际应用快：常数因子小，缓存友好
应用场景
- 大规模数据排序
- 内存受限环境
- 对平均性能要求高的应用
执行示例
1
2
3
4
5
6
7
8
9
10
11
数组: [4, 3, 2, 1, 5]
第1次排序: 随机选pivot=2
分区后: [1, 2, 4, 3, 5]
↑ ↑
a-1 b+1
递归排序[1]和[4, 3, 5]
第2次排序: 对[4, 3, 5]随机选pivot=3
分区后: [1, 2, 3, 4, 5]
最终结果: [1, 2, 3, 4, 5]
随机选择算法
求得一个数组中第k小的元素，可以使用随机选择算法(QuickSelect)来解决，它基于快速排序的分区思想。
算法原理
结合随机快速排序的三路分区（荷兰国旗法）来解决第k小元素问题：
- 利用三路分区将数组分为：< pivot | = pivot | > pivot
- 根据k与各区域边界的比较关系决定搜索方向
- 避免了重复元素的多次处理，提高效率
核心思想
- 随机选择pivot并进行三路分区
- 确定k所在的区域：
- 如果k在小于pivot的区域，在左半部分查找
- 如果k在等于pivot的区域，直接返回pivot
- 如果k在大于pivot的区域，在右半部分查找
完整实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int quickSelect(vector<int>& nums, int l, int r, int k) {
if (l >= r) return nums[l];
// 随机选择pivot
int x = l + rand() % (r - l + 1);
int pivot = nums[x];
// 三路分区: < pivot | = pivot | > pivot
int a = l;
int b = r;
int i = l;
while (i <= b) {
if (nums[i] < pivot) {
swap(nums[a++], nums[i++]);
} else if (nums[i] > pivot) {
swap(nums[i], nums[b--]);
} else {
i++;
}
}
// 现在：
// [l, a-1] : 小于pivot的元素
// [a, b] : 等于pivot的元素
// [b+1, r] : 大于pivot的元素
if (k < a) { // 确定k所在的区域
// 第k小元素在小于pivot的区域
return quickSelect(nums, l, a - 1, k);
} else if (k > b) {
// 第k小元素在大于pivot的区域
return quickSelect(nums, b + 1, r, k);
} else {
// 第k小元素在等于pivot的区域
return pivot;
}
}
算法特点
时间复杂度
- 期望：O(n)
- 最坏：O(n²)（概率极低）
- 最好：O(n)
空间复杂度
- O(log n)（递归栈空间）
优势
- 处理重复元素高效：三路分区避免了重复元素的多次处理
- 随机化保证：期望性能稳定
- 原地操作：只需要O(1)额外空间（不考虑递归栈）
- 适应性强：对于各种数据分布都有良好表现
执行示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入: n=5, k=1
数组: [4, 3, 2, 1, 5]
查找第1小的元素：
第1次分区: 随机选pivot=2
三路分区后: [1, 2, 4, 3, 5]
↑ ↑
a b
区域: [0,0] < 2, [1,1] = 2, [2,4] > 2
k=1, a=1, b=1
k <= b (1 <= 1) 且 k >= a (1 >= 1)
返回pivot = 2
输出: 2
