本文共 934 字，大约阅读时间需要 3 分钟。

问题: 假设一个文件中有9 亿条不重复的9 位整数，现在要求对这个文件进行排序。

一般解题思路:

1 、将数据导入到内存中

2 、将数据进行排序　（比如插入排序、快速排序）

3 、将排序好的数据存入文件

难题:

一个整数为4 个字节

即使使用数组也需要900,000,000 * 4byte = 3.4G 内存

对于32 位系统，访问2G 以上的内存非常困难，而且一般设备也没有这么多的物理内存

将数据完全导入到内存中的做法不现实

其他解决办法:

1 、导入数据库运算

2 、分段排序运算

3 、使用bit 位运算

解决方案一: 数据库排序

将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件

解决方案一: 数据库排序

将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件

解决方案二: 分段排序

操作方式：

规定一个内存大小，比如200M ，200M 可以记录(200*1024*1024/4) = 52428800 条记录，我们可以每次提取5000 万条记录到文件进行排序，要装满9 位整数需要20 次，所以一共要进行20 次排序，需要对文件进行20 次读操作

缺点：

编码复杂，速度也慢( 至少20 次搜索)

关键步骤：

先将整个9 位整数进行分段，亿条数据进行分成20 段，每段5000 万条

在文件中依次搜索0~5000 万，50000001~1 亿……

将排序的结果存入文件

解决方案三:bit 位操作

思考下面的问题:

一个最大的9 位整数为999999999

这9 亿条数据是不重复的

可不可以把这些数据组成一个队列或数组，让它有0~999999999(10 亿个) 元素

数组下标表示数值，节点中用0 表示这个数没有，1 表示有这个数

判断0 或1 只用一个bit 存储就够了

声明一个可以包含9 位整数的bit 数组(10 亿) ，一共需要10 亿/8=120M 内存

把内存中的数据全部初始化为0, 读取文件中的数据，并将数据放入内存。比如读到一个数据为341245909 这个数据，那就先在内存中找到341245909 这个bit ，并将bit 值置为1 遍历整个bit 数组，将bit 为1 的数组下标存入文件

转载地址：https://blog.csdn.net/xxxcyzyy/article/details/50561536 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！