部分排序算法

Question

假设我有5000万个功能,每个功能都来自磁盘.

在我的程序开始时,我处理每个功能,并根据某些条件,我应用一些修改.

在我的程序中这一点,我正在从磁盘读取一个功能,处理它并将其写回来,因为我没有足够的内存来同时打开所有5000万个功能.

现在说我要对这5000万个功能进行排序,是否有任何最佳算法可以实现这一点,因为我无法同时加载每个人？

像部分排序算法或类似的东西？

Answer 1

通常,您正在寻找的算法类称为外部排序.也许这种排序算法最广为人知的例子叫做Merge sort.

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