如何从1G数据中找出最大的1000个？
1G数据，浮点数，怎样快速查找出最大的1000个数？内存足够大。
忘高手解答。


[解决办法]

定义一个1000大小的数组 a,

遍历这1G数据

逐个把数据放到 a 中, (a 中的数据从大到小排列) 把小的数据挤出




[解决办法]
先从大到小排序，再取出前面1000个就可以了。不要搞那么复杂，排个序又不复杂，况且有现成的函数可用。
[解决办法]
全部排序会很慢
用STL的 partial_sort
[解决办法]
这种帖子回了三四次了。
[解决办法]

C/C++ code

//这个应该比全部排序要快点#include <iostream>#include <list>#include <algorithm>using namespace std;#include <time.h>template <class T>void find_max(T* datas,size_t ds,list<T>& max,size_t ms){    size_t i;    for(i=0;i< ms;++i)    {        max.push_back(datas[i]);    }    max.sort( greater<T>());//降序       for ( i = ms; i < ds; ++i)// 20 19 18 16 15 10  8 7//    {        if(datas[i] < *max.begin())//算法效率的关键在,对小于这ms个数的数直接放弃            continue;          list<T>::iterator iter;    for(iter=max.begin();iter != max.end();++iter)            {            if(datas[i] > *iter)            {            max.insert(iter,datas[i]);            max.pop_back();            break;            }        }    }}int main(){    srand(time(0));//    const int size = 100;    float* datas = new float[size];    int i;    for ( i = 0; i < size; ++i)    {        datas[i] = (float)rand();        //cout<<datas[i]<<' ' ;    }    const int m=10;    float max[m] = {0.0};    //排序后输出最大的m个数,测试对比用.    //sort(&datas[0],&datas[size]);    //for ( i = size-1; i >=size-m; --i)    //{    //    cout<<datas[i]<<' ' ;    //}    //cout<<endl;        list<float> fmax;    find_max(datas,size,fmax,m);        for (list<float>::iterator iter=fmax.begin();iter!=fmax.end();++iter)        cout<<*iter<<" ";    cout<<endl;    delete[] datas;    return 0;}
[解决办法]
我有个猜想,请高手指正
利用快速排序中划分,m=1000
(1)一次划分结束后,可以得到一个大数划分和一个小数划分,并且划分元素所在的索引n表示它是第n大元素.
(2)若划分后n>>m,则再在大数划分中选择划分元素继续划分得到该划分中n个最大数,转(2)
(3)若划分后n<<m,则m=m-n再在小数划分中选择划分元素继续划分得到该划分中n个最大数,转(2)
(4)若n接近m,则只需要在现在划分下的大数或小数划分中找出|n-m|个大数,或去掉|n-m|个小数
(5)若n=m,则1000个最大数找出

其主要思想是尽可能不去处理较小的数,通过划分后,不断向目标大数划分逼近,且每次划分后的处理量减少,提高性能.

以上为个人猜想,请指教!
[解决办法]
这种类似问题可以出个专集了。。
。。用数论推个理论出来，大家按那标准做就最好了。
[解决办法]
to iambic:   "楼上的你的partition很典型。但是请考虑下最坏情况。"
sliuyin的方法是在快排基础上的针对这道题一种改进,最坏情况也不过快排的
最坏情况啊.

我觉得他的方法还行.个人看法,请iambic指点.

[解决办法]
1:想把总的数据等分(等分多少分,看实际要求),每一分相当于一组
2:对等分后的每一组数据进行排序(降序)
3:然后在这些组中检最大的1000个数据
[解决办法]
肯定不能进行排序了，星羽那个改一下就是很快了，如果用list来实现的话，在挤出数据那里又会快一点