algorithm - 部分排序算法

Question

假设我有 5000 万个特征，每个特征都来自磁盘。

在我的程序开始时，我处理每个功能，并根据某些条件对某些功能进行一些修改。

在我的程序中，我正在从磁盘读取一个特征，对其进行处理，然后将其写回，因为我没有足够的内存来一次打开所有 5000 万个特征。

现在假设我要对这 5000 万个特征进行排序，是否有最佳算法可以做到这一点，因为我无法同时加载所有特征？

比如部分排序算法之类的？

Answer 1

一般来说，您要查找的算法类称为 external sorting .也许这种排序算法最广为人知的例子是Merge sort。 .

这个算法(外部版本)的想法是将数据分成可以在内存中就地排序的部分(比如 10 万)并独立地对每个 block 进行排序(使用一些标准算法，例如 Quick sort ).然后你取出 block 并合并它们(因此你将两个 100k block 合并为一个 200k block )这可以通过将两个 block 中的元素读入缓冲区来完成(因为 block 已经排序)。最后，您将两个较小的 block 合并为一个 block ，该 block 将以正确的顺序包含所有元素。