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

Orpherus

我有个想法
快排的时候pation把目标分为两个区间
左区间小于右区间

k=10000
设左区间有p个数
若p<k 则 k=k-p;递归的对右区间继续分区  
若p>k 则递归的对左区间继续分区  
若p==k 结束

book11

int型的数，如果没有4g的内存，怎么用计数排序，
这个题还是如32楼用快速排序的思想较好

nully

原帖由 ypxing 于 2007-8-22 23:27 发表
经典的计数排序呀
int *pi;
pi = (int*)malloc(sizeof(int)*INT_MAX);
遍历给定的10000000个数
用这个数组记录每个数字出现的次数
然后,再次遍历该数组,直到累计到10000

能执行成功吗？
这可是2G * 4 内存(32位)

g_hk

10000000个数不应该一次读到memory中.

内存中只需要保存需要的10000个数就可以. 不时的把不符合条件的数据替换了就可以!!!

apsong

patical_sort应该是C++最合适的了，哪位知道C语言有没类似的实现？或者哪个C语言开源项目有类似的实现？

[ 本帖最后由 apsong 于 2007-8-23 10:07 编辑 ]

jigloo

原帖由 zhkl125 于 2007-8-23 09:03 发表
#include
#include
#include

using namespace std;

void main()
{
        vector vecTmp;
        vecTmp.push_back(2);
        vecTmp.push_back(1);
        vecTmp.push_back(3);
        vecTmp.push_back(4);
        vecTmp.pus ...

既然用了stl的话，还可以写得紧凑些

1. 
   
2. #include <iostream>
   
3. #include <fstream>
   
4. #include <vector>
   
5. #include <algorithm>
   
6. #include <iterator>
   
7. #include <functional>
   
8. #include <cstdlib>
   
9. 
   
10. using namespace std;
    
11. 
    
12. void main()
    
13. {
    
14.         vector<int> vecTmp;
    
15.         generate_n(back_inserter(vecTmp), 10, rand);
    
16.         partial_sort(vecTmp.begin(), vecTmp.begin()+6, vecTmp.end(), less<int>());
    
17.         copy(vecTmp.begin(), vecTmp.begin()+6, ostream_iterator<int>(cout, " "));
    
18. }
    

复制代码

bb2bb

用partial_sort就是错的，前10000个不需要排序。