有2种办法;
多路归并排序
和
位图法
.
多路归并排序
采用分块的方法（分而治之），首先将数据分块，对块内数据按选择一种高效的内排序策略进行排序(如
快速排序
)。然后采用
归并排序
的思想对于所有的块进行排序，得到所有数据的一个有序序列。
1TB数据使用32GB内存如何排序
①、把磁盘上的1TB数据分割为40块（chunks），每份25GB。（注意，要留一些系统空间！）
②、顺序将每份25GB数据读入内存，使用quick sort算法排序。
③、把排序好的数据（也是25GB）存放回磁盘。
④、循环40次，现在，所有的40个块都已经各自排序了。（剩下的工作就是如何把它们合并排序！）
⑤、从40个块中分别读取25G/40=0.625G入内存（40 input buffers）。
⑥、执行40路合并，并将合并结果临时存储于2GB 基于内存的输出缓冲区中。当缓冲区写满2GB时，写入硬盘上最终文件，并清空输出缓冲区；当40个输入缓冲区中任何一个处理完毕时，写入该缓冲区所对应的块中的下一个0.625GB，直到全部处理完成。
继续优化
磁盘I/O通常是越少越好（最好完全没有），那么如何降低磁盘I/O操作呢？关键就在第5和第6步中的40路输入缓冲区，我们可以先做8路merge sort，把每8个块合并为1路，然后再做5-to-1的合并操作。
所以
K路合并的次数为 logk(N/M)的向上取整。n为数据总大小，m为最大的内存。
再深入思考一下，如果有多余的硬件，如何继续优化呢？有三个方向可以考虑：
使用并发：如多磁盘（并发I/O提高）、多线程、使用异步I/O、使用多台主机集群计算。
提升硬件性能：如更大内存、更高RPM的磁盘、升级为SSD、Flash、使用更多核的CPU。
提高软件性能：比如采用radix sort、压缩文件（提高I/O效率）等。
位图法
前提是
数据不重复
。
缺点：不适用的场景有
数据稀疏。要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费
在c++中使用 new byte的思路进行处理。如果想用bitset数组的话，数量就不能很大（因为是在栈上创建内存空间的）。
实现过程: 找出整个数组的最大元素max，然后创建一个长度为max + 1的新数组，然后再次扫原数组，遇到几就给新数组的第几位置上置1.最后重新遍历整个新数组进行输出。
优点就是：1内存空间少.2 运算时间快。
#define max_len 4000000000
DWORD dwstart = GetTickCount();
byte *bt = new byte[max_len];
memset(bt, 0, sizeof(byte)*max_len);
for (int64_t i = 0; i <= max_len; i++)
{
if (bt[i] == 1)
{
}
}
DWORD dwend = GetTickCount();
DWORD dw = dwend - dwstart;
delete []bt;
//测试遍历40亿的数据，内存是4G,大概需要8s.
改造,使用bitset
DWORD dwstart = GetTickCount();
bitset<max_len+1> bt;
for (int64_t i = 0; i <= max_len; i++)
{
if (bt[i] == 1)
{
}
}
DWORD dwend = GetTickCount();
DWORD dw = dwend - dwstart;
//测试遍历40亿的数据，内存是500M,大概需要91s.因为是在堆栈上开辟内存，所以要设置vs的堆栈大小，这里设置为600M.
延伸：处理海量数据问题：
1.分而治之/hash映射 + hash统计 + 堆/快速/归并排序；
2.双层桶划分
3.Bloom filter/Bitmap；
4.Trie树/数据库/倒排索引；
5.外排序；
6.分布式处理之Hadoop/Mapreduce。
教你如何迅速秒杀掉：99%的海量数据处理面试题_v_JULY_v的博客-CSDN博客
前提基础：序列容器
序列式容器(vector/list/deque/stack/queue/heap)
关联容器（set/map/multiset/multimap）
散列容器或者说哈希列表 （hash_set/hash_map/hash_multiset/hash_multimap）
分而治之/hash映射 + hash统计 + 堆/快速/归并排序
说白了，就是先映射，而后统计，最后排序：
分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决
hash_map统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。时间复杂度为
n*o(1).
堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。时间复杂度为
N’*logK
具体步骤是：在海量的数据中，没法一次性把数据放进内存。操作思路：使用
分治思维＋hash。分治表现为外排序的多路归并排序。
1.要考虑分成N块小文件，分块的思想是：hash散列表，目的是把相同的数据放到一个小文件。
如果文件不是特别大，看能否一次性装进内存不，如可以，就不用映射分块文件了。
2.对分块的小文件进行归并排序，或者hash统计及排序。
3.已经排好序的分块文件中，提取想要的数据，进行归并整合成新文件。
4.有可能进行重复2-3的步骤，直到满足要求。
多层划分
多层划分—-其实本质上还是分而治之的思想，重在“分”的技巧上！
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
如 2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
Bloom filter/Bitmap
其中Bitmap 适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码。见上面的位图法。
扩展：bloom filter可以看做是对bit-map的扩展。还有2-bitmap.
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。
外排序
适用范围：大数据的排序，去重
基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
问题实例：
1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。内存可以当输入缓冲区使用。
具体见最上面的介绍
Trie树/数据库/倒排索引
Trie树
适用范围：数据量大，重复多，但是数据种类小可以放入内存
基本原理及要点：实现方式，节点孩子的表示方式
扩展：压缩实现。
数据库索引
适用范围：大数据量的增删改查
基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
倒排索引(Inverted index)
适用范围：搜索引擎，关键字查询
基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
分布式处理之Mapreduce
MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序。
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
例子：
给40亿个不重复的unsigned int的整数进行排序。
//排序，按升序排列的输入正数的列表
#define max_len 4000000000
DWORD dwstart = GetTickCount();
bitset<max_len+1> bt1;
FILE *fpsrc;
fpsrc = fopen("data.txt", "r");
int data;
while (fscanf(fpsrc, "%d ", &data) != EOF)
{
if (data <= max_len)
{
bt1.set(data, 1);
}
}
FILE *fpdst;
fpdst = fopen("result.txt", "w");
for (int64_t i = 0; i <= max_len; i++)
{
if (bt1[i] == 1)
{
fprintf(fpdst, "%d ", i);
}
}
fclose(fpdst);
fclose(fpsrc);
DWORD dwend = GetTickCount();
DWORD dw = dwend - dwstart;
时间复杂度为O（2N）,N表示总数
给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
解：申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
//排序，按升序排列的输入正数的列表
DWORD dwstart = GetTickCount();
bitset<max_len+1> bt1;
FILE *fpsrc;
fpsrc = fopen("data.txt", "r");
int data;
while (fscanf(fpsrc, "%d ", &data) != EOF)
{
if (data <= max_len)
{
bt1.set(data, 1);
}
}
int ndst;
if (bt1[ndst] == 1)
{
//表示存在
}
fclose(fpsrc);
DWORD dwend = GetTickCount();
DWORD dw = dwend - dwstart;
时间复杂度为O（N）,N表示总数解法二：
又因为2^32为40亿多，所以给定一个数可能在，也可能不在其中；
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；
与要查找的数的次最高位比较并接着进入相应的文件再查找。
.......
以此类推，就可以找到了,而且时间复杂度为O(logn)，方案2完。
在2.5亿个整数中找出不重复的正整数，注，内存不足以容纳这2.5亿个整数
解法1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。
解法2：采用2个bitmap.即第一个Bitmap存储的是整数是否出现过，
如果没出现过，把第一个bitmap对应的位置置1.
如果出现过就设置第二个BitMap对应的位置也为1。
最后同时遍历这2个BitMap，仅仅在第一个BitMap相应位置为1，第二个bitmap相应位置为0的元素，就是不重复的整数。
int temp;
bitset<max_len+1> bt1(0);
bitset<max_len+1> bt2(0);
for (int i= 0; i < max_len;i++)
{
if (bt1[temp] == 0)
{
bt1.set(temp,1);
}
else
{
bt2.set(temp, 1);
}
}
for (int i = 0; i < max_len; i++)
{
if (bt1[i] == 1 && bt2[i] == 0)
{
//只有一次
}
}
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。
第一步：Query统计
使用Hash Table法（散列表法），因为散列表的每个元素的查找时间复杂度是0（1）。事实上只有300万的Query，每个Query255Byte，那总大小是7百多M,1G的内存够用。因此我们可以考虑把他们都放进内存中去。
具体是：维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。n表示1000万。
第二步：找出Top 10
办法1：没有必要对所有的Query都进行排序，我们只需要维护一个10个大小的数组，初始化放入10个Query，按照每个Query的统计次数由大到小排序，因为有序，每一次可以采用二分的方法查找，遍历这300万条记录。最后当所有的数据都遍历完毕之后，那么这个数组中的10个Query便是我们要找的Top10了。排序的时间复杂度是N'*O（logK）。 n'表示的是300万，k表示10
办法二：借助堆结构，我们可以在log量级的时间内查找和调整/移动。维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。
具体过程是，堆顶存放的是整个堆中最小的数，现在遍历N个数，把最先遍历到的k个数存放到最小堆中，并假设它们就是我们要找的最大的k个数，X1>X2...Xmin(堆顶)，而后遍历后续的N-K个数，一一与堆顶元素进行比较，如果遍历到的Xi大于堆顶元素Xmin，则把Xi放入堆中，而后更新整个堆，更新的时间复杂度为logK，如果Xi<Xmin，则不更新堆，整个过程的复杂度为O(K)+O(（N-K）*logK)=O（N*logK）。
总结：
经过上述第一步、先用Hash表统计每个Query出现的次数，O（N）；然后第二步、采用堆数据结构找出Top 10，N*O（logK）。所以，我们最终的时间复杂度是：O（N） + N'*O（logK）
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
方案：顺序读文件中，对于每个词x，取hash(x)%5000，
然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。
这样每个文件大概是200k左右。
如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，
直到分解得到的小文件的大小都不超过1M。
对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），
并取出出现频率最大的100个词（可以用含100个结点的最小堆），
并把100个词及相应的频率存入文件，这样又得到了5000个文件。
下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。
有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序
。
一般query的总量是有限的，只是重复的次数比较多而已，
可能对于所有的query，一次性就可以加入到内存了。
这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，
然后按出现次数做快速/堆/归并排序就可以了。
海量日志数据，提取出某日访问百度次数最多的那个IP。
算法思想：分而治之+Hash
1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；
2.可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。如果要求使用内存很小，同时按hash分出的文件大小大于要求的内存，则继续对分出来的文件求hash继续分，知道所有的文件大小都小于要求的内存；
3.对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；
4.可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；
在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
可以考虑采用“分而治之”的思想，按照hash散列表,进行划分小文件的方法。
然后在小文件使用hash key为数值，value为数值的次数，进行记录，从而找出不重复的整数，并排序。
然后再进行归并，注意去除重复的元素。