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

前言

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

核心思路：手动模拟栈

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 {
     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);
        }
    }
}