5亿个数中找到中位数

问题

有5亿个整数，没有排序。找到他们的中位数

思路

使用双层桶划分(分而治之)的策略。假设题目中指的是32位的无符号整数，共有2 ^ 32个数字。
我们将2 ^ 32这个范围划分成2 ^ 10个区域。对数据进行第一次扫描，统计各个落到各个区域内的数字的个数。
第一次扫描后，通过统计就可以知道，中位数在哪个区域内，以及它是这个区域的第几大的数字。
进行第二次扫描，这次只统计落到目标区域内的数字，同时结合Bitmap记录都出现了哪些数字。最后通过Bitmap和第一次扫描的结论，就可以找到那个中位数了。