快速排序（Quick Sort）是计算机科学中最著名、应用最广泛的排序算法之一。它的核心思想是分治（Divide and Conquer），这个策略可以分为三个步骤：
简单来说，快速排序就是通过不断地选择基准、进行分区，将一个大问题递归地分解成越来越小的子问题，直到子问题小到可以直接解决（数组只有一个或零个元素），最终完成排序。
Lumuto 分区方案
“分区”是快速排序算法的核心步骤，而 Lomuto 分区方案（Lomuto Partition Scheme）是实现分区的一种非常直观和流行的方法。
Lomuto 分区的思想
可以把它想象成整理书架的过程：
i 来表示这个区域的右边界。初始时，这个区域是空的，所以 i 在书架的最左端之前（i = left - 1）。j）检查每一本书（除了最右边的基准书）。arr[j] < pivot），需要把它放到“已整理区域”中。i 向右移动一格（i++），然后把这本新发现的薄书 arr[j] 和边界 i 所在位置的书进行交换。这样，“已整理区域”就扩大了，并且包含了这本新发现的薄书。[left, i] 这个区间就全都是比基准书薄的书了。i+1 这个位置，理所当然就是“基准书”应该在的最终位置。arr[right]）和 arr[i+1] 进行交换。i+1。#include <cstdio>
#include <vector>
#include <algorithm>
using std::vector;
using std::swap;
/**
* @brief Lumuto 分区函数
* @param arr 要分区的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
* @return 基准元素在分区后的最终索引
*/
int lomutoPartition(vector<int> &arr, int left, int right) {
// 1. 选择区间的最后一个元素作为基准
int pivot_value = arr[right];
// i 是“小于基准”这个区域的右边界
// 初始时，这个区域为空，i 指向 left 的前一个位置
int i = left - 1;
// 2. 遍历数组从 left 到 right-1
for (int j = left; j < right; j++) {
// 如果当前元素 arr[j] 小于基准值
if (arr[j] < pivot_value) {
// 扩大“小于基准”的区域
i++;
// 将 arr[j] 交换到这个区域的末尾
swap(arr[i], arr[j]);
}
}
// 3. 遍历结束后，i+1 的位置就是基准应该在的地方
// 将基准（arr[right]）与 arr[i+1] 交换
swap(arr[i + 1], arr[right]);
// 4. 返回基准的最终位置
return i + 1;
}
/**
* @brief 快速排序的递归实现
* @param arr 要排序的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
*/
void quickSort(vector<int> &arr, int left, int right) {
// 递归的终止条件：当区间只有一个或零个元素时
if (left < right) {
// 调用 Lomuto 分区，获取基准的最终位置
int pivot_index = lomutoPartition(arr, left, right);
// 递归地对基准左边的子数组进行排序
quickSort(arr, left, pivot_index - 1);
// 递归地对基准右边的子数组进行排序
quickSort(arr, pivot_index + 1, right);
}
}
int main()
{
int n; scanf("%d", &n);
vector<int> arr(n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
// 调用快速排序
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d%c", arr[i], i == n - 1 ? '\n' : ' ');
}
return 0;
}
上面这个程序并不能通过模板题的全部测试数据，这是因为标准快速排序存在弱点。
Lomuto 分区方案通常选择区间的最后一个元素作为基准（Pivot），问题就出在这个“固定”的选择上。
[1, 2, 3, 4, 5]，每次都选最后一个元素做基准。5。分区后，左边子数组是 [1, 2, 3, 4]（\(n-1\) 个元素），右边子数组是空的。4。分区后，左边是 [1, 2, 3]（\(n-2\) 个元素），右边是空的。随机化思想
随机快速排序（Randomized Quick Sort） 的思想非常简单，却很有效。
在选择基准时，不再固定地选择最后一个元素，而是在当前待排序的 [left, right] 区间内，随机挑选一个元素作为基准。
这样做的好处是什么？简单来说，随机化用一个可以忽略不计的“坏运气”风险，换来了在任何输入下都极其稳定的高性能。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <random>
using std::vector;
using std::swap;
using std::random_device;
using std::mt19937;
using std::uniform_int_distribution;
/**
* @brief Lumuto 分区函数
* @param arr 要分区的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
* @return 基准元素在分区后的最终索引
*/
int lomutoPartition(vector<int> &arr, int left, int right) {
int pivot_value = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot_value) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[right]);
return i + 1;
}
/**
* @brief 快速排序的递归实现
* @param arr 要排序的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
*/
void randomizedQuickSort(vector<int> &arr, int left, int right) {
if (left < right) {
// 使用 <random> 库生成随机数
// 1. 创建一个随机数生成引擎
static mt19937 generator(random_device{}());
// 2. 创建一个均匀分布，范围是 [left, right]
uniform_int_distribution<int> distribution(left, right);
// 3. 生成一个随机索引
int pivot_idx = distribution(generator);
// 将随机选择的基准与区间的最后一个元素交换
swap(arr[pivot_idx], arr[right]);
// 调用标准 Lomuto 分区
int partition_idx = lomutoPartition(arr, left, right);
// 4. 递归地对左右两个子数组进行排序
randomizedQuickSort(arr, left, partition_idx - 1);
randomizedQuickSort(arr, partition_idx + 1, right);
}
}
int main()
{
int n; scanf("%d", &n);
vector<int> arr(n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
randomizedQuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d%c", arr[i], i == n - 1 ? '\n' : ' ');
}
return 0;
}
上面的程序相比之前多通过了一个测试点，但依然不能通过全部测试数据。实际上，上面的算法在重复元素多时会遇到性能瓶颈。
回顾一下 Lomuto 分区方案：if (arr[j] < pivot_value) 这个条件将数组分成了两部分：
< pivot 的部分>= pivot 的部分问题就出在这里：所有与基准值相等的元素，都被划分到了“大于等于”这一侧。
[5, 5, 5, 5, 5, 5, 5]。5。< 5）：空的（\(0\) 个元素）。>=5）：[5, 5, 5, 5, 5, 5]（\(n-1\) 个元素）。5。荷兰国旗思想：三向切分（3-Way Partitioning）
荷兰国旗由红、白、蓝三色组成。荷兰国旗思想就是将一个数组一次性划分成三个部分，而不是两个。
应用到快速排序中，就是将数组根据基准 pivot 分成：
pivot 小。pivot。pivot 大。这个思想的巨大优势在于：分区结束后，中间的“等于区”的所有元素已经处于其最终的排序位置了，完全不需要 在后续的递归中处理它们。只需要递归地去排序“小于区”和“大于区”即可。
如果一个数组包含大量重复元素，那么这个“等于区”会非常大，一次性就排好了很多元素，极大地减少了递归的规模。
三向切分的实现步骤
使用三个指针来完成这个精巧的操作：
low：指向“小于区”的 下一个位置。[left...low-1] 是小于区。mid：当前正在遍历和检查的元素。[low...mid-1] 是等于区。high：指向“大于区”的 前一个位置。[high+1...right] 是大于区。遍历过程（while (mid <= high)）
arr[mid] < pivot：
arr[mid] 属于“小于区”。arr[low] 和 arr[mid] 交换。low 和 mid 都向右移动一位。arr[mid] == pivot：
arr[mid] 已经在正确的分区（等于区）了。mid 指针，扩大等于区即可。arr[mid] > pivot：
arr[mid] 属于“大于区”。arr[high] 和 arr[mid] 交换。high 向左移动一位。mid 不移动。因为从 high 换过来的那个新 arr[mid] 还没有被检查过，它需要留在原地，在下一轮循环中被判断。当 mid 指针与 high 指针相遇后，整个分区就完成了。
#include <cstdio>
#include <vector>
#include <utility>
#include <random>
using std::vector;
using std::pair;
using std::swap;
using std::mt19937;
using std::random_device;
using std::uniform_int_distribution;
/**
* @brief 荷兰国旗问题（三向切分）分区函数
* @param arr 要分区的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
* @return 一个 pair，包含“等于区”的左右边界索引 {low, high}
*/
pair<int, int> threeWayPartition(vector<int> &arr, int left, int right) {
int pivot_value = arr[right];
int low = left; // 小于区的右边界+1
int mid = left; // 当前检查的元素
int high = right; // 大于区的左边界-1
while (mid <= high) {
if (arr[mid] < pivot_value) {
swap(arr[low], arr[mid]);
low++; mid++;
} else if (arr[mid] > pivot_value) {
swap(arr[high], arr[mid]);
high--;
} else { // arr[mid] == pivot_value
mid++;
}
}
// 循环结束后，[left, low-1] < pivot, [low, high] == pivot, [high+1, right] > pivot
// 但由于基准在最右边，所以最后返回的等于区的边界是 [low, high]
// 实际上，等于区的边界是 [low, mid-1]，但 high 在循环结束时就是 mid-1
// 所以返回 {low, high} 是可以的，代表等于区的开始和结束
return {low, high};
}
/**
* @brief 随机快速排序函数（三向切分优化版）
* @param arr 要排序的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
*/
void randomizedQuickSort(vector<int> &arr, int left, int right) {
if (left >= right) return;
// 随机化：选择一个随机基准并与最后一个元素交换
static mt19937 generator(random_device{}());
uniform_int_distribution<int> distribution(left, right);
int pivot_idx = distribution(generator);
swap(arr[pivot_idx], arr[right]);
// 执行三向切分
pair<int, int> partition_indices = threeWayPartition(arr, left, right);
// 递归地对“小于区”和“大于区”进行排序
// “等于区” [partition_indices.first, partition_indices.second] 不再需要处理
randomizedQuickSort(arr, left, partition_indices.first - 1);
randomizedQuickSort(arr, partition_indices.second + 1, right);
}
int main()
{
int n; scanf("%d", &n);
vector<int> arr(n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
randomizedQuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d%c", arr[i], i == n - 1 ? '\n' : ' ');
}
return 0;
}
Hoare 分区方案
Hoare 分区方案由快速排序算法的发明者 C. A. R. Hoare 本人提出，是最初的分区方法。它的思想与 Lomuto 方案有所不同，更为精巧。
核心思想：使用两个指针，一个从 左端开始向右 扫描，另一个从 右端开始向左 扫描，它们相向而行，寻找并交换那些“站错队”的元素。
arr[left] 作为基准。i 初始化为 left - 1。j 初始化为 right + 1。do-while 循环中先移动再访问。while (true)。i 的移动：i 不断向右移动（i++），直到找到一个 大于或等于 基准 pivot 的元素 arr[i] 才停下。j 的移动：j 不断向左移动（j--），直到找到一个 小于或等于 基准 pivot 的元素 arr[j] 才停下。i >= j，说明两个指针已经相遇或交错，这意味着整个区间已经被扫描完毕，分区过程结束。返回 j 作为分割点。i < j，说明 i 和 j 各自找到了一个“站错队”的元素（arr[i] 在左边但偏大，arr[j] 在右边但偏小），此时 交换 arr[i] 和 arr[j]。交换后，继续下一轮的扫描。Hoare 方案的一个关键特性
与 Lomuto 方案不同，Hoare 分区结束后：
j 这个位置上。[left, j] 区间内的所有元素都 小于或等于 基准。[j+1, right] 区间内的所有元素都 大于或等于 基准。这对递归调用意味着什么？
j 可能不是基准的最终位置，所以递归处理的子数组必须是 [left, j] 和 [j+1, right]。[left, j-1]），否则如果 j 恰好是基准所在的位置，可能会导致无限递归。#include <cstdio>
#include <vector>
#include <utility>
#include <random>
using std::vector;
using std::swap;
using std::mt19937;
using std::uniform_int_distribution;
using std::random_device;
/**
* @brief Hoare 分区函数
* @param arr 要分区的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
* @return 一个分割点索引 j，使得 [left, j] <= pivot 且 [j+1, right] >= pivot
*/
int hoarePartition(vector<int> &arr, int left, int right) {
// 1. 选择第一个元素作为基准
int pivot_value = arr[left];
int i = left - 1, j = right + 1;
while (true) {
// 2. 从左向右找到第一个 >= pivot 的元素
do {
i++;
} while (arr[i] < pivot_value);
// 3. 从右向左找到第一个 <= pivot 的元素
do {
j--;
} while (arr[j] > pivot_value);
// 4. 如果指针相遇或交错，分区完成
if (i >= j) return j;
// 5. 交换站错队的元素
swap(arr[i], arr[j]);
}
}
/**
* @brief 随机快速排序函数（Hoare 分区版）
* @param arr 要排序的数组
* @param left 区间的左边界索引
* @param right 区间的右边界索引
*/
void randomizedQuickSort(vector<int> &arr, int left, int right) {
if (left < right) {
// 随机化：选择一个随机基准并与第一个元素交换
static mt19937 generator(random_device{}());
uniform_int_distribution<int> distribution(left, right);
int pivot_idx = distribution(generator);
swap(arr[pivot_idx], arr[left]);
// 执行 Hoare 分区
int partition_idx = hoarePartition(arr, left, right);
// 递归地对左右两个子数组进行排序
// 注意这里的递归边界
randomizedQuickSort(arr, left, partition_idx);
randomizedQuickSort(arr, partition_idx + 1, right);
}
}
int main()
{
int n; scanf("%d", &n);
vector<int> arr(n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
randomizedQuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d%c", arr[i], i == n - 1 ? '\n' : ' ');
}
return 0;
}
时间复杂度分析
快速排序的时间复杂度取决于 分区（Partition） 操作的好坏，而分区的好坏又取决于 基准（Pivot） 的选择。
最佳情况分析
如果每次都能完美地平分数组，那么处理一个大小为 \(n\) 的问题，需要：
最坏情况分析
对于 随机 快速排序，最坏情况是指 运气差到极点，每次随机选择都恰好选中了当前子数组的最大或最小值。
如果每次分区都产生一个 \(n-1\) 和一个 \(0\) 的划分，递归关系式为：\(T(n)=T(n-1)+O(n)=O(n^2)\)。
最坏情况 \(O(n^2)\) 听起来很吓人，但 随机化 使得这种情况在实践中几乎不可能发生。数学家证明这种算法的平均时间复杂度是 \(O(n \log n)\)。
当算法的最坏时间复杂度的发生概率较小时，平均意义下的时间耗用能够更加准确地度量算法的性能。算法在所有实例上的平均时间耗用，称为算法的平均时间复杂度。
选择题：假设快速排序算法的输入是一个长度为 \(n\) 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为？
C
选择题：考虑对 n 个数进行排序，以下最坏时间复杂度低于 \(O(n^2)\) 的排序方法是？
正确答案是 C。
综上所述，只有归并排序的最坏时间复杂度 \(O(n \log n)\) 低于 \(O(n^2)\)。
选择题：排序的算法很多，若按排序的稳定性和不稳定性分类，则下列哪个是不稳定排序？
C。
程序阅读题
#include <iostream>
using namespace std;
const int N = 1000;
int c[N];
int logic(int x, int y) {
return (x & y) ^ ((x ^ y) | (~x & y));
}
void generate(int a, int b, int *c) {
for (int i = 0; i < b; i++)
c[i] = logic(a, i) % (b + 1);
}
void recursion(int depth, int *arr, int size) {
if (depth <= 0 || size <= 1) return;
int pivot = arr[0];
int i = 0, j = size - 1;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
recursion(depth - 1, arr, j + 1);
recursion(depth - 1, arr + i, size - i);
}
int main() {
int a, b, d;
cin >> a >> b >> d;
generate(a, b, c);
recursion(d, c, b);
for (int i = 0; i < b; ++i) cout << c[i] << " ";
cout << endl;
}
判断题
当 \(1000 \ge d \ge b\) 时，输出的序列是有序的。
当输入 5 5 1 时，输出为 1 1 5 5 5。
假设数组 \(c\) 长度无限制，该程序所实现的算法的时间复杂度是 \(O(b)\) 的。
选择题
int logic(int x, int y) 的功能是？10 100 100 时，输出的第 100 个数是？代码分析
logic(int x, int y) 函数：这个函数执行了一系列位运算，乍一看是一个比较复杂的式子。但是考虑到位运算是独立的，因此把 \(x,y\) 的每一位等于 0 或 1 的情况代入计算就可发现，只有都等于 0 时结果才为 0，否则结果为 1，而这实际上就相当于是按位或。generate(int a, int b, int c) 函数：这个函数会用 logic 函数的结果来填充数组 c，它会计算 c[i] = (a | i) % (b + 1)，其中 i 从 0 到 b-1。recursion(int depth, int *arr, int size) 函数：这是一个实现了快速排序的递归函数。
pivot。depth 参数限制了递归的深度，如果 depth 耗尽，递归就会停止。depth 的值足够大（例如，大于等于数组大小 b），这个函数就能将数组完全排序。如果 depth 很小，相当于快速排序只进行了几趟。判断题
正确。recursion 函数是一个快速排序实现，在最坏的情况下（例如，数组已经有序或逆序），快速排序需要的递归深度等于数组的长度 b。题目条件 d \ge b 保证了递归深度 d 总是足够完成排序，不会因为深度限制而提前终止。
错误。根据前面对 generate 函数的理解可以发现，c[0] = (5|0)%6 = 5; c[1] = (5|1)%6 = 5; c[2] = (5|2)%6 = 7%6 = 1; c[3] = (5|3)%6 = 7%6 = 1; c[4] = (5|4)%6 = 5;，初始数组 c 为 {5, 5, 1, 1, 5}。depth 为 1，表示只执行一层分区操作。pivot = c[0] = 5，分区过程会不停交换左侧的一个大于等于基准值的元素和右侧的一个小于等于基准值的元素，最终结果为 {5, 1, 1, 5, 5}。
错误。程序总的时间复杂度由 generate 和 recursion 决定，generate 的复杂度是 \(O(b)\)，recursion 的复杂度是 \(O(d \times b)\)，因为它执行 \(d\) 层的分区，每层分区操作的总时间是 \(O(b)\)。总复杂度为 \(O(b)+O(d \times b) = O(d \times b)\)，因为 \(d\) 是一个输入变量，不能被当作常数，所以时间复杂度依赖于 \(d\) 和 \(b\)。
选择题
B。如上面的代码分析所示，功能为按位或。
C。输入满足 d >= b 的条件，所以 recursion 函数会将数组 c 完全排序。问题所求的“第 100 个数”就是排序后数组的最后一个元素，也就是数组中的最大值。需要找到 c[i] = (10 | i) % 101 在 i 从 0 到 99 的范围内的最大值。分析 (10 | i) 的可能值，i 的最大值是 99，所以 10 | i 的值不会超过 107。需要找到 i 使得 (10 | i) 在模 101 之后最大。情况一：10 | i >= 101，10 | 99 = 107, 107 % 101 = 6，10 | 98 = 106, 106 % 101 = 5，其他 10 | i 的值都小于 106，所以这种情况下，能产生的最大余数是 6。情况二：10 | i < 101，在这种情况下，(10 | i) % 101 就等于 10 | i。需要找到 i 使得 10 | i 的值最大，且小于 101。此时相当于优先满足最高位，权值为 \(2^6 = 64\) 的位可以为 1，这样按位或上 10 之后是 74，接下来考虑权值位 $2^5 = 32 $ 的位，这一位不能得到 1，不然结果就超过 101 了，以此类推，最终能得到的最大结果是 \(2^6 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 95\)。因此，数组 c 中的最大值是 95，排序后，第 100 个数就是 95。
快速选择算法用于高效地从一个无序数组中找到第 k 大或第 k 小的元素。
一个直接的想法是先对整个数组进行排序，如何直接返回对应索引的元素。这样做时间复杂度是 \(O(n \log n)\)，属于杀鸡用牛刀，为了仅仅找到一个元素，把整个数组都排好序了，做了很多不必要的工作。
快速选择算法的优势在于：它能在平均 \(O(n)\) 的线性时间内找到这个元素，这在理论上是能达到的最优平均时间复杂度。它避免了对整个数组进行排序，只关注包含目标元素的那一部分数据，从而大大减少了计算量。
它的核心思想巧妙地借鉴了快速排序。
k 正好在这个区间，那说明这个基准就是对应的元素值。k < l，说明要找的元素肯定在基准的左边。完全不需要关心右边的子数组了，只需要在左边的子数组中继续寻找。k > r，说明要找的元素肯定在基准的右边。同样舍弃左边的部分，只需要在右边的子数组中继续寻找。与快速排序的关键区别：
这种“只走一边”的策略，就是它能达到 \(O(n)\) 平均时间复杂度的根本原因。
#include <cstdio>
#include <vector>
#include <utility>
#include <random>
using namespace std;
pair<int, int> threeWayPartition(vector<int> &arr, int left, int right) {
int pivot_value = arr[right];
int low = left; // 小于区的右边界+1
int mid = left; // 当前检查的元素
int high = right; // 大于区的左边界-1
while (mid <= high) {
if (arr[mid] < pivot_value) {
swap(arr[low], arr[mid]);
low++; mid++;
} else if (arr[mid] > pivot_value) {
swap(arr[high], arr[mid]);
high--;
} else { // arr[mid] == pivot_value
mid++;
}
}
return {low, high};
}
int quickSelect(vector<int> &nums, int left, int right, int target_idx) {
while (left <= right) {
static mt19937 generator(random_device{}());
uniform_int_distribution<int> distribution(left, right);
int pivot_idx = distribution(generator);
swap(nums[pivot_idx], nums[right]);
// 执行三向划分，返回等于基准值区域的左右边界 [lt, gt]
pair<int, int> pivot_range = threeWayPartition(nums, left, right);
int lt = pivot_range.first, gt = pivot_range.second;
if (target_idx >= lt && target_idx <= gt) {
// 目标索引落在等于区域，找到了答案
return nums[lt];
} else if (target_idx < lt) {
// 目标在小于区域，更新右边界，继续在左边查找
right = lt - 1;
} else { // target_idx > gt
// 目标在大于区域，更新左边界，继续在右边查找
left = gt + 1;
}
}
// 理论上在有效输入下不会到达这里
return -1;
}
int main()
{
int n, k; scanf("%d%d", &n, &k);
vector<int> a(n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d\n", quickSelect(a, 0, n - 1, k));
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。