快速排序非递归实现详解：手动模拟栈结构

核心原理

在标准的递归快速排序中，系统会自动分配内存（函数调用栈）来记住当前的 left 和 right 是多少，以及函数执行完后该回到哪里。在非递归版本中，我们不需要系统帮忙，而是自己创建一个栈（Stack）数据结构来显式管理这些状态。

用栈存取数组区间

核心操作分为两步：

1. 入栈：存储每一次需要排序的子数组的起止下标（begin, end）。由于栈的特性是先进后出，为了模拟递归先处理左区间的顺序，我们需要优先将右区间压入栈，再压入左区间。
2. 出栈与分区：每次从栈里拿出一对下标，对这段范围进行'分区操作'，然后把产生的新范围（左半区和右半区）再扔回栈里。

算法流程

假设存在数组 a，初始化时准备一个空栈，先把整个数组的任务扔进去：入栈 [0, N-1]。

接着进入 while(栈非空) 循环：

1. 弹栈：拿出一个任务（begin, end）。
2. 分区：通过快慢指针法进行分割当前处理任务，获取基准值位置 keyi。此时数组被分为 [begin, keyi-1]、keyi、[keyi+1, end]。
3. 记录左右区间：
   • 左区间：left1 = begin, right1 = keyi - 1
   • 右区间：left2 = keyi + 1, right2 = end
4. 入栈左右区间：优先压入右区间，再压入左区间。因为栈是后进先出，这样下一轮循环就会先处理左边，完美模拟递归的顺序。

注意：如果区间只有一个元素或不存在，则不入栈。

当栈变空时，说明所有的大区间都被切成了小区间，小区间都被切没了，数组就有序了。

代码实现

下面展示基于 C++ 标准库 stack 的非递归实现。这里使用快慢指针法进行分区，逻辑上保持与递归一致，但空间换在了堆内存上。

#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 的下标
     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);
        }
    }
}