为什么我的快排在处理大的逆序数组时会崩溃？

Question

我正在学习C语言并尝试使用递归快速排序算法。在输入规模较小的情况下，它按预期工作；对于随机生成的数组，它在所有测试规模（最高达100,000）上都没有问题。但是，对于降序数组，在某个数组大小（32,506）处程序崩溃了（Windows给我一个消息说程序已停止工作）。我的代码中是否存在任何错误（例如错误的内存分配-我不确定是否正确），或者C语言是否有递归调用的限制，还是其他方面出现了问题？

编辑： 我知道我的快速排序实现比较简单，并且在这种类型的输入情况下表现很差，但我没有预料到它会崩溃。

我正在使用GCC和MinGW在Windows 10的命令提示符上运行。我不确定发生了什么，因为除了Windows告诉我程序已停止工作之外，我并没有得到任何具体的错误消息。

#include <stdio.h>
#include <stdlib.h>

int partition(int *a, int lo, int hi) {
    int i = lo; int j = hi+1; int v,t;
    v = a[lo]; //partition element
    while (1) {
        while (a[++i] < v) {if (i == hi) break;}
        while (v < a[--j]) {if (j == lo) break;}
        if (i >= j) break;
        t = a[j]; a[j] = a[i]; a[i]= t; //swap
    }
    t = a[lo]; a[lo] = a[j]; a[j]= t;//swap
    return j;
}

void quicksort(int a[], int lo, int hi) {
    int j;
    if (hi <= lo) return;
    j = partition(a, lo, hi);
    quicksort(a, lo, j-1);
    quicksort(a, j+1, hi);
}

int main()  {
    int len;
    for (len = 32000;len < 40000;len+=100) {
        printf("New Arr with len = %d\n",len);
        int *arr;
        arr = (int*) calloc(len,sizeof(int));
        int j;
        //create descending Array
        for (j = 0; j < len; ++j) {
            arr[j] = len-j;
        }
        printf("start sorting\n");
        quicksort(arr,0,len-1);
        free(arr);
    }
}

- grebos

---

你使用的是哪个编译器？当程序停止时，错误是否提到堆栈溢出？我之所以问是因为递归程序常见问题是堆栈溢出。 - fvu

calloc 可能会失败。 - William Pursell

这可能会有所帮助 http://softwareengineering.stackexchange.com/questions/257002/what-makes-for-a-bad-case-for-quick-sort - fvu

一个降序数组是“升序”快速排序的最坏输入，特别是当第一个元素作为枢轴时；这种情况下会出现二次复杂度，并且你很可能会递归得太深。你需要使用不同的枢轴选择方法。 - molbdnilo

如果@molbdnilo确实正确，递归深度是问题所在（这非常有可能），那么改变枢轴选择的替代方法是切换到半递归算法。也就是说，不要递归地对两个子分区进行排序，而是递归地对较小的一个进行排序，但是只需循环回来对较大的一个进行排序。这仍然会在不利情况下具有二次运行时间，但在所有情况下都具有对数递归深度和开销。 - John Bollinger

Answer 1

对我来说，你的代码在更大的情况下失败了（约370,000个元素）。你很可能遇到了平台限制（可能是由于堆栈溢出导致递归深度限制）。当然，没有确切的错误信息很难确定。

你的输入集很可能是你实现的病态案例 - 参见快速排序中什么情况会导致糟糕的情况？ 通过更好地选择枢轴，可以减少递归深度 - 一种常见的技术是取第一个、中间和最后一个元素的中位数。像这样：

int v0 = a[lo], v1 = a[(lo+hi+1)/2], v2 = a[hi];
/* pivot: median of v0,v1,v2 */
int v = v0 < v1 ? v1 < v2 ? v1 : v0 < v2 ? v2 : v0 : v0 < v2 ? v0 : v1 < v2 ? v2 : v1;

您也可以通过仅对较小的分区进行递归并使用迭代处理较大的分区来减少递归深度。您可能能够让编译器的尾调用消除器将递归转换为迭代，但如果无法实现，您需要自己编写代码。具体做法类似于：

void quicksort(int a[], int lo, int hi) {
    while (lo < hi) {
        int j = partition(a, lo, hi);
        if (j - lo < hi -j) {
            quicksort(a, lo, j-1);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j-1;
        }
    }
}

通过上述更改，我可以对十亿个元素的数组进行排序而不会崩溃（我必须进行一些性能改进 - 请参见下文 - 即使如此，也需要 17 秒）。

当你发现一个子数组已经排序时，你可能还想尽早返回。我会把这留作练习。

---

附注：您的 main() 中有一些问题:

您没有测试 calloc() 的结果-而且您可能应该使用 malloc()，因为无论如何您都将写入每个元素:

int *arr = malloc(len * sizeof *arr);
if (!arr) return fprintf(stderr, "allocation failed\n"), EXIT_FAILURE;

---

完整列表

这是我最终得到的代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int partition(int *a, int i, int j) {
    int v0 = a[i], v1 = a[(i+j+1)/2], v2 = a[j];
    /* pivot: median of v0,v1,v2 */
    int v = v0 < v1 ? v1 < v2 ? v1 : v0 < v2 ? v2 : v0 : v0 < v2 ? v0 : v1 < v2 ? v2 : v1;
    while (i < j) {
        while (a[i] < v && ++i < j)
            ;
        while (v < a[j] && i < --j)
            ;
        int t = a[j]; a[j] = a[i]; a[i]= t; //swap
    }
    /* i == j; that's where the pivot belongs */
    a[i] = v;
    return j;
}

void quicksort(int a[], int lo, int hi) {
    while (lo < hi) {
        int j = partition(a, lo, hi);
        if (j - lo < hi -j) {
            quicksort(a, lo, j-1);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j-1;
        }
    }
}

int main()  {
    int len = INT_MAX/2+1;
    printf("New Arr with len = %d\n",len);
    int *arr = malloc(len * sizeof *arr);
    if (!arr) return fprintf(stderr, "allocation failed\n"), EXIT_FAILURE;

    /* populate pessimal array */
    for (int j = 0; j < len; ++j) {
        arr[j] = len-j;
    }

    printf("start sorting\n");
    quicksort(arr, 0, len-1);

    /* test - is it sorted? */
    for (int i = 0;  i+1 < len;  ++i)
        if (arr[i] >= arr[i+1])
            return fprintf(stderr, "not sorted\n"), EXIT_FAILURE;
    free(arr);
}

- Toby Speight

---

我认为问题在于递归深度（这可以解释为什么它在你的系统上和在我的系统上不会在同一点崩溃），因为即使只使用您的快速排序（quicksort()）函数实现，它也没有崩溃（测试大小为200,000）。 - grebos

Answer 2

递归深度太大，无法在堆栈中存储。 每个级别都必须存储int j = partition(..)。 有声明性技术可以最小化递归堆栈使用。 例如将结果作为参数传递。但这种情况比我能举的例子要复杂得多。

- renonsz