一、非递归实现快排的思路
1.1 核心原理：手动模拟栈
在标准的递归快速排序中，系统会自动分配函数调用栈来记录当前的 left 和 right 以及返回位置。在非递归版本中，我们需要自己创建一个栈（Stack）数据结构来模拟这一过程。
1.2 核心操作：用栈存取数组区间
- 向栈中存储操作：存储每一次需要排序的子数组的起止下标（begin, end）。由于栈的特性是先进后出，为了优先处理左区间，再处理右区间（模拟前序遍历），存储时应优先存储右区间，再存储左区间。
- 向栈中拿取操作：每次从栈里拿出一对下标，对这段范围进行'分区操作'，然后把产生的新范围（左半区和右半区）再扔回栈里。
二、用栈来模拟存储区间
假设存在数组 a 为：[6, 1, 2, 3, 4, 5, 9, 7, 10, 8]
定义 int left1：左区间数组的起始位置下标 定义 int right1：左区间数组的终止位置下标 则左区间数组的范围是：[left1, right1]
定义 int left2：右区间数组的起始位置下标 定义 int right2：右区间数组的终止位置下标 则右区间数组的范围是：[left2, right2]
第一步：初始化栈 准备一个空栈，先把整个数组的任务扔进去：入栈 [0, N-1]
第二步：循环处理 这是一个 while(栈非空) 的循环：
- 弹栈（Pop）：拿出一个任务（begin, end）。
- 分区（Partition）：通过 Hoare 分区法或快慢指针法进行分割当前处理任务，keyi = Partition(a, begin, end)。 将其分为 [begin, keyi - 1], keyi, [keyi + 1, end]。
- 记录左右区间： 记录左区间 left1 = begin, right1 = keyi - 1，即：[left1, right1] 记录右区间 left2 = keyi + 1, right2 = end，即：[left2, right2]
- 入栈左右区间：优先压入右区间，再压入左区间，因为栈是'后进先出'，这样下一轮循环就会先处理左边，模拟递归的顺序。 压入右区间：push(right2), push(left2) 压入左区间：push(right1), push(left1) 提示：区间只有一个元素不入栈，区间不存在也不入栈
第三步：栈为空 当栈变空时，说明所有的大区间都被切成了小区间，小区间都被切没了（排序完成），数组就有序了！
三、代码实现
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
// 1. 实现快慢指针法分区 (PartitionSlowFast)
// prev 是慢指针，cur 是快指针
int PartitionSlowFast(int* a, int left, 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);
}
}
}
