快速排序非递归实现详解

非递归快速排序实现

一、核心原理与思路

1.1 核心原理：手动模拟栈

在标准的递归快速排序中，系统会自动分配函数调用栈来记录当前的 left 和 right 以及返回位置。在非递归版本中，我们不需要系统帮忙，而是自己创建一个栈（Stack）数据结构。

1.2 核心操作：用栈存取数组区间

① 向栈中存储操作：存储每一次需要排序的子数组的起止下标（begin，end）。由于栈的特性是先进后出，优先处理左区间，再处理右区间，类似于二叉树的前序遍历。故而在存储的时候优先存储右区间，再进行存储左区间。 ② 向栈中拿取操作：每次从栈里拿出一对下标，对这段范围进行'分区操作'，然后把产生的新范围（左半区和右半区）再扔回栈里。

二、用栈来模拟存储区间

假设存在数组 a 为：[6, 1, 2, 3, 4, 5, 9, 7, 10, 8] 下标：[0 1 2 3 4 5 6 7 8 9] 定义 int left1：左区间数组的起始位置下标 定义 int right1：左区间数组的终止位值下标 则左区间数组的范围是：[left1 , right1] 定义 int left2：右区间数组的起始位置下标 定义 int right2：右区间数组的终止位置下标 则右区间数组的范围是：[left2，right2]

第一步：初始化栈 准备一个空栈，先把整个数组的任务扔进去：入栈：[0, N-1] 第二步：循环处理 这是一个 while(栈非空) 的循环：

1. 弹栈（Pop）：拿出一个任务（begin，end）。
2. 分区（Partition）：通过 Hoare 分区法进行分割当前处理任务，keyi = PartitionSlowFast(a, begin, end); 将其分为 [begin , keyi - 1] keyi [keyi+1 , end]
3. 记录左右区间：记录左区间 left1 = begin right1=keyi-1；记录右区间 left2 = keyi+1 right2=end。
4. 入栈左右区间：优先压入右区间，再压入左区间，因为栈是'后进先出'，这样下一轮循环就会先处理左边，模拟递归的顺序。 (💡 小贴士：区间只有一个元素不入栈，区间不存在也不入栈) 第三步：栈为空 当栈变空时，说明所有的大区间都被切成了小区间，小区间都被切没了（排序完成），数组就有序了！

三、代码实现

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

// 1. 实现快慢指针法分区 (PartitionSlowFast)
int PartitionSlowFast(int* a, int left, int right) {
    int keyi = left;
    int prev = left;
    int cur = left + 1;
     (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);
        }
    }
}