在10000000个数(int)中求最小的10000个数

aero

原帖由 yecheng_110 于 2007-8-22 23:52 发表

遍历一次就够了
看看桶排序(和他们说的计数排序应该是一样的吧)就明白了

嗯，学习ing……

converse

原帖由 aero 于 2007-8-22 23:52 发表


前10000个数。

哦,如果用C++的话就用map好了,把全部的数据插入进去,取前10000个就是了.

如果要自己写算法,map底层是用的堆排序算法.

bb2bb

原帖由 converse 于 2007-8-22 23:58 发表


哦,如果用C++的话就用map好了,把全部的数据插入进去,取前10000个就是了.

如果要自己写算法,map底层是用的堆排序算法.

居然想到用map

converse

原帖由 bb2bb 于 2007-8-23 00:04 发表


居然想到用map

有什么问题吗?请指教.

tyc611

计数排序太费空间，小军帽1楼的方法是可行的，由于是求最小10000，效率也可以保证

cjaizss

建堆（优先队列）,算法时间复杂度o(n*logm),n在这里是100000000，m在这里是10000

ypxing

计数排序的
时间复杂度O(n)
空间复杂度O(n),是有点大,
看LZ的需要了

yecheng_110

大家都还没睡呀

bb2bb

原帖由 converse 于 2007-8-23 00:07 发表


有什么问题吗?请指教.

当然有问题了，问题还不是一般的大。这个问题用vector才有效率，map的存储比它差远了。

我写了一个简单的，希望搂主和这个算法先作一下比较，看看谁的更快，这是标准算法，如果能超过这个那可能标准算法还可以优化一下了。

1. 
   
2. 
   
3. #include <vector>
   
4. #include <algorithm>
   
5. #include <sys/time.h>
   
6. 
   
7. int main()
   
8. {
   
9.         std::vector<int> datalist;
   
10.        
    
11.         printf("making data...\n");
    
12.         for(unsigned int i=0;i<10000000;i++)
    
13.         {
    
14.                 datalist.push_back(rand());
    
15.         }
    
16.        
    
17.         printf("sorting data...\n");
    
18.         static struct timeval begin,end;
    
19.     gettimeofday( &begin, NULL );
    
20.        
    
21.         nth_element(datalist.begin(),datalist.begin()+10000,datalist.end());
    
22.        
    
23.     gettimeofday( &end, NULL );
    
24.         printf("sort end\n");
    
25.        
    
26.         long us=(end.tv_sec - begin.tv_sec)*1000*1000 + (end.tv_usec - begin.tv_usec);
    
27.        
    
28.         printf("time=%ld us\n", us);
    
29. 
    
30.         return 0;
    
31. }
    
32. 
    

复制代码

converse

原帖由 bb2bb 于 2007-8-23 00:40 发表


当然有问题了，问题还不是一般的大。这个问题用vector才有效率，map的存储比它差远了。

我写了一个简单的，希望搂主和这个算法先作一下比较，看看谁的更快，这是标准算法，如果能超过这个那可能标准算法 ...

.....