如何在C中对非常大的数组进行排序
我想在C中排序四百万long long s。通常我只是malloc()一个缓冲区用作数组并调用qsort()但是四百万* 8字节是一大块连续内存。
最简单的方法是什么？ 为此，我对速度感到轻松。 我不想使用任何库，结果将需要在Windows和Linux下的适度上网本上运行。
只需分配一个缓冲区并调用qsort 。 即使在适度的上网本上，如今32MB还不是很大。
如果你真的必须拆分它：对较小的块进行排序，将它们写入文件，然后合并它们（合并对每个被合并的东西进行一次线性传递）。 但是，真的，不要。 只是排序吧。
（关于Knuth第2卷中的排序和合并方法有一个很好的讨论，它被称为“外部排序”。当Knuth写这篇文章时，外部数据会出现在磁带上，但原理并不是很好不同的光盘：你仍然希望你的I / O尽可能顺序。与SSD的权衡有点不同。）
32 MB？ 这不是太大……快速排序应该做的伎俩。
您最好的选择是尽可能防止数据无序。 就像它已经提到的那样，你最好将数据从磁盘（或网络或任何源）直接读入一个自组织容器（一棵树，也许std::set会这样做）。
这样，您将永远不必排序，或者不得不担心内存管理。 如果您知道容器所需的容量，则可以通过使用std::vector(initialcapacity)或先调用vector::reserve来挤出额外的性能。
然后，建议您最好使用std::make_heap来堆积任何现有元素，然后使用push_heap逐个元素地添加元素（另请参阅pop_heap ）。 这基本上与自我排序集相同，但是
- 重复是好的
- 存储被“优化”为平面数组（适用于例如共享内存映射或内存映射文件 ）
（哦，小细节，请注意堆上的sort_heap最多需要N log N比较，其中N是元素数）
如果您认为这是一种有趣的方法，请告诉我。 我真的需要关于用例的更多信息