快速排序非递归实现详解

前言

在实际工程中，递归实现的快速排序虽然简洁，但面对极端数据或超大数组时，系统调用栈的深度限制可能引发栈溢出。非递归版本通过手动管理栈结构，不仅规避了这一风险，也是对数据结构掌握程度的更好体现。

核心思路

手动模拟栈

递归的本质是系统隐式维护调用栈。在非递归实现中，我们需要显式创建一个栈（Stack），用来保存待处理的数组区间 [left, right]。

区间存取策略

由于栈遵循后进先出（LIFO）原则，为了模拟递归'先左后右'的执行顺序，在将子区间压入栈时，必须先压右区间，再压左区间。这样弹出时才能先处理左区间。

模拟过程演示

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

1. 初始化：将整个区间 [0, 9] 压入栈。
2. 循环处理：
   • 弹栈获取当前区间 [begin, end]。
   • 执行分区操作（Partition），得到基准值位置 keyi。
   • 此时数组被分为 [begin, keyi-1] 和 [keyi+1, end]。
   • 检查左右区间有效性（长度大于 1），按'先右后左'的顺序压入栈。
3. 结束条件：栈为空时，排序完成。

代码实现

以下是基于 C++ 标准库 std::stack 的实现，采用快慢指针法进行分区。

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

// 快慢指针分区法
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);
        }
    }
}