C语言 超过最大递归深度.堆栈溢出异常

Question

我目前正在编写一个算法来分析排序算法。我有很多输入，从1000个数到1000000个数。目前我有一些问题与快速排序功能。由于我输入了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

如果在递归过程中出现堆栈溢出，这意味着递归被破坏了。通常应该避免递归，因为它有创建缓慢和危险算法的巨大潜力。如果你是一个初级程序员，那么我强烈建议你忘记你曾经听说过递归，不要再读这里了。

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

如果它不能执行尾部调用优化，则意味着每次执行递归时实际上都调用了一个函数。这意味着堆栈会不断堆积，你也会得到函数调用的开销。这是不必要的缓慢和不可接受的危险。因此，您编写的所有递归函数都必须针对目标进行反汇编，以确保代码没有出现混乱。

因为这段代码似乎取自这个网站https://www.geeksforgeeks.org/iterative-quick-sort/，他们已经用代码为您描述了大部分这些问题。他们有一个"快速排序"函数，这是一个更好的实现。

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

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分区方案存在大量重复值的问题。Hoare分区方案没有这个问题(事实上，更多的副本导致更少的时间)。

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;
}
}
}