快速排序非递归实现详解：栈模拟与代码实战

前言

本文结合图解与代码，深入剖析快速排序的非递归实现。虽然递归版本在面试中常见，但面试官往往更倾向于考察非递归写法，因为这能体现对栈结构及内存管理的理解深度。

核心思路：手动模拟栈

1. 原理对比

在标准递归快排中，系统会自动分配调用栈来记录 left 和 right 以及返回地址。非递归版本则不再依赖系统，而是显式创建一个 Stack 数据结构来管理待处理的区间。

2. 操作逻辑

• 入栈：存储每次需要排序的子数组起止下标（begin, end）。
• 出栈：弹出一组下标进行分区，生成新的左右子区间后，再压回栈中。

由于栈遵循后进先出（LIFO）原则，为了模拟递归的'先左后右'处理顺序，我们在入栈时应先压右区间，再压左区间。这样下一轮循环弹出时，会先处理左区间。

流程解析

假设数组为 [6, 1, 2, 3, 4, 5, 9, 7, 10, 8]，我们定义左右区间的边界变量。

初始化阶段只需将完整区间 [0, N-1] 压入栈中。随后进入主循环，只要栈不为空，就持续执行以下操作：

1. 弹栈：取出一组任务 (begin, end)。
2. 分区：使用快慢指针法（PartitionSlowFast）分割当前区间，得到基准值位置 keyi。
3. 划分区间：此时数组被分为 [begin, keyi-1]、keyi、[keyi+1, end] 三部分。
4. 入栈：若左右子区间有效（长度大于 1），优先压入右区间，再压入左区间。

当栈彻底清空时，意味着所有子区间都已有序，排序完成。

区间分割逻辑如图所示：

代码实现

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

// 1. 实现快慢指针法分区 (PartitionSlowFast)
// prev 是慢指针，cur 是快指针
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 自己
        // prev 前进一步，并交换 prev 和 cur 的值
        if (a[cur] < a[keyi] && ++prev != cur) {
            swap(a[prev], a[cur]);
        }
        cur++;
    }
    // 最后将 key 放到 prev 的位置
    swap(a[keyi], a[prev]);
    return prev; // 返回 key 最终的位置
}

// 2. 非递归快速排序主函数
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);
        }
    }
}

非递归实现的优势

1. 防止栈溢出

递归的深度受限于系统栈大小。若数据量极大或处于最坏情况（如倒序），递归层数过深可能导致程序崩溃。非递归版本利用堆内存（Heap）存储栈，空间通常比系统栈大得多，更加安全。

2. 性能优化

在某些极端环境下，函数调用本身存在开销（保存现场、恢复现场）。手动模拟可以省去这些微小的开销，提升运行效率。