转载。。。。
输入:
所输入的文件,至多包含n个正整数,每个正整数都小于n,题目中n = 10^7,如果输入时某个正整数重复出现俩次,就会产生致命的错误,这些整数,与其他任何数据都不相关.
输出:
以增序形式输出经过排序的整数列表
约束
至多只有1MB(包括程序本身)可用的主存,但是可以用的磁盘空间是充足的,运行时间至多几分钟,10秒针是最适宜的运行时间.
作者第一个方案使用基于磁盘的合并排序.将每个号码用32位整数表示,可以在1MB的空间里存储250000个号码,使用一个带有40个通道的程
序,在第一个通道中将0到249999之间的整数读入内存,并对它们进行排序,可以使用高效的快速排序,第一个通道中将250000到499999之间的整数读入内存,并对它们进行排序,直到第40个通道,读取9750000到9999999之间的证书进行排序,但是完成整个任务,我们要牺牲读文件40次的代价.
还有一种归并排序。。。。。。
最后作者引出了另外一种解决方案位图和位向量:
我们可以用一个20位的字符串可以表示小于20的非负数集合.例如,我们可以将集合{1,2,3,5,8,13}存储在下面字符串中:
集合中代表数字的各个位设置为1 ,而其他的位全部设置为0
在上面问题中,我们使用一千万位的字符串表示该文件,当且仅当整数i在该文件中的时候,第i位才被设置为1,这种表示法使用了这个问题中的三中属性,输入的范围相对小一些,并且还不包括重复的数据,而且没有数据和单个整数以外的每一记录相关联
算法实现分三阶段
1 设置每个位为0
2 读取文件,将相应的位设置为1
3 检查每个位,当为1时,将整数写入
这些函数使用常量来设置,清除并测试位值
分享到:
相关推荐
ASP.NET 2.0编程珠玑--来自MVP的权威开发指南
asp.net 2.0编程珠玑--来自mvp的权威开发指南asp.net 2.0编程珠玑--来自mvp的权威开发指南
ASP.NET+2.0编程珠玑--来自MVP的权威开发指南(英文版+中文16章节)
ASP.NET 2.0编程珠玑--来自MVP的权威开发指南
编程中的一本关于算法的好书。
为此,本书给出了一些精心设计的有趣而且颇具指导意义的程序,这些程序能够为那些复杂的编程问题提供清晰而且完备的解决思路,书中还充满了对实用程序设计技巧及基本设计原则的清晰而睿智的描述。 本书在第一版的...
关于很多很优秀的算法,五路从时间复杂度和空间复杂度上都很优秀
NULL 博文链接:https://philoscience.iteye.com/blog/1010964
ASP.NET+2.0编程珠玑,来自MVP的权威开发指南(无密码)
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
编程珠玑-英文版+中文版+source code
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
编程珠玑-[美]乔恩美特利.mobi、kindle文档、第二版修订版
本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。《编程珠玑(第 2版·修订版)》对各个层次的...