QuickSort随机选择基准时出现栈溢出问题求助

让我来帮你定位问题所在——你的随机基准实现有两个关键错误，正是它们共同导致了栈溢出：

1. 重复初始化随机数生成器导致随机数重复 #

你在每次调用quickSort时都执行srand(time(0))，但time(0)返回的是秒级精度的时间戳。当递归调用快速排序时，短时间内会连续触发大量quickSort调用，这些调用的time(0)返回值完全相同，导致srand每次都把随机数生成器重置到同一个初始状态，后续的rand()会生成完全一样的数值。

这就意味着每次递归选的基准都是同一个元素，快速排序的递归树会退化成单链表结构，递归深度达到O(n)级别。当数组规模稍大时，调用栈就会被撑爆，出现栈溢出错误。

正确的做法是：只在程序启动时调用一次srand(time(0))，比如在main函数的开头，而不是在递归函数内部。

2. 随机基准的范围错误 #

你用rand() % arr.size()来生成基准索引，这会从整个数组的范围内选元素，但当前递归处理的只是[low, high]这个子数组。如果选到了子数组之外的元素，基准值就不在当前待排序的区间内，会破坏快速排序的分区逻辑——导致分区后左右子数组的规模无法有效缩小，甚至可能出现递归无法终止的情况，进一步加剧栈溢出的风险。

正确的随机基准索引应该限制在当前子数组的范围内：

int pivotIndex = low + rand() % (high - low + 1);

修正后的代码 #

// 只在main函数里调用一次这个初始化
void initRandom() {
    srand(time(0));
}

void quickSort(int low, int high, vector<int>& arr) {
    int i = low, j = high;
    // 正确生成当前子数组范围内的随机基准
    int pivotIndex = low + rand() % (high - low + 1);
    int pivot = arr.at(pivotIndex);

    while (i <= j) {
        while (arr.at(i) < pivot) { ++i; }
        while (arr.at(j) > pivot) { --j; }
        if (i <= j) { swapElem(arr, i, j); ++i; --j; }
    }
    if (low < j) quickSort(low, j, arr);
    if (i < high) quickSort(i, high, arr);
    return;
}

关于调试时未发现问题的原因 #

调试时你是单步执行，每次递归调用之间的时间间隔足够长，time(0)会返回不同的数值，rand()能生成不同的随机数，递归树不会退化成单链表，所以栈深度在调试环境的限制内。但程序正常运行时递归调用极快，srand重复初始化导致随机数完全相同，递归深度瞬间达到栈的上限，触发溢出。

内容的提问来源于stack exchange，提问作者M-J