大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》785 题——快速排序。这篇文章介绍了使用快速排序算法对整数数列进行排序的方法，包括选择基准元素、分区操作和递归排序子数组。通过详细的步骤和示例，解释了快速排序的过程及其非稳定性特征，并提供了相应的 Java 代码实现。
文章目录
❓题目描述
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
💡算法思路
- 选择基准元素：从数组中选择一个元素作为基准。这里我们选择的是中间位置的元素。
- 分区操作：重新排列数组，将所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作。
- 递归排序子数组：递归地将小于基准值元素的子数列和大于基准值元素的子数列排序。
具体实现步骤如下：
- 首先检查数组的起始索引
l是否大于或等于结束索引r，如果是，则直接返回，因为这意味着数组已经是有序的或者是空数组。 - 初始化两个指针
i和j，分别指向数组的起始位置的前一个位置和结束位置的后一个位置。选择数组的中间元素作为基准元素x。 - 使用两个指针
i和j从数组的两端向中间移动，直到i找到一个大于或等于基准的元素，j找到一个小于或等于基准的元素。如果i仍然小于j，则交换这两个元素。 - 重复上述过程，直到
i不再小于j。 - 递归地对基准元素左侧和右侧的子数组进行快速排序。
时间复杂度：O(n log n)
空间复杂度：O(n)
快速排序是非稳定排序：快速排序的分区过程中，当遇到与基准元素相等的元素时，通常会停止移动指针（在某些实现中，指针会继续移动），这可能导致相同元素的相对顺序被改变。例如，如果数组中有多个相同的元素，分区操作可能会将这些元素分散到基准的两侧，从而改变它们的相对顺序。
稳定排序的定义是：在排序过程中，具有相同键值的元素在排序前后的相对位置保持不变。然而，快速排序的分区操作可能会改变相同元素的相对顺序。
接下来，我给大家举个具体的例子来说明为什么快速排序是非稳定排序。
假设我们有一个包含学生信息的数组，每个学生由他们的姓名和成绩组成。我们希望按照成绩对学生进行排序。初始数组如下：
[ ("何未来", 85), ("乔布斯", 75), ("牛顿", 85), ("图灵", 75) ]
选择基准元素 ("牛顿", 85)，进行第一次分区操作：
初始指针位置：
i = -1，j = 4移动
i直到找到大于或等于基准的元素：i停在("何未来", 85)移动
j直到找到小于或等于基准的元素：j停在("图灵", 75)交换
i和j指向的元素：[ (“图灵”, 75), (“乔布斯”, 75), (“牛顿”, 85), (“何未来”, 85) ]
第一次分区结束，基准元素 ("牛顿", 85) 的位置已经确定。现在我们有两个子数组：
- 左子数组：
[ ("图灵", 75), ("乔布斯", 75) ] - 右子数组：
[ ("何未来", 85) ]
我们先对左子数组进行递归排序：
选择基准元素 ("乔布斯", 75)，进行第二次分区操作：
初始指针位置：
i = -1，j = 2移动
i直到找到大于或等于基准的元素：i停在("图灵", 75)移动
j直到找到小于或等于基准的元素：j停在("乔布斯", 75)交换
i和j指向的元素：[ (“乔布斯”, 75), (“图灵”, 75) ]
第二次分区结束，基准元素 ("乔布斯", 75) 的位置已经确定。现在我们有两个子数组：
- 左子数组：
[ ]（空数组） - 右子数组：
[ ("图灵", 75) ]
由于左子数组为空，右子数组只有一个元素，这两个子数组都已经是有序的。
接下来对右子数组进行递归排序：
右子数组 [ ("何未来", 85) ] 只有一个元素，已经是有序的。
最终排序结果：
[ ("乔布斯", 75), ("图灵", 75), ("牛顿", 85), ("何未来", 85) ]
通过这个过程，我们可以看到，初始数组中相同成绩的学生 ("何未来", 85) 和 ("牛顿", 85) 的相对顺序在排序后发生了变化，从 ("何未来", 85) 在前变成了 ("牛顿", 85) 在前。这就是快速排序不稳定性的体现。
✅Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Aw785 {
// 创建一个StreamTokenizer用于读取输入
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
// 读取下一个整数的方法
static int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
static int n; // 存储数组的大小
static int[] nums = new int[100000 + 10]; // 存储输入的数组，预留一些额外的空间
public static void main(String[] args) throws IOException {
n = nextInt(); // 读取数组的大小
for (int i = 0; i < n; i++) {
nums[i] = nextInt(); // 读取数组的每个元素
}
quickSort(0, n - 1, nums); // 调用快速排序方法对数组进行排序
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + " "); // 输出排序后的数组
}
}
// 快速排序方法，参数为数组的起始和结束索引，以及数组本身
static void quickSort(int l, int r, int[] a) {
if (l >= r) {
// 如果起始索引大于或等于结束索引，则直接返回
return;
}
int i = l - 1, j = r + 1, x = a[l + r >> 1]; // 初始化指针i, j和基准元素x，以中间元素作为基准元素
while (i < j) {
// 当i小于j时，执行循环
do {
i++; // i指针向右移动，直到找到一个大于或等于x的元素
} while (a[i] < x);
do {
j--; // j指针向左移动，直到找到一个小于或等于x的元素
} while (a[j] > x);
if (i < j) {
// 如果i仍然小于j，交换这两个元素
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
quickSort(l, j, a); // 递归排序左半部分
quickSort(j + 1, r, a); // 递归排序右半部分
}
}
🔗参考
🔍推荐阅读
欢迎
关注我的博客：@程序员何未来，持续为你输出有价值 的技术文章\~
你们的点赞👍 收藏⭐ 留言🗨️ 关注✅
是我持续创作，输出优质内容的最大动力！谢谢！
文章关键词：算法，计算机算法，算法题解，算法竞赛，Java，数据结构，AcWing算法基础课
原文链接: https://blog.csdn.net/coder_heweilai/article/details/141720984