数据结构实战

    返回首页    发表留言
本文作者:李德强
          第九章 外部排序
 
 

        与内部排序相对的是外部排序,它指的是在计算机外存中对数据进行排序工作。当然排序时可以将外存中的文件数完全读入内存,然后利用内部排序算法对其排序,排序完成后再写入外存。然而大多数情况下外存数据非常大,常常大于内存的大小,这时我们无法一次性将文件内容读入内存进行排序,所以我们就需要一种可以对外存文件内容排序的算法。

        对于大型的文件排序算法通常采用2路归并或多路归并算法,其思想是先将文件分块,重新写入文件系统。排序时再对这多个文件块进行2路归并或多路归并。例如在外存中有一个1GB大小的数文件需要进行排序,我们可以先将其按顺序读入,每读入100MB就将其写入一个新的块文件,于是一个1GB的文件就被分解成了10个100MB的块文件。然后再对这10个块文件分别两两读入进行归并排序,最后将多趟排序的结果保存起来。

        外部排序与内部排序有一些区别,但其核心思想还是利用内部排序对外存数据进行排序。具体实现过程不再给出,请读者做为课后题自己完成。

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号