C++快速排序处理百万级数组仍栈溢出，已改用堆存储求解决方案

你已经将数组从栈分配改为堆分配，但仍然遇到栈溢出，核心原因是快速排序的递归调用深度过大——默认的递归实现在最坏情况（如数组已完全有序）下，递归深度可达O(n)，百万级元素会直接耗尽程序的调用栈空间。以下是具体解决方法：

1. 尾递归优化（最小化递归深度） #

修改递归逻辑，每次只对较小的子数组进行递归，较大的子数组用循环代替递归，将递归深度控制在O(logn)级别（对1e6元素来说仅约20层）：

template<typename T>
void quicksortPivotLastTwo(T arr[], int startIndex, int endIndex) {
    while (startIndex < endIndex) {
        int p = partitionPivotLast(arr, startIndex, endIndex);
        
        // 优先递归处理较短的分区，减少递归栈占用
        if (p - startIndex < endIndex - p) {
            quicksortPivotLastTwo(arr, startIndex, p - 1);
            startIndex = p + 1; // 循环处理较长的分区，避免递归
        } else {
            quicksortPivotLastTwo(arr, p + 1, endIndex);
            endIndex = p - 1; // 循环处理较长的分区，避免递归
        }
    }
}

2. 改用迭代实现快速排序 #

用堆上的栈（如std::stack）模拟递归过程，完全避开程序调用栈的限制：

#include <stack>
template<typename T>
void quicksortIterative(T arr[], int n) {
    std::stack<std::pair<int, int>> stk;
    stk.push({0, n});
    
    while (!stk.empty()) {
        auto [start, end] = stk.top();
        stk.pop();
        
        if (start >= end) continue;
        
        int p = partitionPivotLast(arr, start, end);
        
        // 先压入较大的分区，保证后续先处理较小分区（缓存友好，非必须）
        if (p - start > end - p) {
            stk.push({start, p - 1});
            stk.push({p + 1, end});
        } else {
            stk.push({p + 1, end});
            stk.push({start, p - 1});
        }
    }
}

调用时直接替换为quicksortIterative(enMiljon, 999999);即可。

3. 优化分区的Pivot选择（避免最坏情况） #

当前用最后一个元素作为Pivot，在数组有序时会触发最坏递归深度。改用三数取中策略选择Pivot，大幅降低最坏情况出现的概率：

template <typename T>
int partitionPivotLast(T arr[], int startIndex, int endIndex)
{
    // 三数取中：选择start、mid、end中的中间值作为Pivot
    int mid = startIndex + (endIndex - startIndex) / 2;
    // 通过交换将中间值移到end位置，保持原有分区逻辑不变
    if (arr[mid] > arr[endIndex]) swap(arr[mid], arr[endIndex]);
    if (arr[startIndex] > arr[endIndex]) swap(arr[startIndex], arr[endIndex]);
    if (arr[mid] > arr[startIndex]) swap(arr[mid], arr[startIndex]);
    swap(arr[startIndex], arr[endIndex]);
    
    int pivot = arr[endIndex];
    int count = 0;

    for (int i = startIndex; i < endIndex; i++) {
        if (arr[i] <= pivot) {
            count++;
        }
    }

    int indexP = startIndex + count;
    swap(arr[indexP], arr[endIndex]);

    int i = startIndex;
    int j = endIndex;

    while (i < indexP && j > indexP) {
        while (arr[i] <= pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i < indexP && j > indexP) {
            swap(arr[i++], arr[j--]);
        }
    }
    return indexP;
}

建议组合方案 #

优先使用尾递归优化+三数取中，既保留递归代码的简洁性，又能将递归深度控制在安全范围，同时避免最坏情况的出现。

内容的提问来源于stack exchange，提问作者Tyler Durden