非递归快排需用显式栈模拟递归调用顺序：先压右区间再压左区间，确保左子区间先处理；partition须原地交换并返回基准索引；边界检查l>=r时跳过，避免栈溢出。
为什么快速排序的递归版本容易栈溢出
递归版 quick_sort 在最坏情况下（如已排序数组）会退化为 O(n) 递归深度，每层调用压栈函数帧，std::stack 或系统栈都可能耗尽。尤其在嵌入式或栈空间受限环境（如 Windows 默认 1MB 栈），std::bad_alloc 或段错误很常见。
非递归的核心是：把「待排序区间」抽象成 pair<int int></int>（左右下标），用显式栈代替函数调用栈。
用 std::stack 实现非递归快排的正确写法
关键不是“能不能用栈”，而是“压栈顺序”和“边界处理”是否与递归逻辑严格等价。错误写法（如先压左再压右）会导致分区后处理顺序错乱，影响稳定性（虽快排本就不稳定）或逻辑错误。
- 每次从栈中弹出一个区间
[l, r]，若l >= r直接跳过 - 调用
partition得到基准位置pivot_idx - 必须先压入右子区间（
[pivot_idx + 1, r]），再压入左子区间（[l, pivot_idx - 1]）——这样才能保证左子区间先被处理（模拟递归中先递归左再递归右的执行顺序） -
partition必须使用原地交换，且返回的是最终基准索引，不能只返回值
void quick_sort_iterative(std::vector<int>& arr) {
if (arr.size() <= 1) return;
std::stack<std::pair<int, int>> stk;
stk.push({0, static_cast<int>(arr.size()) - 1});
<pre class='brush:php;toolbar:false;'>while (!stk.empty()) {
auto [l, r] = stk.top();
stk.pop();
if (l >= r) continue;
int pivot_idx = partition(arr, l, r);
stk.push({pivot_idx + 1, r}); // 右区间后压，先处理
stk.push({l, pivot_idx - 1}); // 左区间先压，后处理
}}
立即学习“C++免费学习笔记（深入）”；
int partition(std::vector
如何避免小数组带来的栈开销和性能损失
纯非递归对小数组（如长度 c++ 的 std::sort）一定混合使用插入排序回退。
- 在
while (!stk.empty())循环内，弹出区间后先判断r - l + 1 ，满足则调用 <code>insertion_sort(arr, l, r) - 不要在
partition前做判断，否则小数组仍被压栈 - 插入排序实现要 inline 或定义为
static，避免函数调用开销
手写栈 vs std::stack：什么时候该换
std::stack 默认基于 std::deque，内存不连续，频繁 push/pop 有分配开销；但安全、无需手动管理。手写固定大小数组栈（如 std::array<:pair>, 64></:pair>）仅适合已知最大深度场景（如 2^20 元素最多需约 20 层栈），且必须加溢出检查。
- 若确定输入规模上限（如游戏引擎中排序顶点索引，最大 65536），可用静态栈避免动态分配
- 否则坚持
std::stack，但用std::stack<:pair>, std::vector<:pair>>></:pair></:pair>替代默认 deque，提升缓存友好性 - 永远不要用
malloc+free手写栈——C++ 中无 RAII 保障，异常安全难保证
非递归快排真正难的不是“怎么写栈”，而是分区函数的边界细节（比如 l 和 r 是否闭区间）、压栈顺序与递归语义的一致性，以及小数组优化的插入时机——这三个地方写错一个，结果就可能错位或变慢。
