c++实现非递归快速排序

C++实现非递归快速排序通常使用栈来模拟递归过程。这是一种常见的技巧，可以避免直接的递归调用带来的栈溢出问题。以下是基本的非递归快速排序算法的步骤：

1. **分治策略**: 快速排序的核心思想是选取一个基准元素（pivot），将数组分为两部分，一部分所有元素都小于基准，另一部分所有元素都大于或等于基准。

2. **栈实现**:
- 初始化一个空栈，然后压入两个指针，一个指向数组的开始，另一个指向结束。
- 当栈不为空且两个指针未相遇时，执行以下操作：
- 弹出栈顶元素，取出基准元素。
- 找到基准的正确位置（小于基准的元素在左边，大于等于基准的元素在右边）。
- 将新的分割点的指针（小于基准的右边界）压入栈中。
- 将基准右侧的指针（大于等于基准的左边界）压入栈中。

3. **交换和分区**:
- 在找到新分割点的过程中，如果遇到比基准小的元素，就将其与基准左边的元素交换，这样左侧的所有元素都小于基准。
- 如果遇到比基准大的元素，不做交换。

4. **递归终止条件**:
- 当栈中只剩下一个元素或为空时，表示已经对当前子区间完成了排序。

5. **合并结果**:
- 从栈中弹出的子区间都是排好序的，可以通过遍历栈，依次将每个子区间的有序部分合并回原始数组。

下面是简化的C++代码示例：

#include <vector>
#include <stack>

int partition(std::vector<int>& 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++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void non_recursive_quick_sort(std::vector<int>& arr, int low, int high) {
    std::stack<std::pair<int, int>> s;
    s.push({low, high});

    while (!s.empty()) {
        auto [left, right] = s.top();
        s.pop();

        if (left < right) {
            int pivot_pos = partition(arr, left, right);
            s.push({left, pivot_pos - 1});
            s.push({pivot_pos + 1, right});
        }
    }
}

// 示例用法
int main() {
    std::vector<int> vec = {9, 7, 5, 11, 12, 2, 14, 3, 10};
    non_recursive_quick_sort(vec, 0, vec.size() - 1);
    // 输出排序后的数组
    for (const auto& num : vec) {
        std::cout << num << " ";
    }
    return 0;
}