c - 超过 50 万个元素的快速排序崩溃

Question

我的非常简单的算法 - C 中的快速排序有问题。它非常有效(随机化大约 0.1 秒并检查列表是否已排序)但是当我想要对超过 500k 的元素进行排序时它会崩溃。不幸的是，我需要对它们进行更多排序，因为我需要在最后写一些总结:(

这是我的代码，也许有人会看到一个愚蠢的错误。提前致谢!

int quick (int a[],int begin,int end)
{
    int i = begin, j = end, w, q, pivot, k;
    q=begin+end;
    q=q/2;
    pivot=a[q];
    while (1)
    {
        while (a[j] > pivot && j>=0)
        j=j-1;
        while (a[i] < pivot && i<j)
        i=i+1;
        if (i < j)
        {
            k = a[i];
            a[i] = a[j];
            a[j] = k;
            i++;
            j--;
        }
        else
        return j;
    }
}

void quicks (int a[], int begin, int end)
{
    int x;
    if (end>begin)
    {
        x=quick(a,begin,end);
        quicks(a,begin,x);
        quicks(a,x+1,end);

    }
}

看来我只需要使用 malloc，它工作正常。非常感谢您的帮助!

Answer 1

您正在遭受 RAM 耗尽/翻转的困扰:当您使用 int 数组时，每个数组都需要 4 个字节。您的内存映射是使用 size_t 类型的索引处理的。如果您在 32 位模式下编译(这可能是您的情况)，它可以获得的最大数字是 2147483648 (2^31)。每个 int 有 4 个字节，您只能处理 536870912 个元素 (2^31/4)。

由于系统需要一些 RAM 用于其他目的(例如全局变量)，您只能使用略多于 500K 的条目。

解决方案:使用 64 位编译器，应该没问题。

BR