看到这个问题时，相信大多数人都会想：“这不是很简单嘛，先排序，然后最中间那个数不就是了？”

好像很有道理，但是大家往往忽略了一个问题，2亿个32位的整数就要占用4GB的内存空间，而内存空间往往不像我们想象中的那么充裕。

“那么，使用归并排序呢？每次先排序小部分。”，归并排序有一个不可避免的问题，虽然排序一小部分的时候占用的内存较小，但是总归是要合并到一起的，最终完全合并的时候还是需要占用4GB的内存。

那么我们还能怎么办？别急，我们来慢慢分析一下。

2亿个随机整数还可以分为两种情况，一种是2亿个不重复的随机整数，另一种是2亿个有重复项的随机整数。由于题目并没有指出数据中是否有重复项，所以我们只能按照有重复项的情况来解决。

[title]2亿个（有重复项的）随机整数[/title]
既然内存空间不够用，那我们能不能不把这些数据读入到内存中，而是直接在硬盘中直接排序？

但是！我们要知道，直接在硬盘中对数据进行排序的话需要多次读写硬盘，巨量的读写操作会消耗大量的性能，并且速度也比较慢。说直白点就是：可以，但是这种方法简直蠢死了。

那我们要怎么办啊？似乎是走投无路了。

别着急，你有没有发现题目虽然说让我们找出这些数的中间值，但是并没有要求我们对数据进行排序，只是我们自己绕进了排序的怪圈中。

我们只需要找出这些数据中，按大小排序处于第一亿位和第一亿零一位的两个数即可，而且我们可以利用一种很巧妙的方法来找到这两个数。

这是一种近似于二分查找思想的方法，我们可以在最开始的时候，以0为分界线，对所有整数进行遍历并统计小于0的整数个数和大于等于0的整数个数，假设小于0的整数有94,632,563个，那么大于等于0的数就有105,367,437个，这也就意味着，我们需要的那两个数是大于等于0的。

接下来我们就可以向第一次遍历那样对数据进行拆分了，我们知道int类型正整数最大值是2^31，那么第二次遍历我们就以2^30作为分界线吧，统计小于2^30的数与大于等于2^30的数，假设小于2^30的数有36,524,163个，大于2^30次方的数有68,843,274个，那么我们需要的那两个数处于0到2^30-1这个闭区间内。

按照这个方法，一次又一次第进行遍历，当我们统计出我们需要的那两个数处于某一个区间内，并且这个区间内的数比较少，至少能让我们直接在内存中进行排序时，我们就可以将符合这个区间的数全部读取到内存中排序，比如：

假设第一亿个数和第一亿零一个数是大于等于1,065,236且小于3,216,320的，并且我们统计到在这个区间内只有21,365个数，小于1,065,236的数有99,989,764个，这时候我们就可以将这21,365个数直接读入到一个数组中，对这个数组中的数据进行排序，第一亿个数即为排序完毕后的数组中的第10,236个数，而第一亿零一个数则为排序后的数组中的10,237个数。

怎么样？我们并没有对这2亿个整数进行排序，但依然找到了我们想要的这两个数字。

[title]2亿个（不重复的）随机整数[/title]
如果题目中提到的随机整数不存在重复项那就好办了，我们可以利用一种效率极高的算法来进行排序——位图排序

位图排序是一种空间换时间的排序算法，时间复杂度仅为O(n)，但它的限制很多，比如数据不能有重复项，在排序之前必须知道数据的范围（最小值及最大值，或者大致范围），范围越宽广，占用的内存空间就越大。

打个比方，假设有一万个不重复的整数，已知这些整数里最小的数为0，最大的数为100,000，这时候，我们可以申请一个长度为100,001位的内存空间（即97.66KB），然后遍历这一万个整数并且将内存空间中对应位置的位设为1，在遍历结束后排序也已经结束了。

可能这段话还不是很能让你理解透彻，这样吧，把数据量再缩小一些，比如有[19, 36, 3, 42, 11, 26, 5, 9, 24]这样一个数组，假设我们已经知道这个数组最小值为3，最大值为42，这时候我们就可以申请一个长度为40位的内存空间，如下：

00000 00000 00000 00000 00000 00000 00000 00000

（为了看起来方便，这里以5位相隔一个空格来表示）

对该数组进行遍历，并且将每个整数的值减去3之后，将对应位置设为1，结果如下：

10100 01010 00000 01000 01010 00000 00010 00001

从这串0和1中，我们能看到这里的第0位、第2位、第6位都为1，这几个1的位置加上数组中的最小值3则表示的是3, 5, 9这几个数。

说到这应该就能明白了吧，在排序完成后，只需要遍历一遍这个内存空间中的每一位就能输出排序后的数组。

在数据不重复的情况下，我们可以使用位图排序来对题目中的2亿个数据进行排序，随后遍历内存空间，遍历到第一亿个1的时候，这个1及下一个1所在的位置的平均值则为中间值。

什么？题目没有给出数据范围？其实是有的，int类型能表示的范围是-2^31到2^31之间，因此我们其实只需要2^32位的内存空间（即4GB）即可表示int类型所能表示的所有整数。

哈哈，开个玩笑，位图排序的使用限制实在是太多了，所以这道题，并不适合位图排序，这里只是心血来潮对位图排序做一个简单的介绍~