算法概述
快速排序（Quick Sort）是一种基于分治思想的高效排序算法，由英国计算机科学家 C.A.R. Hoare 于 1960 年提出。它是实际应用中最常用的排序算法之一，也是许多编程语言标准库中 sort 函数的底层实现（如 C++ STL 的 std::sort 采用了内省排序，其核心就是快速排序）。
快速排序的基本思路是：从数组中选一个"基准"元素，将数组划分为"小于基准"和"大于基准"两个部分，然后对这两部分递归地进行同样的操作，最终整个数组有序。
核心思想
- 选择基准（Pivot）：从数组中选取一个元素作为基准值。
- 分区（Partition）：重新排列数组，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。这一步完成后，基准元素就处于其最终的正确位置。
- 递归：对基准左右两侧的子数组分别重复上述过程，直到子数组长度为 0 或 1。
分治三要素：
- 分（Divide）：通过分区操作将数组分成两部分。
- 治（Conquer）：递归地对两个子数组排序。
- 合（Combine）：由于分区后基准已经就位，且左右子数组排序后整个数组自然有序，无需额外合并步骤。
算法步骤 / 伪代码
分区过程（Lomuto 分区方案）
function partition(arr, low, high):
pivot = arr[high] // 选择最后一个元素作为基准
i = low - 1 // i 指向小于基准的区域的最后一个元素
for j = low to high - 1:
if arr[j] <= pivot:
i = i + 1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[high]) // 将基准放到正确位置
return i + 1 // 返回基准的最终位置
整体流程
function quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high) // 分区，获得基准位置
quickSort(arr, low, pi - 1) // 递归排序左半部分
quickSort(arr, pi + 1, high) // 递归排序右半部分
C++ 代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 分区函数（Lomuto 分区方案）
// 选取 arr[high] 作为基准，将数组分为两部分
// 返回基准元素最终所在的下标
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // i 指向"小于 pivot 的区域"的末尾
for (int j = low; j < high; ++j) {
// 若当前元素小于等于基准，将其交换到左侧区域
if (arr[j] <= pivot) {
++i;
swap(arr[i], arr[j]);
}
}
// 将基准放到正确位置（i+1 处）
swap(arr[i + 1], arr[high]);
return i + 1; // 返回基准的最终下标
}
// 快速排序递归函数
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 分区
quickSort(arr, low, pi - 1); // 排序左半部分
quickSort(arr, pi + 1, high); // 排序右半部分
}
}
// 快速选择算法：在未完全排序的情况下找到第 k 大的元素
// 这是快速排序思想的经典应用——LeetCode 215
int quickSelect(vector<int>& arr, int low, int high, int k) {
if (low == high) return arr[low];
int pi = partition(arr, low, high);
// pi 是基准在排序数组中的最终位置（0-indexed）
// 我们要找的是第 k 大的元素，即排序后下标为 n-k 的元素
int target = arr.size() - k;
if (pi == target) {
return arr[pi];
} else if (pi < target) {
return quickSelect(arr, pi + 1, high, k);
} else {
return quickSelect(arr, low, pi - 1, k);
}
}
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() - 1, k);
}
int main() {
// ========== 测试快速排序 ==========
vector<int> arr = {10, 7, 8, 9, 1, 5, 3, 6, 4, 2};
cout << "排序前: ";
for (int x : arr) cout << x << " ";
cout << endl;
quickSort(arr, 0, arr.size() - 1);
cout << "排序后: ";
for (int x : arr) cout << x << " ";
cout << endl;
// ========== 测试快速选择 LeetCode 215 ==========
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
cout << "\n数组: ";
for (int x : nums) cout << x << " ";
cout << endl;
cout << "第 " << k << " 大的元素是: " << findKthLargest(nums, k) << endl;
k = 4;
cout << "第 " << k << " 大的元素是: " << findKthLargest(nums, k) << endl;
return 0;
}
复杂度分析
| 指标 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 时间 | O(n log n) | O(n²) | |
| 空间 | O(log n) | O(n) | |
| 稳定性 | ❌ 不稳定 | ||
-
时间复杂度说明：
- 最好/平均情况：每次分区都能将数组大致平分成两半，递归深度为 log n，每层处理 n 个元素，因此为 O(n log n)。
- 最坏情况：每次选取的基准都是当前子数组的最大值或最小值（例如数组已经有序且总是选最后一个元素作为基准），分区极不平衡，递归深度达到 n，总时间退化为 O(n²)。
- 通过随机选择基准或三数取中可以大幅降低最坏情况出现的概率。
-
空间复杂度说明：
- 空间开销主要来自递归调用栈。最好情况下递归深度为 O(log n)；最坏情况下达到 O(n)。
- 快速排序是原地排序，不需要额外的数组空间（归并排序则需要 O(n) 额外空间）。
-
稳定性：快速排序在分区过程中会交换不相邻的元素，因此是不稳定的排序算法。
应用场景
-
通用排序：快速排序是大多数编程语言标准库排序函数的首选或核心算法，适合大规模数据的通用排序场景。
-
快速选择（Quick Select）：利用快速排序的分区思想，可以在 O(n) 的平均时间内找到数组中第 k 大（或第 k 小）的元素，无需完全排序。典型题目如 LeetCode 215。
-
Top K 问题：求数组中的前 K 个最大/最小元素时，快速选择比完全排序更高效。
-
大规模数据处理：由于快速排序是原地排序且常数因子小，在实际系统中处理海量数据时表现优异。
经典例题
LeetCode 215 — 数组中的第K个最大元素
题目描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。（注意：需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素）
示例：
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
快速选择解法思路：
- 不需要对整个数组进行排序，只需利用快速排序的
partition函数。 - 每次 partition 后，基准元素会到达其最终位置
pi。 - 若
pi正好是第 k 大元素应在的位置（即n - k），则直接返回。 - 若
pi偏左，说明目标在右侧，递归右半部分；否则递归左半部分。 - 平均时间复杂度 O(n)，最坏 O(n²)。
（完整 C++ 代码已包含在上方的代码实现中）
