快速排序非递归实现详解：基于栈的模拟思路

快速排序非递归实现详解

在工程实践中，递归虽然简洁，但受限于系统调用栈的深度。当数据量极大或出现最坏情况（如数组已逆序）时，递归层数过深极易导致栈溢出（Stack Overflow）。为了避免这一风险，我们通常采用显式栈来模拟递归过程，将函数调用栈转移到堆内存中管理。这不仅提升了程序的健壮性，也让我们对数据结构有了更直观的理解。

核心原理：手动模拟栈

标准的递归快排中，quickSort(a, left, right) 会自动保存现场。非递归版本则需要我们自己维护一个栈（Stack），用来存储待处理的子数组区间 [begin, end]。

由于栈遵循'后进先出'（LIFO）原则，为了保持与递归相同的处理顺序（即优先处理左子区间），我们需要先压入右区间，再压入左区间。这样弹出时，左区间会先被取出处理。

实现流程

1. 初始化：创建一个空栈，将整个数组的范围 [0, N-1] 压入栈中。
2. 循环处理：只要栈不为空，就执行以下操作：
   • 弹栈：取出当前待处理的区间 [begin, end]。
   • 分区：使用快慢指针法（PartitionSlowFast）进行分割，得到基准值位置 keyi。此时数组被分为 [begin, keyi-1]、keyi、[keyi+1, end] 三部分。
   • 记录并压栈：分别检查左右两个新区间是否有效（长度大于 1）。若有效，按照'先右后左'的顺序压入栈中。
3. 结束条件：当栈为空时，说明所有区间都已有序，排序完成。

代码实现

下面是一个完整的 C++ 实现示例。注意 PartitionSlowFast 函数负责单趟划分，而 QuickSortNonR 负责栈的管理逻辑。

#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;
     cur = left + ;
     (cur <= right) {
        
        
         (a[cur] < a[keyi] && ++prev != cur) {
            (a[prev], a[cur]);
        }
        cur++;
    }
    
    (a[keyi], a[prev]);
     prev; 
}


{
    stack<> st;
    
    
    
     (left < right) {
        st.(right);
        st.(left);
    }

     (!st.()) {
        
         begin = st.();
        st.();
         end = st.();
        st.();

        
         keyi = (a, begin, end);

        
        
        

        
         left2 = keyi + ;
         right2 = end;
        
         (right2 - left2 >= ) {
            st.(right2);
            st.(left2);
        }

        
         left1 = begin;
         right1 = keyi - ;
         (right1 - left1 >= ) {
            st.(right1);
            st.(left1);
        }
    }
}