如何从1G数据中找出最大的1000个？

huasby 2007-10-21 11:17:59

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

...全文

1084 65 打赏收藏转发到动态举报

写回复

用AI写文章

65 条回复

切换为时间正序

请发表友善的回复…

发表回复

benbshmily 2010-04-09

打赏
举报

这个算法可以达到O(n)的复杂度，O(1000)空间

小洋 2010-04-09

打赏
举报

[Quote=引用 28 楼 xiantongyuan 的回复:]
先对这1G数据进行排序，建议堆排，然后去处前1000个数就行了。
[/Quote]

楼主图像太恶心啦哈哈

超级大笨狼 2007-11-05

打赏
举报

pjlpjl 二叉排序树算法复杂度o(NLogN)

jessekyypig 2007-11-04

打赏
举报

1.将数据分成x组（题目x=1000)（s1,s2,s3...),分别找出各自的最大值,再在各最大值中找出最大值，设在i组，这里
找出全部数据的最大值用了n-1次比较
2.然后在其他组的最大值和Si组里找最大值，需比较次数是（n/x+x-4)
3.以后每次找最大值最坏的比较次数均是（n/x+x-4)

故总的比较次数：n-1+(x-1)(n/x+x-4)=2*n+x*x=O(n)

zhiang75 2007-10-23

打赏
举报

为什么没有一个人说基数排序呢?
不过是n*4左右...

StealDream 2007-10-23

打赏
举报

浮点数比较，不用考虑精度吗？

liluyemin 2007-10-23

打赏
举报

需要计算的次数大约是（log 1000）*n/2次
1：建立链表取前1000个数排序，同时把链表的指针存放到a【1000】中
2：遍历剩下的数据出现比前1000个大的temp就把链表最后一个数据的值换成temp，插入链表对应位置
这里数组a为了方便链表的查找和操作因为1G的数据显然是上亿的，这里较少链表的查找次数可以大大提高效率。

以上算法大概计算次数就前面说的。

对于这么多数据采取排序这些肯定是不行的

pjlpjl 2007-10-23

打赏
举报

前1000个数构成二叉排序树，后来的数如果比排序树的最小值小则直接pass，否则插入到二叉排序树中。算法复杂度o(n)

超级大笨狼 2007-10-23

打赏
举报

1.直接插入最坏 n*n;
2.直接选择最坏 n*n;
3.冒泡排序最坏 n*n; 但是只要冒出来前1000个就好了，所以应该是1000＊n;
4.快速排序最坏 n*n;
5.堆排序最坏 n*logn;
6.归并排序最坏 n*logn;

补充一下:

7,桶排序(基数排序) 最好是O(n) 最坏n*n;

yuanchuang 2007-10-23

打赏
举报

当然，如果这1000个数字本身是要排序的，那楼主可以参考堆排序，呵呵

yuanchuang 2007-10-23

打赏
举报

取出1000个，这一千个本身不需要排序的话

楼主可以看看中位数排序，比较简单，我感觉他就是阉割后的快速排序，呵呵

huasby 2007-10-22

打赏
举报

Chiyer 的做法好象确实有问题
问题我注释了，看下面：

for (int i = 0; i < size; ++i)
{
for (int j = 0; j < 100; ++j)
if (datas[i] > Max[j])
{
Max[j] = datas[i];//这个地方是直接换掉的，而不是你所说的把小的挤出去
break;
}
}

0黄瓜0 2007-10-22

打赏
举报



//这个应该比全部排序要快点



#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;

}