C++ 非递归快速排序算法实现

以下是非递归快速排序的 C++ 代码：

#include <stack>
#include <utility>

void quickSort(int arr[], int left, int right) {
    std::stack<std::pair<int, int>> stk;
    stk.push(std::make_pair(left, right));

    while (!stk.empty()) {
        int l = stk.top().first;
        int r = stk.top().second;
        stk.pop();

        int pivot = arr[(l + r) / 2];
        int i = l, j = r;

        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            if (i <= j) {
                std::swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }

        if (l < j) stk.push(std::make_pair(l, j));
        if (i < r) stk.push(std::make_pair(i, r));
    }
}

该程序使用一个栈来模拟递归调用，每次将待排序区间的左右端点压入栈中。在每次循环中，从栈中弹出一个区间，并选取中间位置的元素作为枢轴，将小于枢轴的元素移到左边，大于枢轴的元素移到右边。然后将左右两个子区间压入栈中，直到栈为空，排序完成。