如何在海量100亿数据中精确计算中位数？

本文共计909个文字，预计阅读时间需要4分钟。

在大量数据中寻找中位数，内存无法一次性放下所有数据。中位数定义：数字排序后，位于中间的数。例如，将100亿个数字排序，排序后，位于第50亿位的那个数即为中位数。

海量数据中找到中位数，内存肯定是无法一次性放下这么多数据的

中位数定义：数字排序之后，位于中间的那个数。比如将 100 亿个数字进行排序，排序之后，位于第 50 亿个位置的那个数就是中位数。

桶排序

1）创建多个小文件桶，设定每个桶的取值范围，然后把海量数据元素根据数值分配到对应的桶中，并记录桶中元素的个数

2）根据桶中元素的个数，计算出中位数所在的桶（比如 100 亿个数据，第 1 个桶到第 18 个桶一共有 49 亿个数据，第 19 个桶有 2 亿数据，那么中位数一定在第 19 个桶中），然后针对该桶进行排序，就可以求出海量数据中位数的值（如果内存还是不够，可以继续对这个桶进行拆分；或者直接用 BitMap 来排序）

简单用 100 个数据画个图直观理解下：

分治法 + 基于二进制比较

假设这 100 亿数据都是 int 类型，4 字节（32 位）的有符号整数，存在一个超大文件中。

将每个数字用二进制表示，比较二进制的 (第 32 位)，如果数字的最高位为 0，则将这个数字写入 file_0 文件中；如果最高位为 1，则将该数字写入 file_1文件中。