5亿个int找中位数 - AstroMen/Algorithm-DataStructure GitHub Wiki

统计各个区域的数

首先我们将 int 划分为 2^16 个区域，然后读取数据统计落到各个区域里的数，之后我们根据统计结果就可以判断中位落到那同时知道这个区域中的第几大数刚好是位。然后二次扫描我们只统计落在那些数就可以了。

确定子区

实际上，如果不是 int 是 int64，我们可以经过 3 次这样的划分即可降低到以接受程度。即可以先将 int64 分成 2^24 个区域，然后确定的第几大数在将该分成 2^20 个子区域，然后确定是子区的第几大数，然后确定是子区的第几大数里个只有 2^20，就可以直接利用direct addr table 进行统计了。