快速排序非递归实现详解

为什么需要手动模拟栈？

在标准的递归快速排序中，当我们写下 quickSort(a, left, right) 时，系统会自动分配一块内存（函数调用栈）来记住当前的 left 和 right 是多少，以及函数执行完后该回到哪里。这虽然方便，但在处理极大数据或最坏情况时，递归层数过深容易导致栈溢出。

在非递归版本中，我们不需要系统帮忙，而是自己创建一个栈（Stack）数据结构来接管这部分工作。

用栈来模拟存储区间

核心思路是用栈存取数组区间。每次从栈里拿出一对下标，对这段范围进行'分区操作'，然后把产生的新范围（左半区和右半区）再扔回栈里。

由于栈的特性是先进后出，为了模拟递归的顺序（先处理左边），我们在入栈时需要优先存储右区间，再存储左区间。这样下一轮循环弹出时，就会先拿到左区间进行处理。

假设存在数组 a 为 [6, 1, 2, 3, 4, 5, 9, 7, 10, 8]。

定义 left1, right1 为左区间起止下标，left2, right2 为右区间起止下标。

流程如下：

1. 初始化栈，先把整个数组的任务扔进去：入栈 [0, N-1]。
2. 进入 while(栈非空) 循环：
   • 弹栈（Pop）：拿出一个任务 (begin, end)。
   • 分区（Partition）：通过快慢指针法分割当前处理任务，得到基准值位置 keyi。此时数组被分为 [begin, keyi-1], keyi, [keyi+1, end]。
   • 记录左右区间：左区间 [begin, keyi-1]，右区间 [keyi+1, end]。
   • 入栈左右区间：优先压入右区间，再压入左区间。如果区间只有一个元素或不存在，则不入栈。
3. 当栈变空时，说明所有的大区间都被切成了小区间，排序完成。

代码实现

下面是具体的 C++ 实现，重点看栈的操作逻辑和分区函数的配合。

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