【9.4】外排序

磁盘文件的排序:

• 对外存设备上(文件)的排序技术
• 通常由两个相对独立的阶段组成:
• 文件形成尽可能长的初始顺串(run )
• 处理顺串，最后形成对整个数据文件的 排列文件

一、置换选择排序

置换选择示例：

置换选择算法的实现：

置换选择算法的效果：

• 置换选择排序算法得到的顺串长度并不相等。 如果堆的大小是 M
• 一个顺串的最小长度就是 M 个记录
• 至少原来在堆中的那些记录将成为顺串的一 部分
• 最好的情况下，例如输入为正序，有可能一次 就把整个文件生成为一个顺串
• 平均情况下，置换选择排序算法可以形成长度 为 2M 的顺串

扫雪机模型

二、二路外排序

• 归并原理:把第一阶段所生成的顺串加以合并(例如通 过若干次二路合并)，直至变为一个顺串为止，即形成 一个已排序的文件
• 为一个待排文件创建尽可能大的初始顺串，可以大大减 少扫描遍数和外存读写次数
• 归并顺序的安排也能影响读写次数，把初始顺串长度作 为权，其实质就是 Huffman 树最优化问题

三、多路归并——选择树

• k 路归并是每次将 k 个顺串合并成一个排好序的顺串
• 在 k 路归并中，最直接的方法就是作 k-1 次比较来找 出所要的记录，但这样做花的代价较大
• 我们采用选择树的方法来实现 k 路归并
• 选择树是完全二叉树，有两种类型:赢者树和败方 树
• 一般情况下，对 m 个初始顺串进行 k 路归并时归并趟 数为 log_km 。增加每次归并的顺串数量 k 可以减少归 并趟数

赢者树与数组的对应关系

外部结点的数目为 n，LowExt 代表最底层的外部结点数目 ; offset 代表最底 层外部结点之上(内部+LowExt之外的外部)所有结点数目。每一个外部结点L[i]所 对应的内部结点B[p]，i和p之间存在如下的关系:

赢者树的示例

败方树 ADT

外排序效率考虑

• 对同一个文件而言，进行外排序所需读写外存 的次数与归并趟数有关系
• 假设有 m 个初始顺串，每次对 k 个顺串进行 归并，归并趟数为 [ log_km ]
• 为了减少归并趟数，可以从两个方面着手:
• 减少初始顺串的个数 m
• 增加归并的顺串数量 k

假设对 k 个顺串进行归并，归并后长 n

• 原始方法Θ(k*n)，找到每一个最小值的 时间是Θ(k)
• 败方树方法总时间为 Θ(k+n*log k)
• 初始化包含k个选手的败方树需要 Θ(k)的时间
• 读入一个新值并重构败方树的时间为
• Θ(log k)

最佳归并树

四、思考

• 是否可以用赢者树或败方树形成 初始顺串?
• 是否可以用堆进行多路归并?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾