算法—外部排序&多路归并
发布网友
发布时间：2024-10-19 14:43
共1个回答
热心网友
时间：2024-11-21 17:39
我们知道算法中有一种叫做分治思想，一个大问题我们可以采取分而治之，各个突破，当子问题解决了，大问题也就解决了。
当我们要对存储的大量文件进行排序时，可以把数据比较均匀放在k个小文件中，分别对k个小文件进行排序，然后再使用多路归并的方式排序到一个文件中。
多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。
算法
解剖
可以看到这个算法的关键点在于，如何将有效的k个数据中选出最大或者最小的那个值x。我们假设数据总量是n个。
