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 < 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 < high) {
int pi = partition(arr, low, high);
quickSortRecursive(arr, low, pi - 1);
quickSortRecursive(arr, pi + 1, high);
}
}

非递归实现快速排序

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

思路：

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