c++ - 具有 O(N log N) 读取和 O(N) 写入的整数的外部排序

Question

我对算法感兴趣，我应该使用它来满足对ints进行外部排序的O(N log N)读写O(N)要求

Answer 1

如果您正在寻找一种用于这种排序的算法（其中数据不能一次全部放入核心），我的解决方案来自“革命”的最早时期，当时高端机器的内存比大多数机器少现代计算器。

我还没有计算出 big-O 属性，但我认为这将是 O(n) 读取、O(n log n) 排序阶段（取决于选择的排序方法）和 O(n) 写入。

假设您的数据集有 100 万个元素，而您一次只能在内存中容纳 100,000 个元素。这是我要做的：

• 读入前 100,000 个，对它们进行排序，然后将排序后的列表写回。
• 对每组 100,000 人执行此操作。
• 对 10 个组运行合并操作。

换句话说，一旦您的 10 个组在组内排序，请从每个组中获取第一个条目。

然后将这 10 个中的最低值（整百万中的最低值）写入输出文件，并从该组中读取下一个。

然后继续选择 10 个中最低的一个，写出来并从同一组中替换它。这样，最终输出是一百万个条目的整个排序列表。

Answer 2

查看外部合并排序算法。

Answer 3

试试这个页面：排序算法。除了展示几种算法的漂亮动画外，它还解释了它们的工作原理和复杂性。