了解一下什么是外部排序算法

以前我们学习的排序算法，比如冒泡排序、插入排序、快速排序等都是属于内部排序，即所有排序 *** 作都是在内存中完成。然而如果需要排序的文件比整个内存还大时，这时就无法将文件一次性放到内存中，需要借助外部存储来进行排序，这就是外部排序。型凳

外部孝侍排序有两个步骤，分别是 分 与 合 ：

上面的这个步骤其实就是3路平衡归并。因此，对于实际的场景中，对于 k-路平衡归并中的 k 值得选择，增加 k 可以减少归并的次数，从而减少外存读写的次数。但 k 的值也不是越大越好，k越大，在内存中选择最小值的时候也会更加花费时间。一般情况下，对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为 。

从公式中可以看出，要想提高算法效率，可以从两个角度实现：

但其实这两个角度是有矛盾之处的，实际场景中需要就综合考虑，平衡这两者了卜慎旅。

一般来说外排序分为两个步骤：预处理和合并排序。首先，根据可用内存的大小，将外存上含有n个纪录的文件分成若干长度为嫌逗t的子文件（或段）；其培模次，利用内部排序的方法，对每个子文件的t个纪录进行内部排序。这些经过排序的子文件（段）通常称为顺串(run)，顺串生成后即将其写入外存。这样在外存上就得到了m个顺串（m=[n/t]）。最后，对这些顺串进行归并，使顺串配者缓的长度逐渐增大，直到所有的待排序的几率成为一个顺串为止。

你好，外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部带皮碰存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法蠢谈是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子握陪文件进行多路归并排序。

---