一数组有10亿个元素，取最大的1万条，有什么好算法。

Question

  一数组有10亿个元素，取最大的1万条，有什么好算法。不能用10亿个元素直接排序。再取前一万条。

Answer 1

内存放不下数组的话，建议用Merge sort

Answer 2

哈哈,  我昨天才发了.  你看下  记得给分啊!http://topic.csdn.net/u/20100421/19/63588372-a9a1-4c2d-a90c-0354c474a17d.html

Answer 3

哈哈, 我昨天才发了. 你看下 记得给分啊!http://topic.csdn.net/u/20100421/19/63588372-a9a1-4c2d-a90c-0354c474a17d.html

Answer 4

先做一个最大容量为1万的优先队列，以元素大小作为优先级，
先用前1万个数据填充这个优先队列
然后把剩下的数据，一个一个往里面丢：
如果当前数据比队列里最小的元素大，就把该元素删除，把当前元素扔进去。否则就什么都不做。效率为 n log(m) n=10亿，m=1万如果是排序的话，效率为 n log(n)

Answer 5

又想到了一种极其高效的算法，只需将数组遍历两遍。效率为 O(n)1）首先，找到第1万大的那个数。
算法见算法导论9.2节的算法：RANDOMIZED-SELECT(A, p, r, i)
A为数组，p和r为查找的初始和末尾位置，i表示查找第i大小的数。
算法的平均效率为 O(n)2）假设找到的数为a
然后遍历数组，将所有 >= a的数取出来。3）最后，考虑到数组里可能有重复的数，那么得到数据的可能多于1万个。（多出来的肯定是等于a的那些数）
这时只需将这1万多个数排序，然后把后面的丢掉即可。
当然还有一种更快的方法，在第（2）步遍历数组的时候，把>a的数放在一起，把=a的数放在另外一个地方，最后数一数两组数据的总个数，然后从等于a的那一组里把多余的数去掉即可。