欢迎来到雄杰鑫电商资讯网
技术教程

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

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

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

递归实现快速排序

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

步骤如下：

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

#include 
#include 
using namespace std;

int partition(vector& arr, int low, int high) {
int pivot = arr[high]; // 以最后一个元素为基准
int i = low - 1;       // 小于基准的区域边界
for (int j = low; j zuojiankuohaophpcn high; j++) {
    if (arr[j] zuojiankuohaophpcn= 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]
    • 

  • 循环取出栈顶区间进行分区
    • 

  • 将分割后的子区间压入栈中，直到栈为空
    • 



#include 

void quickSortIterative(vector& arr, int low, int high) {
stack> stk;
stk.push({low, high});
while (!stk.empty()) {
    auto [l, h] = stk.top();
    stk.pop();

    if (l zuojiankuohaophpcn h) {
        int pi = partition(arr, l, h);
        stk.push({l, pi - 1});
        stk.push({pi + 1, h});
    }
}
}


完整测试示例


下面是一个完整的测试程序，验证两种实现的效果。


int main() {
    vector arr = {64, 34, 25, 12, 22, 11, 90};

cout zuojiankuohaophpcnzuojiankuohaophpcn "原数组: ";
for (int x : arr) cout zuojiankuohaophpcnzuojiankuohaophpcn x zuojiankuohaophpcnzuojiankuohaophpcn " ";
cout zuojiankuohaophpcnzuojiankuohaophpcn endl;

// 使用递归快排
quickSortRecursive(arr, 0, arr.size() - 1);

cout zuojiankuohaophpcnzuojiankuohaophpcn "递归排序后: ";
for (int x : arr) cout zuojiankuohaophpcnzuojiankuohaophpcn x zuojiankuohaophpcnzuojiankuohaophpcn " ";
cout zuojiankuohaophpcnzuojiankuohaophpcn endl;

// 再次打乱用于非递归测试
arr = {64, 34, 25, 12, 22, 11, 90};
quickSortIterative(arr, 0, arr.size() - 1);

cout zuojiankuohaophpcnzuojiankuohaophpcn "非递归排序后: ";
for (int x : arr) cout zuojiankuohaophpcnzuojiankuohaophpcn x zuojiankuohaophpcnzuojiankuohaophpcn " ";
cout zuojiankuohaophpcnzuojiankuohaophpcn endl;

return 0;
}


基本上就这些。递归写法简洁易懂，适合一般场景；非递归更稳定，适合大数据量或栈空间受限环境。关键在于正确实现 partition 函数，并注意边界条件。实际开发中也可以直接使用 std::sort，它内部结合了快排、堆排和插入排序（Introsort），性能更优且安全。






            
 ai 大数据 快速排序 排序算法 算法 是一个 是一种 迭代 两种 stream ios 栈 推荐使用 循环 排列 堆 if 可以使用 第一个 递归 c++ 中也 可以直接 int sort void 插入排序

相关文章

按ESC键退出。