C++快速排序处理超32000长度有序数组触发0xC00000FD错误

API 探路者

2026-8-29

问题诊断

错误码-1073741571 (0xC00000FD)对应Windows平台的栈溢出异常，问题和动态分配的数组无关，完全是快速排序的递归逻辑触发的。

你当前实现的partition函数固定选择待排序区间的第一个元素作为基准值，当传入数组为完全升序或完全降序时，每次划分都会得到极度失衡的两个区间：一个区间长度为0，另一个长度为当前区间长度减1。这种场景下递归调用的深度等于数组总长度——对于长度32000的数组，递归深度会达到32000层。Windows默认给线程分配的栈空间通常为1MB，每层递归需要存储传入参数、返回地址，累计下来很快就会耗尽栈空间触发崩溃。
数组长度较小时递归深度达不到栈空间阈值，无序数组时划分相对均衡，递归深度仅为log₂n量级（32000长度的数组递归深度仅15层左右），因此不会触发异常。

另外你贴的代码里quick_sort函数定义后缺失左大括号{，属于笔误，编译阶段就会报错，记得补上。

修复方法

优化基准值选择逻辑，避免最坏划分场景
放弃固定选首元素为基准值的策略，改用三数取中（取区间首、中、尾三个位置的元素中位数）或者随机选点的方式确定基准值，就能从根源上避免有序数组下的O(n)深度递归。随机选点的改法非常简单，只需要在partition函数取pivot的逻辑前加两行代码：
```
// 插入到 int pivot = arr[first]; 之前
int randIdx = first + rand() % (last - first + 1);
swap(arr[first], arr[randIdx]);
```

优化递归逻辑，降低栈占用
递归时优先处理长度更短的子区间，较长的子区间通过循环迭代处理，能进一步把最坏场景下的栈深度压缩到log₂n量级，修改后的quick_sort参考实现：

void quick_sort( int* arr, int first, int last, int &compCount, int &moveCount, int pivotIndex) {
    // 原有的if判断替换为循环
    while( first < last ) {
        partition( arr, first, last, pivotIndex, compCount, moveCount );
        // 优先递归处理长度更小的区间，减少栈帧占用
        if (pivotIndex - first < last - pivotIndex) {
            quick_sort(arr, first, pivotIndex - 1, compCount, moveCount, first);
            first = pivotIndex + 1;
        } else {
            quick_sort(arr, pivotIndex + 1, last, compCount, moveCount, pivotIndex + 1);
            last = pivotIndex - 1;
        }
    }
}

极端场景下可以直接实现非递归版快排，用手动维护的栈结构存储待排序的区间下标，完全不占用程序调用栈空间，从根本上杜绝栈溢出风险。

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