c++中如何实现快速排序的非递归版本_c++使用栈优化排序算法【详解】

为什么快速排序的递归版本容易栈溢出

递归版 quick_sort 在最坏情况下（如已排序数组）会退化为 O(n) 递归深度，每层调用压栈函数帧，std::stack 或系统栈都可能耗尽。尤其在嵌入式或栈空间受限环境（如 Windows 默认 1MB 栈），std::bad_alloc 或段错误很常见。

非递归的核心是：把「待排序区间」抽象成 pair（左右下标），用显式栈代替函数调用栈。

用 std::stack 实现非递归快排的正确写法

关键不是“能不能用栈”，而是“压栈顺序”和“边界处理”是否与递归逻辑严格等价。错误写法（如先压左再压右）会导致分区后处理顺序错乱，影响稳定性（虽快排本就不稳定）或逻辑错误。

• 每次从栈中弹出一个区间 [l, r]，若 l >= r 直接跳过
• 调用 partition 得到基准位置 pivot_idx
• 必须先压入右子区间（[pivot_idx + 1, r]），再压入左子区间（[l, pivot_idx - 1]）——这样才能保证左子区间先被处理（模拟递归中先递归左再递归右的执行顺序）
• partition 必须使用原地交换，且返回的是最终基准索引，不能只返回值

void quick_sort_iterative(std::vector& arr) {
    if (arr.size() <= 1) return;
    std::stack> stk;
    stk.push({0, static_cast(arr.size()) - 1});
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++免费学习笔记（深入）”；

							

								
								

									蚂蚁PPT
									
AI在线智能生成PPT
								
								下载 
							
						
int partition(std::vector& arr, int l, int r) {
int pivot = arr[r];
int i = l;
for (int j = l; j 
如何避免小数组带来的栈开销和性能损失
纯非递归对小数组（如长度 std::sort）一定混合使用插入排序回退。

在 while (!stk.empty()) 循环内，弹出区间后先判断 r - l + 1 ，满足则调用 insertion_sort(arr, l, r)

不要在 partition 前做判断，否则小数组仍被压栈
插入排序实现要 inline 或定义为 static，避免函数调用开销

手写栈 vs std::stack：什么时候该换
std::stack 默认基于 std::deque，内存不连续，频繁 push/pop 有分配开销；但安全、无需手动管理。手写固定大小数组栈（如 std::array<:pair>, 64>）仅适合已知最大深度场景（如 2^20 元素最多需约 20 层栈），且必须加溢出检查。

若确定输入规模上限（如游戏引擎中排序顶点索引，最大 65536），可用静态栈避免动态分配
否则坚持 std::stack，但用 std::stack<:pair>, std::vector<:pair>>> 替代默认 deque，提升缓存友好性
永远不要用 malloc + free 手写栈——C++ 中无 RAII 保障，异常安全难保证

非递归快排真正难的不是“怎么写栈”，而是分区函数的边界细节（比如 l 和 r 是否闭区间）、压栈顺序与递归语义的一致性，以及小数组优化的插入时机——这三个地方写错一个，结果就可能错位或变慢。