面试的问题请高手帮忙解决

sunyore

一个存有超过40亿个整型数据的二进制文件，请把数据排序由小到大然后写到另一个文件里。

svenwang

如果不是考算法的话，自己写一个枚举器封装文件I/O操作，使用stl的sort函数就可以了；自己写算法的话，也不是很难的事，写一个模板的排序算法就是了。关键是这么多的数，内存是放不下的，只能直接在文件上操作。

iwhy

如果数字范围有限，比如从0到40亿。
如果内存比较足，比如40亿可以用40亿bit位内存，即4G内存。bit位表示范围从数字范围下限开始。

依次读取整数，将相应比特位置位。

从bit0开始读取，置位则计算出该位代表的数字并写入输出文件，最后得到的就是一个顺序的数字排序文件。

耗内存比较多。变通的方法是，将40亿个数字分隔读取，比如每次读入1亿个数字，按照上述方法排序。得到40个顺序数字集合，再合并所有顺序数字集合即可。

不计效率，也可以直接创建一中间结果文件（40亿比特大小），每次向该文件某个地方写入一bit（需要根据数值进行定位）。然后顺序读取该文件，算出每个置位bit对应的整数，写入另一个文件。

assiss

1、创建一个4GB的文件，全部置0
2、挨个读原始文件中的数
3、以这个数值为索引，在新创建的文件1中的相应位置写入＋1值（即先读一下，把这个位置的数值加1，再写回去，这主要是为了重复数字），一直到读完原始文件
4、读文件1，读到的数值是多少，就把这个数值对应的索引值往结果文件里写多少遍。
5、空间复杂度：需要一个4GB的中间文件
6、时间复杂度：共读12GB，写8GB。

iwhy

通常遇到的排序问题，经常将重复数据（冗余），从结果中剔除。比如某地市所有电话号码。或者全国电话号段等。所以上面我没有将重复数据计次。

iwhy

原帖由 "assiss" 发表：
1、创建一个4GB的文件，全部置0
2、挨个读原始文件中的数
3、以这个数值为索引，在新创建的文件1中的相应位置写入＋1值（即先读一下，把这个位置的数值加1，再写回去，这主要是为了重复数字），一直到读完原始文件..........

提醒一下，如果一定要计次。那么只用字节存储相关数据重复计数是远远不够的。严密的话，每个数据单元应该可以表示40亿大小的数字。否则所有数据重复将造成计数结果的不准确。所需的文件空间远远不止4GB了。

assiss

原帖由 "iwhy" 发表：


提醒一下，如果一定要计次。那么只用字节存储相关数据重复计数是远远不够的。严密的话，每个数据单元应该可以表示40亿大小的数字。否则所有数据重复将造成计数结果的不准确。所需的文件空间远远不止4GB了。

忘记说明了，呵呵，我这个记数不是以字节记的，而是以4字节为单位，刚才也计算出错，不是4GB，而是4×4GB。

benjiam

将40亿个数字分隔读取，比如每次读入1亿个数字，按照上述方法排序。得到40个顺序数字集合，再合并所有顺序数字集合即可。

感觉最简单 实用 每次读1000w 个数字
排序

最后400个串列何必就可以了

FH

assiss才是正解！

bleem1998

用mmap行不行？
然后开始冒泡
最后munmap写到磁盘