共计 1004 个字符，预计需要花费 3 分钟才能阅读完成。
海量数据中找到中位数，内存必定是无奈一次性放下这么多数据的
中位数定义：数字排序之后，位于两头的那个数。比方将 100 亿个数字进行排序，排序之后，位于第 50 亿个地位的那个数就是中位数。
桶排序
1）创立多个小文件桶，设定每个桶的取值范畴，而后把海量数据元素依据数值调配到对应的桶中，并记录桶中元素的个数
2）依据桶中元素的个数，计算出中位数所在的桶（比方 100 亿个数据，第 1 个桶到第 18 个桶一共有 49 亿个数据，第 19 个桶有 2 亿数据，那么中位数肯定在第 19 个桶中），而后针对该桶进行排序，就能够求出海量数据中位数的值（如果内存还是不够，能够持续对这个桶进行拆分；或者间接用 BitMap 来排序）
简略用 100 个数据画个图直观了解下：
分治法 + 基于二进制比拟
假如这 100 亿数据都是 int 类型，4 字节（32 位）的有符号整数，存在一个超大文件中。
将每个数字用二进制示意，比拟二进制的【 最高位 】(第 32 位)，如果数字的最高位为 0，则将这个数字写入 file_0 文件中；如果最高位为 1，则将该数字写入 file_1 文件中。
最高位为符号位，也就是说 file_1 中的数都是正数，而 file_0 中的数都是负数。
通过这样的操作，这 100 亿个数字分成了两个文件，假如 file_0 文件中有 60 亿个数字，而 file_1 文件中有 40 亿个数字。
这样划分后，思考一下：所求的中位数在哪个文件中？
100 亿个数字的中位数是 100 亿个数排序之后的第 50 亿个数，当初 file_0 有 60 亿个负数，file_1 有 40 亿个正数，file_0 中的数都比 file_1 中的数要大，排序之后的第 50 亿个数是中位数，那么这个中位数肯定位于 file_0 中，并且是 file_0 文件中所有数字排序之后的第 10 亿个数字。
当初，咱们只须要解决 file_0 文件了（不须要再思考 file_1 文件）。
而对于 file_0 文件，能够同样地采取下面的措施解决：将 file_0 文件顺次读一部分到内存，将每个数字用二进制示意，比拟二进制的【 次高位 】（第 31 位），如果数字的次高位为 0，写入 file_0_0 文件中；如果次高位为 1，写入 file_0_1 文件中。
现假如 file_0_0 文件中有 30 亿个数字，file_0_1 中也有 30 亿个数字，则中位数就是：file_0_1 文件中的数字从小到大排序之后的第 10 亿个数字。
摈弃 file_0_0 文件，持续对 file_0_1 文件 依据【 次次高位 】(第 30 位) 划分，如此重复上来
