C++如何实现快速排序_C++快排算法递归与非递归实现-C++-PHP中文网

C++如何实现快速排序_C++快排算法递归与非递归实现

冰火之心

发布： 2025-12-19 17:53:02

原创

133人浏览过

快速排序基于分治思想，通过基准元素划分数组并递归或迭代排序子区间；C++中可递归实现（简洁直观）或非递归用栈模拟（避免栈溢出），核心为partition函数；实际推荐使用std::sort。

c++如何实现快速排序_c++快排算法递归与非递归实现

快速排序是一种高效的排序算法，基于分治思想，通过选择一个基准元素将数组划分为两部分，使得左边元素小于等于基准，右边大于等于基准，然后递归或迭代处理左右子区间。C++中可以使用递归和非递归两种方式实现快排。

递归实现快速排序

递归版本是快排最直观的写法。核心在于分区（partition）操作和递归调用。

步骤如下：

选取一个基准值（通常选第一个、最后一个或中间元素）
重新排列数组，使小于基准的放左边，大于的放右边
对左右两个子数组分别递归执行快排

AI Sofiya

一款AI驱动的多功能工具

147

查看详情

立即学习“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& arr, int low, int high) { if (low

非递归实现快速排序

非递归版本使用栈模拟函数调用过程，避免深层递归带来的栈溢出风险。

思路：

手动创建一个栈存储待处理的区间 [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），性能更优且安全。

以上就是C++如何实现快速排序_C++快排算法递归与非递归实现的详细内容，更多请关注php中文网其它相关文章！