C++ 在快速排序函数中获取 StackOverflow 错误

Question

当我尝试使用快速排序对大型数组进行排序时出现计算器溢出错误，并且该数组按降序排列。我想使用以下代码按升序对其进行排序:

int partition_lastElementPivot(int * arr, int lo, int hi)
{
    int x = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[hi];
    arr[hi] = arr[i + 1];
    arr[i + 1] = temp;

    return i + 1;
}

void quicksortLastElementPivot(int*arr, int lo, int hi)
{
    if (lo<hi)
    {
        int mid = partition_lastElementPivot(arr, lo, hi);
        quicksortLastElementPivot(arr, lo, mid - 1);
        quicksortLastElementPivot(arr, mid + 1, hi);
    }
}

当我随机生成一个任意大小的数组(假设大小为 5000)时，此代码工作正常。但是当我生成一个大小为 5000 的数组并按降序排序，然后尝试使用此代码进行排序时，出现计算器错误。 C++ 是否限制堆栈可用的内存以及为什么会这样。

int arr[5000];
int count = 5001;
for(int i=0; i<5000; i++)
{
    arr[i] = count;
    count--;

}
quicksortLastElementPivot(arr, 0, 4999)

谢谢

Answer 1

正如您在此处发现的那样，快速排序在最坏情况下的性能确实非常糟糕。它在 5000 的堆栈深度调用自身。This Wikipedia article对该主题进行了很好的讨论。特别是，它提到了 tail recursion作为堆栈溢出问题的解决方案。

简而言之，这意味着不是最后一次调用 quicksortLastElementPivot 后立即返回，而是循环回到函数的开头。这具有相同的效果，但尾递归不会增加堆栈大小。为此，您必须确保首先使用传统递归对两个分区中较小的分区进行排序，然后使用尾递归对较大的分区进行排序。像这样的东西(未经测试!):

void quicksortLastElementPivot(int*arr, int lo, int hi)
{
TailRecurse:
    if (lo<hi)
    {
        int mid = partition_lastElementPivot(arr, lo, hi);
        if (mid < (lo + hi) / 2)
            { // First partition is smaller
            quicksortLastElementPivot(arr, lo, mid - 1); // Sort first partition
            lo = mid + 1; goto TailRecurse;              // Sort second partition
            }
        else
            { // Second partition is smaller
            quicksortLastElementPivot(arr, mid + 1, hi); // Sort second partition
            hi = mid - 1; goto TailRecurse;              // Sort first partition
            }
    }
}