外存辅助排序

假设有一个4G可排序的文件,内存大小有1G,给出你的排序算法。
1.使用选择排序:遍历4G文件,最次找出最小的一个元素,找到后,写入一个文件中。其中每次加载进内存比如一行数据(内存利用率极低),为找到一个最小的元素,可能需要N多次载入内存的操作,效率极低。假如有N个元素,那时间复杂度为O(N^2 )

2.快速排序+合并排序:每次载入内存800M数据,这样5次即可遍历一遍所有的元素。对于每次载入内存的800M内存进行快速排序。5次快排之后,整个文件变为5块已排序的数据,然后再对这5部分数据进行合并排序。那时间复杂度为O(NlogN ).
未完待续。。。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 本文排序全部基于升序,为了方便阅读全部基于C,代码将全部部署到github上。(为方便各位看官调试,代码中的打印数...
    _onePiece阅读 519评论 0 1
  • http://www.cnblogs.com/mfryf/archive/2012/07/31/2616697.h...
    寻雨的人阅读 2,093评论 0 1
  • 最近被调过去做日志分析系统,接触所谓的大数据。学校的时候也做过空间数据库索引与数据挖掘研究(LBS方向),但是工作...
    HilaryQiao阅读 5,739评论 2 17
  • 2016 summer & 1、递归与分治法 递归的基本思想:一个直接或间接调用自身的算法 (1)斐波那契数列: ...
    橙小汁阅读 3,821评论 6 24
  • 写这些话的时候我内心一片柔软。 我叫春末,随我妈姓赵,全名赵春末,是一只雄性的金毛狗子,开心、跳跃的一只金毛狗子。...
    阿笙阅读 190评论 0 1

友情链接更多精彩内容