快速排序算法抛出堆栈转储错误的 C++ 运行时错误

Question

当我尝试 size = 20000 时代码工作正常，当我尝试 size = 50000 时它似乎失败并给出以下错误:

2 [] cppapplication_4 7628 cygwin_exception::open_stackdumpfile: Dumping stack trace to cppapplication_4.exe.stackdump

long long compares; // for counting compares
long long swaps; // for counting swaps
bool counted_less(int n1, int n2) {
    ++compares;
    return n1 < n2;
}

void counted_swap(int& n1, int& n2) {
    ++swaps;
    int t = n1;
    n1 = n2;
    n2 = t;
}

int* partition(int* start, int* stop) {
    int noUse=99;
    int* pivot = (stop - 1); // you can randomly pick one as the pivot
    int* i = start;
    int* j = stop - 1;
    for (;;) {
        while (*i < *pivot && i < stop)
        {
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
            ++i;
        }
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
        // skip "low" on left side
        while (*j >= *pivot && j > start) {
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
            --j;
        }
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);

        // skip "high" on right side
        if (i >= j) 
        {
            counted_less(noUse,noUse);
            break;
        }
        else
        {
            counted_less(noUse,noUse);
        }
        swap(*i, *j);
        counted_swap(noUse,noUse);// swap out-of-place items
    }
    swap(*(stop - 1), *i); 
    counted_swap(noUse,noUse);// swap pivot to the final place i
    return i;

}
void quickSort(int* start, int* stop) {
    int noUse=99;
    if (start>= stop){
        counted_less(noUse,noUse);
        return;
    }
    else
    {
        counted_less(noUse,noUse);
    }
    int* pivot = partition(start,stop);
    quickSort(start, pivot);
    quickSort((pivot +1), stop);
}

int main()
{
    int size = 20000;
    int* data = new int[size];
     for (int i = 0; i < size; ++i) data[i] = i;
     quickSort(data, data + size);
}

我认为该错误意味着我正在超出数据类型存储限制，我认为问题出在我使用 int 上，所以我将所有 int 更改为 long long，但仍然没有解决问题。根据代码的逻辑，我不认为我们正在改变数组的大小。所以我不确定是什么导致了错误。

Answer 1

您可能遇到了堆栈溢出。这就是递归不好的原因。

作为临时解决方法，尝试通过链接 --stack 16777216 来增加堆栈大小:

$ g++ -Wl,--stack,16777216  . . .

== 编辑 ==

此外，您在 (end - 1) 处选择的枢轴也不好。尝试将枢轴设置在中间。

    int* pivot = (stop - start)/sizeof(int*)/2 + start;