输入任意M个正整数，要求输出N个最大值，其中M和N数量任意，M远大于N?
如输入10?98?46?55?37?87，输出两个最大值为?98?87，?给出更快，更节省内存的算法
------解决方案--------------------
搞个N长的队列，每次输入都和队列中的值比较，最终保存下来的就是最大的N个数
------解决方案--------------------
用一个大小为N的数组 min heap, 每个输入值和最小值比较，小就抛弃，大就替换。这样算法空间复杂度是 O(N)，时间复杂度是 O(M*logN)。
------解决方案--------------------
建一个collection，size N，使用comparator重小到大排列，先一次吃进N个数。最小的在位置0。然后后面的数每个都跟位置0的对比，如果大于就把位置0的删掉，插入新数。时间复杂度 N+logM
------解决方案--------------------
如果是面试题的话，首先要回答"建立size=N的大根堆"；接下来，面试官会问你有没有更好的方法，你回答"快速选择"；然后你给他解释“快速选择”的基本算法与历史来源，面试官会对你刮目相看。
------解决方案--------------------
既然是只选择前几个最大的数那么就没有必要进行排序了，因为最快的比较排序算法下限都是nln(n), 不过楼主可以试下非比较排序，比如计数排序或者桶排序，详细介绍看我的博文http://blog.csdn.net/china_zoujinyong/article/details/16892223
http://blog.csdn.net/china_zoujinyong/article/details/16898707
不过我还是觉得排序是没有必要的，现在给你一个算法，线性的时间复杂度，常数的大小取决于数据
#include <stdio.h>
#include <time.h>
#define SWAP(x, y) {int t; t=x; x=y; y=t;}
int partition(int a[], int p, int r)
{
int x = a[r];
int i = p-1, j;
for(j = p; j <= r-1; j++)
{
if(a[j] <= x)
{
i++;
SWAP(a[i], a[j]);
}
}
SWAP(a[i+1], a[r]);
return i+1;
}
int randomized_partiton(int a[], int p, int r)
{
int x = rand()%r;
int temp;
temp = x+p > r ? x: x+p;
SWAP(a[temp], a[r]);
return partition(a, p, r);
}
int randomized_select(int a[], int p, int r, int i)
{
int q, k;
// 检测程序只有一个元素的情况
if(p==r)
return a[p];
q = randomized_partiton(a, p, r);
k = q - p+1;
if(i==k)
return a[q];
else if(i < k)
return randomized_select(a, p, q-1, i);
else
return randomized_select(a, q+1, r, i-k);
}
int main()
{
int a[10]={3,1,5,7,8,2,4,6,10,9};
int x;
srand(time(NULL));
x = randomized_select(a, 0, 9, 10);
printf("%d\n", x);
system("pause");
return 0;
}
C语言写的，楼主改下就可以了