Java算法OJ（7）随机快速排序
目录
1.前言
2.正文
1. 快速排序的基本原理
2. 随机快速排序的改进
3. 随机快速排序的步骤
3.小结
1.前言
哈喽大家好吖，今儿给大家带来算法—随机快速排序相关知识点，废话不多说让我们开始。
2.正文
在了解随机快排之前，先了解一下原始的快速排序是什么：
1. 快速排序的基本原理
快速排序是一种基于分治法的排序算法，主要步骤包括：
- 选取基准：从数组中选取一个基准元素，通常选择第一个元素、最后一个元素或中间元素。
- 分区：将数组分为两个子数组，使得左子数组的元素都小于基准，右子数组的元素都大于基准。
- 递归排序：分别对左、右子数组递归进行快速排序，直到子数组的长度为1。
public static void quickSort1(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int x = arr[l + (int) (Math.random() * (r - l + 1))]; // 随机选择基准值
int mid = partition1(arr, l, r, x); // 分区操作
quickSort1(arr, l, mid - 1); // 递归排序左部分
quickSort1(arr, mid + 1, r); // 递归排序右部分
}
分区过程（
partition1）
- 遍历
arr[l...r]的所有元素，将小于等于x的元素放到左侧（<=x区域），大于x的元素放到右侧。- 使用一个变量
a来记录<=x区域的边界，并动态更新位置。- 遍历完成后，将等于
x的最后一个元素放在<=x区域的最后位置，以确保分区后的基准值处于正确位置。
public static int partition1(int[] arr, int l, int r, int x) {
int a = l, xi = 0; // a 记录 <=x 区域的边界，xi 用于记录 x 的位置
for (int i = l; i <= r; i++) {
if (arr[i] <= x) {
swap(arr, a, i);
if (arr[a] == x) {
xi = a;
}
a++;
}
}
swap(arr, xi, a - 1); // 将 x 放到 <=x 区域的末尾
return a - 1; // 返回 x 的最终位置
}
2. 随机快速排序的改进
在传统的快速排序中，选择固定的基准可能导致较差的时间复杂度。比如，如果数组已经有序或逆序，选择第一个或最后一个元素作为基准会导致算法的性能退化到 O(n2)O(n^2)O(n2)。
改进版使用了“荷兰国旗问题”的分区方式，将数组分为小于基准值、等于基准值、大于基准值三部分，分别放在左中右，即不再是使用俩块的分区方式，而是在一个分区中将所有都等于基准值的数字都放到中间。这样在处理大量重复元素时效率更高。
3. 随机快速排序的步骤
public static void quickSort2(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int x = arr[l + (int) (Math.random() * (r - l + 1))]; // 随机选择基准值
partition2(arr, l, r, x); // 分区操作
int left = first; // 左边界（小于 x 的部分的末尾）
int right = last; // 右边界（等于 x 的部分的末尾）
quickSort2(arr, l, left - 1); // 递归排序小于 x 的部分
quickSort2(arr, right + 1, r); // 递归排序大于 x 的部分
}
分区过程（
partition2）
partition2使用双指针方法实现了“荷兰国旗”分区。- 使用三个区域：
<x（小于x的区域）、==x（等于x的区域）和>x（大于x的区域）。- 通过遍历
arr[l...r]，将小于x的元素放在左边，大于x的元素放在右边，等于x的元素放在中间。- 更新全局变量
first和last，分别指向==x区域的左右边界
public static int first, last;
public static void partition2(int[] arr, int l, int r, int x) {
first = l;
last = r;
int i = l;
while (i <= last) {
if (arr[i] == x) {
i++;
} else if (arr[i] < x) {
swap(arr, first++, i++);
} else {
swap(arr, i, last--);
}
}
}
逻辑
- 初始时
first指向l，last指向r，i指针用于遍历数组。- 当
arr[i] == x时，i向右移动，继续检查下一个元素。- 当
arr[i] < x时，表示当前元素属于<x区域，将其交换到first所指位置，并同时增大first和i。- 当
arr[i] > x时，表示当前元素属于>x区域，将其交换到last所指位置，并减少last。- 这样在遍历完成后，
<x区域、==x区域和>x区域的边界已经划分完毕，first和last分别指向==x区域的左边界和右边界。
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}这里再对比一下改进前和改进后的不同：
| 比较项 | quickSort1 | quickSort2 |
|--------------|----------------------------------------------|-----------------------------------------------------------|
| **效率** | 适合普通数据集，但处理重复元素效率较低 | “荷兰国旗”分区方式更适合含有重复元素的数组，将等于基准值的部分集中在中间，减少重复元素的处理次数 |
| **递归调用** | 递归划分基于一个位置 | 递归划分基于两个位置（`first` 和 `last`），有效减少递归深度 |
| **使用场景** | 适合一般数据集，重复元素较多时效率较低 | 推荐用于重复元素较多的数组，一般情况下也更高效 |
下面这俩个是俩个排序的测试链接，一个是填函数风格，另一个是acm练习风格，本文仅将核心部分罗列出来，剩下的调试部分就交给大家了。
P1177 【模板】排序 - 洛谷 | 计算机科学教育新生态
https://www.luogu.com.cn/problem/P1177912. 排序数组 - 力扣（LeetCode）https://leetcode.cn/problems/sort-an-array/description/
3.小结
今天的分享到这里就结束了，喜欢的小伙伴点点赞点点关注，你的支持就是对我最大的鼓励，大家加油！