输入任意M个正整数，要求输出N个最大值

Question

用一个大小为N的数组 min heap,  每个输入值和最小值比较，小就抛弃，大就替换。这样算法空间复杂度是 O(N)，时间复杂度是 O(M*logN)。

Answer 1

建一个collection，size N，使用comparator重小到大排列，先一次吃进N个数。最小的在位置0。然后后面的数每个都跟位置0的对比，如果大于就把位置0的删掉，插入新数。时间复杂度 N+logM

Answer 2

如果是面试题的话，首先要回答"建立size=N的大根堆"；接下来，面试官会问你有没有更好的方法，你回答"快速选择"；然后你给他解释“快速选择”的基本算法与历史来源，面试官会对你刮目相看。

Answer 3

既然是只选择前几个最大的数那么就没有必要进行排序了，因为最快的比较排序算法下限都是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语言写的，楼主改下就可以了