快速排序非递归实现详解

前言

在实际工程中，递归实现的快速排序虽然简洁，但面对极端数据或超大数组时，系统调用栈的深度限制可能引发栈溢出。非递归版本通过手动管理栈结构，不仅规避了这一风险，也是对数据结构掌握程度的更好体现。

核心思路

手动模拟栈

递归的本质是系统隐式维护调用栈。在非递归实现中，我们需要显式创建一个栈（Stack），用来保存待处理的数组区间 [left, right]。

区间存取策略

由于栈遵循后进先出（LIFO）原则，为了模拟递归'先左后右'的执行顺序，在将子区间压入栈时，必须先压右区间，再压左区间。这样弹出时才能先处理左区间。

模拟过程演示

假设数组为 [6, 1, 2, 3, 4, 5, 9, 7, 10, 8]，下标范围 [0, 9]。

1. 初始化：将整个区间 [0, 9] 压入栈。
2. 循环处理：
   • 弹栈获取当前区间 [begin, end]。
   • 执行分区操作（Partition），得到基准值位置 keyi。
   • 此时数组被分为 [begin, keyi-1] 和 [keyi+1, end]。
   • 检查左右区间有效性（长度大于 1），按'先右后左'的顺序压入栈。
3. 结束条件：栈为空时，排序完成。

代码实现

以下是基于 C++ 标准库 std::stack 的实现，采用快慢指针法进行分区。

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

// 快慢指针分区法
int PartitionSlowFast(int* a, int left, int right) {
    int keyi = left; // 选取最左边为 key 的下标
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        // 如果快指针指向的值小于 key，且 prev 下一步不是 cur 自己
        if (a[cur] < a[keyi] && ++prev != cur) {
            swap(a[prev], a[cur]);
        }
        cur++;
    }
    // 最后将 key 放到 prev 的位置
    swap(a[keyi], a[prev]);
    return prev;
}

// 非递归快速排序主函数
void QuickSortNonR(int* a, int left, int right) {
    stack<int> st;
    // 初始状态入栈：注意栈是后进先出
    // 我们希望出来的时候先拿 begin，再拿 end
    // 所以先压入 right (end)，再压入 left (begin)
    if (left < right) {
        st.push(right);
        st.push(left);
    }

    while (!st.empty()) {
        // 取栈顶元素
        int begin = st.top(); st.pop();
        int end = st.top(); st.pop();

        // 使用快慢指针法进行一趟分割
        int keyi = PartitionSlowFast(a, begin, end);

        // [begin, keyi-1] keyi [keyi+1, end]
        // 核心逻辑保持不变：先处理右边，再处理左边（为了模拟递归顺序）
        // 也就是先压入右区间，再压入左区间

        // 处理右区间 [keyi+1, end]
        int left2 = keyi + 1;
        int right2 = end;
        if (right2 - left2 >= 1) {
            st.push(right2);
            st.push(left2);
        }

        // 处理左区间 [begin, keyi-1]
        int left1 = begin;
        int right1 = keyi - 1;
        if (right1 - left1 >= 1) {
            st.push(right1);
            st.push(left1);
        }
    }
}

优势分析

防止栈溢出

递归深度受限于系统栈大小。对于倒序等最坏情况，递归层数过深会导致崩溃。非递归版本使用堆内存（Heap）存储栈，空间通常更大，更加安全。

性能优化

在某些极端环境下，函数调用的现场保存与恢复存在微小开销。手动模拟可以省去这部分开销，尽管在现代编译器优化下差异不大，但在对性能敏感的场景仍有意义。