首页 > 其他 > 详细

20140528 归并排序 内排序 外排序

时间:2014-05-30 00:14:16      阅读:365      评论:0      收藏:0      [点我收藏+]

1、归并排序

bubuko.com,布布扣

2、内排序和外排序

外排序的一个例子是外归并排序(External merge sort),它读入一些能放在内存内的数据量,在内存中排序后输出为一个顺串(即是内部数据有序的临时文件),处理完所有的数据后再进行归并。比如,要对 900 MB 的数据进行排序,但机器上只有 100 MB 的可用内存时,外归并排序按如下方法操作:

  1. 读入 100 MB 的数据至内存中,用某种常规方式(如快速排序堆排序归并排序等方法)在内存中完成排序。
  2. 将排序完成的数据写入磁盘。
  3. 重复步骤 1 和 2 直到所有的数据都存入了不同的 100 MB 的块(临时文件)中。在这个例子中,有 900 MB 数据,单个临时文件大小为 100 MB,所以会产生 9 个临时文件。
  4. 读入每个临时文件(顺串)的前 10 MB ( = 100 MB / (9 块 + 1))的数据放入内存中的输入缓冲区,最后的 10 MB 作为输出缓冲区。(实践中,将输入缓冲适当调小,而适当增大输出缓冲区能获得更好的效果。)
  5. 执行九路归并算法,将结果输出到输出缓冲区。一旦输出缓冲区满,将缓冲区中的数据写出至目标文件,清空缓冲区。一旦9个输入缓冲区中的一个变空,就从这个缓冲区关联的文件,读入下一个10M数据,除非这个文件已读完。这是“外归并排序”能在主存外完成排序的关键步骤 -- 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并),每个大块不用完全载入主存。

20140528 归并排序 内排序 外排序,布布扣,bubuko.com

20140528 归并排序 内排序 外排序

原文:http://www.cnblogs.com/yexuannan/p/3758064.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!