超过最大递归深度。堆栈溢出异常

Question

我目前正在编写一个算法来分析排序算法。我有很多输入，从 1000 个数字到 1 000 000 个输入。目前我在使用快速排序功能时遇到了一些问题。因为我输入了 1 000 000 个相似的数字（1-10 之间的数字），所以这段代码会抛出一个错误 (0xC00000FD)（似乎是堆栈溢出异常）。现在，我不知道如何减少递归调用的次数或如何增加堆栈以便可以进行多次递归调用。我附上了快速排序的代码。

void swap(int *xp, int *yp)
    {
        int temp = *xp;
        *xp = *yp;
        *yp = temp;
    }

int partition (int arr[], int low, int high)
{
    int pivot = arr[(low+high)/2];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
void quicksort(int A[], int l, int h)
{
    if (l < h) {
        int p = partition(A, l, h);
        quicksort(A, l, p - 1);
        quicksort(A, p + 1, h);
    }
}

Answer 1

如果你在递归过程中遇到堆栈溢出，这意味着你的递归被破坏了。通常应该避免递归，因为它有可能创建缓慢而危险的算法。如果您是初级程序员，那么我强烈建议您忘记您曾经听说过递归并停止阅读这里。

唯一可以合理允许的情况是递归调用放在函数末尾时，即所谓的“尾调用递归”。这几乎是编译器实际可以优化并用内联循环替换的唯一递归形式。

如果不能进行tail-call优化，那么说明你每次递归实际上都调用了一个函数。这意味着堆栈不断堆积，并且您还会获得函数调用开销。这既不必要地缓慢又危险得令人无法接受。因此，您编写的所有递归函数都必须针对目标进行反汇编，以确保代码没有失控。

由于此代码似乎取自此站点 https://www.geeksforgeeks.org/iterative-quick-sort/，他们已经在此处为您描述了代码中的大部分问题。他们在底部有一个“quickSortIterative”函数，这是一个更好的实现。

我的看法是，本教程的目的是向您展示一些损坏的代码（您问题中的代码），然后演示如何通过摆脱递归来正确编写它。

Answer 2

可以通过只在较小的分区上递归来避免堆栈溢出：

void quicksort(int A[], int l, int h)
{
    while (l < h) {
        int p = partition(A, l, h);
        if((p - l) <= (h - p)){
            quicksort(A, l, p - 1);
            l = p + 1;
        } else {
            quicksort(A, p + 1, h);
            h = p - 1;
        }
    }
}

然而，最坏情况下的时间复杂度仍然是O(n^2)，问题代码中使用的Lomuto分区方案存在大量重复值的问题。霍尔分区方案没有这个问题（事实上，更多的重复导致更少的时间）。

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

快速排序中具有分区逻辑的示例代码：

void quicksort(int a[], int lo, int hi)
{
    int p;
    int i, j;
    while (lo < hi){
        p = a[lo + (hi - lo) / 2];
        i = lo - 1;
        j = hi + 1;
        while (1){
            while (a[++i] < p);
            while (a[--j] > p);
            if (i >= j)
                break;
            swap(a+i, a+j);
        }
        if(j - lo < hi - j){
            quicksort(a, lo, j);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j;
        }
    }
}

超过最大递归深度。堆栈溢出异常

Maximum recursion depth exceeded. Stack overflow exception

c

stack-overflow

recursion

quicksort

bigdata