一、外部排序算法

1. 路归并

假设各片段均已采用内排序算法进行排序，外排序归并最简单使用的是2路归并，每次读入2路有序片段的前m个元素进行归并。若输出缓冲区已满，则将已归并好的元素写入文件；若其中一路m个元素归并完成，读入该路剩下的前m个元素。重复交替执行，直到所有元素都归并完成为止，则当前文件的元素为有序的。

由于2路归并需要所有元素反复进行比较，比较的次数过多，导致归并的效率很低，因此有人提出了改进算法，采用多路归并来提高效率，即k路归并。

k路归并一般采用堆进行排序，利用完全二叉树的性质，可以很快更新，保持堆的性质。然而堆操作次数还是不够精简，因此有人进一步提出了胜者树和败者树的数据结构来进行多路归并。

胜者树与败者树的叶子节点记录的都是数据，胜者树中间节点记录的是胜者对应的标号，而败者树中间节点记录的是败者对应的标号。同时败者树需要一个额外节点来记录最终胜者。由于败者树的更新只需将子节点与父节点比较，而胜者树的更新需要与父节点和子节点比较，因此在实际应用中采用败者树更好。

2. 败者树

败者树，顾名思义，即记录胜败者的树形结构。实际上，这种数据结构的最初灵感来源就是来自于比赛中记录胜败得分的。只不过在败者树中，父节点记录的是败者节点，而胜者节点继续上浮比较。

3. 多路平衡归并算法

初始化操作

b[0..k]，其中0~k-1为k个叶节点，存放k路归并片段的首地址，k为虚拟记录，该关键字取可能的最小值minkey

ls[0..k-1]，其中1~k-1存放不含叶节点的败者树的败者编号，0存放最后胜出的编号。

处理步骤

建败者树ls[0..k-1]

重复下列操作直至k路归并完毕

将b[ls[0]]写至输出归并段

补充记录（某归并段变空时，补∞），调整败者树。

延伸阅读：

二、外部排序算法阶段

外部排序算法由两个阶段构成，预处理和合并排序。预处理产生有序的顺串： 按照内存大小，将外存上含有 n 个纪录的大文件分成若干长度为 t 的子文件（t 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对子文件的 t 个纪录进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间；这样在外存上就得到了m个顺串（m= [n/t]）。. 合并序列： 对得到的顺段进行合并，直至得到整个有序的文件为止。

以上就是关于外部排序算法的内容希望对大家有帮助。

上一篇

RAM和ROM的区别?

下一篇

什么是云数据库?