我想long long在 C 中按四百万的顺序排序。通常我只是malloc()一个缓冲区用作数组并调用qsort()，但四百万 * 8 字节是一大块连续内存。
最简单的方法是什么？为此，我将轻松程度置于纯粹的速度之上。我不想使用任何库，结果需要在 Windows 和 Linux 下的普通上网本上运行。
问问题
3543 次
3 回答
11
只需分配一个缓冲区并调用qsort. 如今，即使在普通的上网本上，32MB 也不是很大。
如果您真的必须拆分它：对较小的块进行排序，将它们写入文件，然后合并它们（合并对每个被合并的事物进行一次线性传递）。但是，真的，不要。就排序吧。
（在 Knuth 的第 2 卷中对排序和合并方法进行了很好的讨论，它被称为“外部排序”。当 Knuth 写那篇文章时，外部数据本来应该在磁带上，但原理不是很清楚与磁盘不同：您仍然希望 I/O 尽可能连续。SSD 的权衡有点不同。）
于 2011-04-07T21:47:53.967 回答
1
32MB？那不是太大....快速排序应该可以解决问题。
于 2011-04-07T21:49:22.520 回答
0
如果可能，您最好的选择是防止数据无序。就像已经提到的那样，您最好将数据从磁盘（或网络或任何来源）直接读取到自组织容器（一棵树，也许std::set可以）中。
这样一来，您就不必对大量内容进行分类，也不必担心内存管理。std::vector(initialcapacity)如果您知道容器所需的容量，您可能会通过使用或预先调用来挤出额外的性能vector::reserve。
然后最好建议您使用std::make_heap来堆化任何现有元素，然后使用逐个元素添加元素push_heap（另请参见参考资料pop_heap）。这本质上是与自排序集相同的范式，但
- 重复没问题
- 存储被“优化”为平面数组（非常适合共享内存映射或内存映射文件）
（哦，小细节，注意sort_heap在堆上最多进行 N log N 比较，其中 N 是元素的数量）
如果您认为这是一种有趣的方法，请告诉我。我真的需要更多关于用例的信息
于 2011-04-07T21:54:32.793 回答