置换选择排序算法详解

  • 内容
  • 评论
  • 相关

上一节介绍了增加 k-路归并排序中的 k 值来提高外部排序效率的方法,而除此之外,还有另外一条路可走,即减少初始归并段的个数,也就是本章第一节中提到的减小 m 的值。

m 的求值方法为:m=⌈n/l⌉(n 表示为外部文件中的记录数,l 表示初始归并段中包含的记录数)

如果要想减小 m 的值,在外部文件总的记录数 n 值一定的情况下,只能增加每个归并段中所包含的记录数 l。而对于初始归并段的形成,就不能再采用上一章所介绍的内部排序的算法,因为所有的内部排序算法正常运行的前提是所有的记录都存在于内存中,而内存的可使用空间是一定的,如果增加 l 的值,内存是盛不下的。

所以要另想它法,探索一种新的排序方法:置换—选择排序算法

例如已知初始文件中总共有 24 个记录,假设内存工作区最多可容纳 6 个记录,按照之前的选择排序算法最少也只能分为 4 个初始归并段。而如果使用置换—选择排序,可以实现将 24 个记录分为 3 个初始归并段,如图 1 所示:


本文标题:置换选择排序算法详解

本文地址:http://www.hosteonscn.com/5269.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注