我对算法感兴趣,我应该使用它来满足对int
s进行外部排序的O(N log N)
读写O(N)
要求
问问题
1854 次
3 回答
4
如果您正在寻找一种用于这种排序的算法(其中数据不能一次全部放入核心),我的解决方案来自“革命”的最早时期,当时高端机器的内存比大多数机器少现代计算器。
我还没有计算出 big-O 属性,但我认为这将是 O(n) 读取、O(n log n) 排序阶段(取决于选择的排序方法)和 O(n) 写入。
假设您的数据集有 100 万个元素,而您一次只能在内存中容纳 100,000 个元素。这是我要做的:
- 读入前 100,000 个,对它们进行排序,然后将排序后的列表写回。
- 对每组 100,000 人执行此操作。
- 对 10 个组运行合并操作。
换句话说,一旦您的 10 个组在组内排序,请从每个组中获取第一个条目。
然后将这 10 个中的最低值(整百万中的最低值)写入输出文件,并从该组中读取下一个。
然后继续选择 10 个中最低的一个,写出来并从同一组中替换它。这样,最终输出是一百万个条目的整个排序列表。
于 2009-08-08T13:02:06.817 回答
3
查看外部合并排序算法。
于 2009-08-08T12:57:40.233 回答
2
试试这个页面:排序算法。除了展示几种算法的漂亮动画外,它还解释了它们的工作原理和复杂性。
于 2009-08-08T12:41:16.723 回答