随机快速排序的原理与优化实现
算法核心思想
随机快速排序是一种基于分治策略的高效排序算法，其核心在于每次从待排序区间中随机选取一个基准值（pivot），通过一次划分操作将数组分为三部分：小于基准值、等于基准值、大于基准值。该过程递归执行，直至整个数组有序。
基础实现逻辑
- 在区间
[l, r]内随机选择一个元素作为基准值x。 - 以
x为参照，将数组划分为两部分：所有 ≤x的元素置于左侧，所有 >x的元素置于右侧。 - 将基准值
x移动到左半部分的末尾位置，确保其已处于最终排序位置。 - 对左右两个子区间分别递归执行相同操作，直到区间长度 ≤ 1。
代码实现（基础版本）
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
// 随机选择基准值
int pivotIndex = left + (int)(Math.random() * (right - left + 1));
int pivot = arr[pivotIndex];
// 划分并返回基准值最终位置
int partitionIndex = partition(arr, left, right, pivot);
// 递归处理左右子数组
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
private static int partition(int[] arr, int l, int r, int x) {
int i = l; // 当前遍历指针
int boundary = l; // 小于等于x区域的右边界
for (; i <= r; i++) {
if (arr[i] <= x) {
swap(arr, i, boundary);
boundary++;
}
}
// 将基准值放入正确位置（位于≤x区域的末尾）
swap(arr, boundary - 1, l + (int)(Math.random() * (r - l + 1)));
return boundary - 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
优化策略：三路划分（荷兰国旗问题）
当数组中存在大量重复元素时，传统二路划分效率下降。为此引入三路划分：
- 左区：所有元素 <
x - 中区：所有元素 ==
x - 右区：所有元素 >
x
这样可一次性将多个相等元素归位，减少不必要的递归调用。
三路划分实现
private static int[] threeWayPartition(int[] arr, int l, int r, int x) {
int lt = l; // 左边界：小于x的区域右端
int gt = r; // 右边界：大于x的区域左端
int i = l; // 当前扫描指针
while (i <= gt) {
if (arr[i] < x) {
swap(arr, lt++, i++);
} else if (arr[i] > x) {
swap(arr, i, gt--);
} else {
i++; // 等于x，无需移动，仅前进
}
}
// 返回中区的左右边界
return new int[]{lt, gt};
}
// 使用示例
public static void quickSortThreeWay(int[] arr, int l, int r) {
if (l >= r) return;
int pivotIndex = l + (int)(Math.random() * (r - l + 1));
int pivot = arr[pivotIndex];
int[] bounds = threeWayPartition(arr, l, r, pivot);
int leftBound = bounds[0];
int rightBound = bounds[1];
quickSortThreeWay(arr, l, leftBound - 1);
quickSortThreeWay(arr, rightBound + 1, r);
}
时间复杂度分析
- 最坏情况：O(n²)，当每次选中的基准值都是最大或最小元素（如已排序数组），但因随机化机制，此情况概率极低。
- 最好情况：O(n log n)，每次基准值都接近中位数，递归树深度为 log n。
- 平均情况：期望时间复杂度为 O(n log n)，得益于随机化策略，使分割趋于平衡。
空间复杂度
- 递归栈空间：最坏情况下为 O(n)，平均情况下为 O(log n)。
- 无额外辅助数组，原地排序，空间效率高。
通过随机化选择基准和三路划分优化，随机快速排序在实际应用中表现出卓越的性能，尤其适合处理含有重复元素的数据集。
