代码之家  ›  专栏  ›  技术社区  ›  M-J

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

  •  -1
  • M-J  · 技术社区  · 6 年前

    我已经编写了一个矢量快速排序算法的实现,它在中间有一个枢轴时运行良好,但令我惊讶的是,当我将枢轴选择部分更改为随机执行时,程序会出现堆栈溢出错误!虽然据说所选的枢轴对算法没有影响,对我来说也是有意义的,但我不知道是什么导致了我的代码中出现这个问题:

    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有很多递归),它成功地结束了!不会出现同样的错误!但是如果我一起运行整个程序,就会出现堆栈溢出错误!在这里的其他地方,我读到它与“debug”和“release”概要文件有关,所以我将构建配置切换到release,但它也不起作用。

    请帮助,如果你需要完整的代码,我会把它。泰亚。

    1 回复  |  直到 6 年前
        1
  •  2
  •   Albert    6 年前

    你为什么要搬家 arr.size() 而不是 high - low ? 示例:如果选择的索引高于 high ,则分区将不执行任何操作,您将在不减小大小的情况下再次递归调用。如果这种情况经常发生,尤其是对于较小的大小,那么堆栈将溢出。

    要修复,请将该行替换为:

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