主要目的是减少访存次数
外排序基本过程：
- 置换选择排序（把外存文件初始化为尽可能长的顺串集）
- 归并排序（把顺串合并排序）
置换选择算法
- 用一个堆来维护
- 主要步骤：每个顺串至少长为M，平均长度2M
- 读取M个记录到堆中，建立最小堆，设置堆尾标志LAST
- 把根节点输出
- 读入下一条记录，如果比刚刚输出的根节点小，根节点用LAST位置的记录代替，新纪录放进LAST位置，LAST减1；否则把记录放到根节点重新排列堆。重复。
- LAST<0的时候前面输出的就是一个顺串，然后重复。
归并排序
- 访存次数与归并趟数有关
- 有m个初始顺串，每次对k个顺串归并，归并趟数为$log_k^m$
- 可用huffman树安排归并顺序优化
多路归并树
- 外部结点L[i]与内部父节点B[p]关系：
-
$p=\begin{cases} \frac{i+offset}{2}& i\leq LowExt\\ \frac{i-LowExt+n-1}{2}& i＞LowExt \end{cases}$
-
-
offset是最底层外部结点之上的所有结点数目
- LowExt是最底层外部节点个数
- 原始方法
- 复杂度：产生一个大小为n的顺串的总时间是$O(k*n)$
- 赢者树
- 每棵子树的树根记录左右结点的赢家
- 每次L[i]改变，沿着到根节点的路径和兄弟结点的值进行比较
- 败者树
- 记录每次的败者，最终胜者放在B[0]
- 每次L[i]改变，沿着到根节点的路径和父节点进行比较
- 简化重构过程，其他没变
- 复杂度：$O(k+nlog^k)$