非递归快排需用std::stack存储子区间边界（left/right），而非单个索引；压栈时先右后左可降低栈深；partition必须返回合法基准位置并确保子区间收缩，否则易致死循环或越界。
为什么递归快排在栈深度大时会崩
递归实现的快速排序，最坏情况下（比如数组已有序）递归深度达到 O(n)，容易触发栈溢出。尤其在嵌入式或栈空间受限环境里，std::stack 模拟调用栈是更可控的选择。
用 std::stack 存什么才对
不能只存 pivot 位置或单个索引——得存待处理的子区间边界。标准做法是压入一对 left 和 right 下标（通常用 std::pair<int int></int> 或自定义结构体），每次弹出一个区间，partition 后把合法的左右子区间再压入。
- 压栈顺序不影响正确性，但先压右区间、再压左区间，能略微降低栈峰值深度（模拟尾递归优化）
- 必须检查
left 才压栈，避免无效区间（如 <code>left == right或left > right） - 分区函数
partition必须返回基准元素最终位置，且保证左段 ≤ 基准、右段 ≥ 基准
非递归快排的典型实现骨架
核心逻辑干净：初始化栈 → 压入整个区间 → 循环弹出、划分、压入子区间。注意 partition 的实现要和递归版一致，否则行为不一致。
void quickSortIterative(std::vector<int>& arr) {
if (arr.size() > stk;
stk.push({0, static_cast<int>(arr.size()) - 1});
<pre class="brush:php;toolbar:false;">while (!stk.empty()) {
auto [left, right] = stk.top(); stk.pop();
if (left >= right) continue;
int pivot_idx = partition(arr, left, right);
// 先压右半，后压左半（让左半先处理，减少栈深）
if (pivot_idx + 1 <p>}</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）"><img
src="https://img.php.cn/upload/manual/000/000/001/5d6de31fedca2993.png" alt="C函数速查手册（CHM版）" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）" class="overflowclass">C函数速查手册（CHM版）</a>
<p class="overflowclass">C函数速查手册（CHM版）</p>
</div>
<a rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
partition 函数写错会导致无限循环或越界
非递归版本对 partition 更敏感：如果返回位置没落在 [left, right] 内，或者左右子区间判断条件漏掉等号，就可能压入非法区间，导致死循环或访问越界。
- 推荐用 Lomuto 分区方案（简单易控）：选
arr[right]为 pivot，维护smaller指针指向最后一个小于等于 pivot 的位置 - 务必确保返回值满足
left ，且 <code>arr[pivot_idx]是 pivot 的最终位置 - 测试边界用例：
{1,2,3,4,5}、{5,4,3,2,1}、{3,3,3}—— 尤其重复元素多时，分区是否稳定、子区间是否收缩
真正麻烦的不是写循环，而是 partition 边界和栈压入逻辑稍有偏差，程序就静默跑飞。建议先手写一遍递归版，再逐行对照改栈逻辑。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
