C++中如何实现快速排序的非递归版本

快速排序的核心逻辑是选取基准元素，将数组分为左右两部分，左边元素都小于基准，右边元素都大于基准，再对两部分分别排序。递归版本通过函数调用栈实现这一过程，但递归深度过大会导致栈溢出，非递归版本则手动维护一个栈来保存待排序的区间，避免系统栈溢出的问题。

非递归快速排序的实现思路

非递归快速排序的整体流程可以分为以下几步：

• 首先实现一个划分函数，完成数组的区间划分，返回基准元素的最终位置
• 创建一个栈，用于存储待排序的区间左右边界
• 先将初始的整个数组区间入栈
• 循环从栈中取出区间，对该区间进行划分，再将划分后产生的两个子区间（如果长度大于1）分别入栈
• 直到栈为空，说明所有区间都排序完成

核心代码实现

划分函数实现

划分函数的作用是选取最左元素作为基准，将数组区间[left, right]中小于基准的元素移到左边，大于基准的移到右边，最后返回基准的位置。

#include <vector>
#include <stack>
using namespace std;

// 划分函数，返回基准元素的最终位置
int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[left]; // 选取最左元素作为基准
    int i = left;
    int j = right;
    while (i < j) {
        // 从右往左找第一个小于基准的元素
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        // 从左往右找第一个大于基准的元素
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    // 将基准元素放到最终位置
    arr[i] = pivot;
    return i;
}

非递归快速排序主函数

主函数通过栈来保存待处理的区间，模拟递归的调用过程。

void quickSortNonRecursive(vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }
    stack<pair<int, int>> stk;
    // 初始区间入栈，先右后左，保证出栈时先处理左区间
    stk.push({arr.size() - 1, 0});
    while (!stk.empty()) {
        // 取出当前待处理的区间
        int right = stk.top().first;
        int left = stk.top().second;
        stk.pop();
        // 区间长度大于1才需要排序
        if (left < right) {
            int pivotPos = partition(arr, left, right);
            // 如果左子区间长度大于1，入栈
            if (pivotPos - 1 > left) {
                stk.push({pivotPos - 1, left});
            }
            // 如果右子区间长度大于1，入栈
            if (pivotPos + 1 < right) {
                stk.push({right, pivotPos + 1});
            }
        }
    }
}

完整使用示例

以下是调用非递归快速排序的完整示例，包含数组初始化和结果打印。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 划分函数
int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[left];
    int i = left;
    int j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = pivot;
    return i;
}

// 非递归快速排序
void quickSortNonRecursive(vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }
    stack<pair<int, int>> stk;
    stk.push({arr.size() - 1, 0});
    while (!stk.empty()) {
        int right = stk.top().first;
        int left = stk.top().second;
        stk.pop();
        if (left < right) {
            int pivotPos = partition(arr, left, right);
            if (pivotPos - 1 > left) {
                stk.push({pivotPos - 1, left});
            }
            if (pivotPos + 1 < right) {
                stk.push({right, pivotPos + 1});
            }
        }
    }
}

int main() {
    vector<int> arr = {3, 6, 8, 2, 1, 9, 5, 4, 7};
    cout << "排序前数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    quickSortNonRecursive(arr);
    cout << "排序后数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

实现注意事项

• 栈中存储的区间边界要注意顺序，示例中先压入右边界再压入左边界，出栈时先取右再取左，也可以调整顺序，只要保证逻辑一致即可
• 划分函数的基准选择可以优化，比如三数取中法，避免有序数组下快速排序退化成O(n²)的时间复杂度
• 当待排序区间长度较小时，可以切换为插入排序，进一步提升整体排序效率
• 栈的大小取决于快速排序的递归深度，最坏情况下栈的大小为O(n)，平均情况下为O(log n)，相比递归版本的系统栈更稳定

时间复杂度分析

非递归快速排序的时间复杂度和递归版本一致：

空间复杂度为栈的最大深度，平均O(log n)，最坏O(n)，优于递归版本的系统栈调用开销，更适合处理大规模数据排序场景。

C++快速排序非递归栈排序算法修改时间：2026-07-02 04:42:45