c - 10,000,000 的随机数组排序

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 5 年前。

Improve this question

我必须对数组进行排序，但我有一个问题:

所以，我做了这个:

#define size 10000000

int main() {
int arr[size], i, j;
int aux = 0;
int num;`

srand(time(NULL));

for (i = 0; i < size; i ++)
{
       num = rand() % size + 1;
       arr[i] = num;
}

for(i = 0; i < size; i++)
{

    for (j = 0; j < size-1; j++)
    {
        if (arr[j] > arr[j+1])
        {
            aux = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = aux;
        }
    }
}

for (i = 0; i < size; i++)
{
    printf("%d\n",arr[i]);
}

return 0; }

最有效的方法是什么？快速排序？我应该怎么办？请提前提供帮助。

Answer 1

考虑到输入大小，很少有事情可以说清楚。

使用冒泡排序对 10^7 个输入进行排序时，平均需要 10^14 次比较。现在，在标准机器上几乎可以在 1 秒内完成 10^8 次比较。所以这会花费很长的时间。(冒泡排序是O(n^2))

你必须寻找一些O(nlogn)算法。 (具有最佳的空间和时间复杂度)。也许是快速排序、合并排序或堆排序。

在这个位置最好是进行快速排序。它不会像合并排序或堆排序那样具有空间复杂度。 因此在这种情况下这将是最有效的解决方案。

正如评论中提到的，堆排序也可以在没有额外内存的情况下就地完成，其优点是平均复杂度将nlogn(theta nlogn)，因此在这种情况下，堆排序可能是一个不错的选择。 Lee Daniel Crocker 在评论中提到了这一点。

要像 Eugene 所说的那样摆脱堆栈溢出，您可以将 main 标记为 static 或将数组设置为全局。这将使它不属于堆栈的一部分。正如您所提到的，使用动态内存分配是另一种选择。尝试在 main() 内分配(malloc()) 和 free。

<小时/>

为了进一步澄清，由于调用堆栈中的堆栈帧，快速排序中最坏情况的空间复杂度为 nlogn 量级。对于堆排序来说，这不是必需的。