设为首页 - 加入收藏 ASP站长网(Aspzz.Cn)- 科技、建站、经验、云计算、5G、大数据,站长网!
热搜: 创业者 数据 手机
当前位置: 首页 > 综合聚焦 > 编程要点 > 语言 > 正文

多路平衡归并排序 胜者树 败者树 算法细说

发布时间:2022-07-10 11:56 所属栏目:51 来源:互联网
导读:通过上一节对于外部排序的介绍得知:对于外部排序算法来说,其直接影响算法效率的因素为读写外存的次数,即次数越多,算法效率越低。若想提高算法的效率,即减少算法运行过程中读写外存的次数,可以增加 k 路平衡归并中的 k 值。 但是经过计算得知,如果毫无
  通过上一节对于外部排序的介绍得知:对于外部排序算法来说,其直接影响算法效率的因素为读写外存的次数,即次数越多,算法效率越低。若想提高算法的效率,即减少算法运行过程中读写外存的次数,可以增加 k –路平衡归并中的 k 值。
 
  但是经过计算得知,如果毫无限度地增加 k 值,虽然会减少读写外存数据的次数,但会增加内部归并的时间,得不偿失。
 
  例如在上节中,对于 10 个临时文件,当采用 2-路平衡归并时,若每次从 2 个文件中想得到一个最小值时只需比较 1 次;而采用 5-路平衡归并时,若每次从 5 个文件中想得到一个最小值就需要比较 4 次。以上仅仅是得到一个最小值记录,如要得到整个临时文件,其耗费的时间就会相差很大。
 
  为了避免在增加 k 值的过程中影响内部归并的效率,在进行 k-路归并时可以使用“败者树”来实现,该方法在增加 k 值时不会影响其内部归并的效率。
  败者树实现内部归并
  败者树是树形选择排序的一种变形,本身是一棵完全二叉树。
 
  胜者树和败者树的区别就是:胜者树中的非终端结点中存储的是胜利的一方;而败者树中的非终端结点存储的是失败的一方。而在比较过程中,都是拿胜者去比较。

(编辑:ASP站长网)

    网友评论
    推荐文章
      热点阅读