随机快速排序算法
一、随机化原理
-
经典快速排序 选取固定的“枢轴”（通常取第一个或最后一个元素），在最坏情况下（如已经有序）会退化为
。
-
随机快速排序 在每次分区前随机地从当前区间 [p..r] 中等概率选取一个枢轴，将它与末尾元素交换，再做标准分区。
-
随机化保证任意输入上每个元素都有同样概率被选为枢轴，从而平均下能避免极端不平衡的划分，取得期望
。
二、算法步骤
-
入口调用
调用RQS(A, 1, n)对长度为 n 的数组 A 进行排序。 -
递归基
若子区间长度小于等于 1（即 p≥r ），直接返回。 -
随机选枢轴
在 [p,r] 上用RANDOM(p,r)等概率选出下标 i ，交换A[i]与A[r]，这样A[r]就是随机枢轴。 -
分区（Partition）
以A[r]为枢轴做一次线性扫描，将 ≤ 枢轴的都移动到左边，返回枢轴最终位置 q 。 -
递归排序
分别对左右两段A[p..q-1]和A[q+1..r]递归调用RQS。
三、伪代码
RQS(A, p, r)
1 if p < r
2 // 随机化选枢轴
3 i ← RANDOM(p, r)
4 swap A[i] ↔ A[r]
5
6 // 标准 Partition
7 q ← PARTITION(A, p, r)
8
9 // 递归排序左右子区间
10 RQS(A, p, q-1)
11 RQS(A, q+1, r)// Partition: 以 A[r] 为枢轴，返回最终位置
PARTITION(A, p, r)
1 x ← A[r]
2 i ← p − 1
3 for j = p to r − 1
4 if A[j] ≤ x
5 i ← i + 1
6 swap A[i] ↔ A[j]
7 swap A[i+1] ↔ A[r]
8 return i + 1
四、时间复杂度推导
（一）最坏情况
-
若每次随机恰巧选到当前子数组最小或最大元素，分区极端不平衡：
（二）期望／平均情况
令 T(n) 为对长度为 n 的数组运行的期望时间。
-
随机选枢轴后，其秩 k 在 {1,2,…,n} 上均匀分布。
-
若枢轴落在第 k 小位置，则子问题规模为 k−1 和 n−k 。
这一递归可通过替换法或主定理分析得出：