海量数据排序
外排序
传统意义上的排序都指的是内排序，针对的是数据可以一次全部载入内存中的情况。但是面对海量数据，不可能一次全部载入内存中，于是要使用外排序。外排序通常采用一种”排序-归并”的策略，首先要对数据分块，对块内数据选择一种高效的内排序策略进行排序，然后采用归并排序的思想对于所有的块进行多路归并，得到所有数据的一个有序序列。
假定现在有20个数据的文件A：{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15}，但一次只能使用仅装4个数据的内容，所以，我们可以每趟对4个数据进行排序，即5路归并，具体方法如下述步骤：
- 我们先把“大”文件A，分割为a1，a2，a3，a4，a5等5个小文件，每个小文件4个数据
a1文件为：5 11 0 18
a2文件为：4 14 9 7
a3文件为：6 8 12 17
a4文件为：16 13 19 10
a5文件为：2 1 3 15 - 然后依次对5个小文件分别进行排序
a1文件完成排序后：0 5 11 18
a2文件完成排序后：4 7 9 14
a3文件完成排序后：6 8 12 17
a4文件完成排序后：10 13 16 19
a5文件完成排序后：1 2 3 15 - 最终多路归并，完成整个排序
整个大文件A文件完成排序后：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
如果有1TB的数据需要排序，但只有100M的内存如何排序处理
将1TB数据进行拆分为20000份，每份为50M；
对每份数据使用快排排序，并写回硬盘；
对20000份数据采用多路归并
位图
对于数字大小有限的数据集，可以采用位图排序。32位无符号整数需要512M内存((2^32-1)/(810241024))
TOP K
topk通常指两类问题
- 集合中最大的前K个数
- 集合中出现频率最高的前K个数
对于情况1，我们可以使用外排序或最小堆来解决,两种方法都可极大的节省空间
最小堆实现时间复杂度为O(nlogn)
具体到这个题，时间复杂度是10log5
对于情况2，可以对记录值hash取模分为N个文件(对于仍然比较大的文件，可以继续hash分割)，对于单个小文件使用hashmap计数并排序，然后归并找出K个出现频率最高的数。