【9.4】外排序

磁盘文件的排序:

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

一、置换选择排序

置换选择示例:

置换选择算法的实现:

置换选择算法的效果:

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

扫雪机模型

二、二路外排序

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

三、多路归并——选择树

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

赢者树与数组的对应关系

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

赢者树的示例

败方树 ADT

外排序效率考虑

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

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

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

最佳归并树

四、思考

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

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学