快速排序中奇怪的堆栈溢出

Question

我已经用向量编写了一个快速排序算法的实现，它在中间有一个枢轴的情况下工作正常，但令我惊讶的是，当我将枢轴选择部分更改为随机完成时，程序给出了堆栈溢出错误！虽然据说选择的枢轴对算法没有影响，这对我来说也很有意义，但我不知道是什么导致了我的代码中的这个问题：

void quickSort(int low, int high, vector<int>& arr) {
int i = low, j = high;

//If I choose the pivot from the middle, works fine:
int pivot = arr[(low + high) / 2];

//But the next three lines won't work (instead of the line above):
//srand(time(0));
//int pivotIndex = rand() % arr.size();
//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;
}

我正在使用 VS15 并调试我的程序以找到无限递归或其他问题（尽管我花了好几年:) b/c 有很多递归）并且它成功结束了！没有给出同样的错误！但是如果我把整个程序运行放在一起，就会出现栈溢出错误！在 SO 的其他地方，我读到它与 "debug" 和 "release" 配置文件有关，所以我将构建配置切换为发布，但它也没有用。

请帮忙，如果你需要完整的代码，我会把它放上去。 TYIA.

Answer 1

为什么您使用 arr.size() 而不是 high - low 进行改装？示例：如果您选择一个高于 high 的索引，那么该分区将不执行任何操作，您将在不减小大小的情况下再次递归调用。如果这种情况经常发生（很可能会发生），尤其是对于较小的尺寸，那么堆栈就会溢出。

要修复，请将该行替换为：

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

快速排序中奇怪的堆栈溢出

weird stack overflow in Quicksort

c++

stack-overflow

quicksort