快速排序非递归实现详解：原理与代码

引言

在面试或实际工程中，面试官常考察快速排序的非递归实现。这不仅是对算法逻辑的检验，更是对栈结构应用能力的考察。本文将结合图解思路与 C++ 代码，深入讲解如何用手动栈模拟递归过程。

核心原理

手动模拟系统栈

标准递归快排中，quickSort(left, right) 调用时，系统会自动分配内存（函数调用栈）来记录当前的 left 和 right 以及返回地址。在非递归版本中，我们不再依赖系统栈，而是自己创建一个显式的栈（Stack）数据结构来管理待处理的区间。

用栈存取数组区间

1. 入栈操作：存储每一次需要排序的子数组起止下标（begin, end）。由于栈遵循后进先出（LIFO）特性，为了模拟递归中先处理左区间的顺序，我们需要优先将右区间压入栈，再压入左区间。
2. 出栈操作：每次从栈顶弹出一对下标，对这段范围执行分区操作（Partition），生成新的左右子区间后，再次压回栈中。

流程解析

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

首先初始化一个空栈，将整个数组的任务 [0, N-1] 压入。接着进入循环，只要栈不为空，就重复以下步骤：

1. 弹栈：取出一对任务下标 (begin, end)。
2. 分区：使用快慢指针法（Hoare 或 Lomuto 变体）分割当前区间，得到基准值位置 keyi。此时数组被分为 [begin, keyi-1]、keyi、[keyi+1, end] 三部分。
3. 记录区间：定义左区间 [left1, right1] 和右区间 [left2, right2]。
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) {
     keyi = left; 
     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);
        }
    }
}