快速排序基于分治思想，通过基准元素划分数组并递归或迭代排序子区间；C++中可递归实现（简洁直观）或非递归用栈模拟（避免栈溢出），核心为partition函数；实际推荐使用std::sort。
快速排序是一种高效的排序算法，基于分治思想，通过选择一个基准元素将数组划分为两部分，使得左边元素小于等于基准，右边大于等于基准，然后递归或迭代处理左右子区间。C++中可以使用递归和非递归两种方式实现快排。
递归实现快速排序
递归版本是快排最直观的写法。核心在于分区（partition）操作和递归调用。
步骤如下：
- 选取一个基准值（通常选第一个、最后一个或中间元素）
- 重新排列数组，使小于基准的放左边，大于的放右边
- 对左右两个子数组分别递归执行快排
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
using namespace std;
<p>int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 以最后一个元素为基准
int i = low - 1; // 小于基准的区域边界</p><pre class='brush:php;toolbar:false;'>for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;}
void quickSortRecursive(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSortRecursive(arr, low, pi - 1); quickSortRecursive(arr, pi + 1, high); } }
非递归实现快速排序
非递归版本使用栈模拟函数调用过程，避免深层递归带来的栈溢出风险。
思路：
- 手动创建一个栈存储待处理的区间 [low, high]
- 循环取出栈顶区间进行分区
- 将分割后的子区间压入栈中，直到栈为空
立即学习“C++免费学习笔记（深入）”；
#include <stack>
<p>void quickSortIterative(vector<int>& arr, int low, int high) {
stack<pair<int, int>> stk;
stk.push({low, high});</p><pre class='brush:php;toolbar:false;'>while (!stk.empty()) {
auto [l, h] = stk.top();
stk.pop();
if (l < h) {
int pi = partition(arr, l, h);
stk.push({l, pi - 1});
stk.push({pi + 1, h});
}
}}
完整测试示例
下面是一个完整的测试程序，验证两种实现的效果。
立即学习“C++免费学习笔记（深入）”；
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
<pre class='brush:php;toolbar:false;'>cout << "原数组: ";
for (int x : arr) cout << x << " ";
cout << endl;
// 使用递归快排
quickSortRecursive(arr, 0, arr.size() - 1);
cout << "递归排序后: ";
for (int x : arr) cout << x << " ";
cout << endl;
// 再次打乱用于非递归测试
arr = {64, 34, 25, 12, 22, 11, 90};
quickSortIterative(arr, 0, arr.size() - 1);
cout << "非递归排序后: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;}
基本上就这些。递归写法简洁易懂，适合一般场景；非递归更稳定，适合大数据量或栈空间受限环境。关键在于正确实现 partition 函数，并注意边界条件。实际开发中也可以直接使用 std::sort，它内部结合了快排、堆排和插入排序（Introsort），性能更优且安全。
