从一亿个数中找出最大的一万个数

问题定义：

        从一亿个数中找出最大的一万个数

不假思索：

        拿到这道题，马上就会想到的方法是建立一个数组把1亿个数装起来，然后用for循环遍历这个数组，找出最大的1万个数来。原因很简单，如果要找最大的那个数，就是这样解决的；而找最大的一万个数，只是重复一万遍。这个解法类似于选择排序，一次将一个正确解放在合适的位置，重复一万次，所以时间复杂度为O(n *m)，如果你愿意去实现一下，会发现不等个几十分钟是不会出结果的。

稍做思考：

        上面的解决方案类似于一个选择排序，而我们知道，所有排序算法中选择排序是比较慢的，所以我们选择快速排序，将整个数组都排好续，然后取前一万个数就是我们想要的结果，solution1就是采用这种方法，将时间减少到只要几秒，可见快速排序真的很快。

深入思考：

        上面的方法已经有一个不错的效率了，但是，这里我们做了很多无用功，题目只要求我们将前一万个最大的数找到，我们却排序了整个数组，稍微相一下就知道还有很大的优化空间。方法二是解设前一万个数是我们需要找的一万个数，但是假设不一定成立，那么，我们只需要讲后续元素与前一万个数中的最小元素比较，如果最小元素比后续元素小，则交换数据，这样只需要遍历一遍大数组就能得到正确解。时间复杂度为O(n).solution2就是采用这种方法

深思熟虑：

        solution3的基本思路和solution2是一样的，不过做了两点优化。在solution2中，我们需要不断的找出前一万个数中最小的元素，是否可以进行优化呢？答案是肯定的，优化的方法就是维持前一万个数基本有序，则每次只需要查找一个很小的范围，就能找到前一万个数中最小的元素。还有点优化就是，前一万个数无序的时候，查找时间就变长了，就退化成solution2了，所以再交换600次数据以后，再对前一万个数进行排序，这样能提高查找最小元素的时间。

不断否定自己的方法：

        solution4测试了使用mutilset来保存前一万个数的情况，我们知道mutilset采用的是红黑树，且容器中的元素是有序的，正好符合我们的需求，实际测试发现，先率没有solution3快。


思路：
1、先取一亿个数中的前一万个数，建立小顶堆。
2、从一亿个数的第一万零一个数起，到最后一个数遍历。如果遍历到的数大于堆顶，则把堆顶替换成遍历到的数，然后调整堆。
3、遍历之后的那一万个数就是一亿中的最大数了。