今天待着无聊，测试了一下我的算法(不对筛选结果排序)，单线程(只用一个CPU的核心)大约用440ms(测试10次的平均值)，不过跟楼主的函数头稍有差异，楼主的函数头筛选结果似乎要放到一个数组result里面，我没有这样做，而是直接筛选出来，我测试使用的随机数用我的random产生(范围是0~21亿)(假如用系统的rand()，还用不了440ms)。假如需要对筛选结果排序，则总时间大约用1秒。

系统配置：
OS: Windows XP Professional SP2 (English Version)
RAM: DDRII 667 1GB
CPU Intel(R) Core(TM)Duo CPU 2.09GHz Mobile
Comiler: g++ 3.4.5 (-O3)

希望别的朋友提出更好的算法。

#include<memory.h>
#include <algorithm> 
#include <functional> 

void MaxK_1(int a[], int n, int k, int result[]);
void MaxK_2(int a[], int n, int k, int result[]);
void my_nth_element(int low,int high,int key[],int n);
void MaxK(int *bigr,int bigarr_len, int *res,int n);

void MaxK_1(int bigr[],int bigarr_len,int res[],int n){ 
    memcpy(res,bigr,sizeof(int)*n);
    std::sort(res,res+n);
//    my_qsort(0,n,res);
    int mindex=0;
    int minzone=mindex;
    
    for(int i=n;i<bigarr_len;i++){
        if(res[mindex]<bigr[i])    {
            res[mindex]=bigr[i];
            if(mindex==minzone)
                minzone++;
            if(    minzone==n) minzone--;
            int l=700;
            if(minzone>=l){          
                std::sort( res , res + l+1); 
                std::merge(res, res +l+1, res + l+1, res + n, bigr); 
                memcpy(res,bigr,sizeof(int)*n);
                mindex=minzone=0;
                continue;
            }     
            mindex=minzone;
            for(int k=minzone-1;k>=0;k--){
                if(res[k]<res[mindex])
                    mindex=k;
            }         
        }
        
    }
}
void MaxK_2(int *bigr,int bigarr_len, int *res,int n){
    my_nth_element(0, bigarr_len-1, bigr,bigarr_len-n);
    memcpy(res,bigr+bigarr_len-n,sizeof(int)*n);
}
void MaxK(int *bigr,int bigarr_len, int *res,int n){
     if(n<15000)
          MaxK_1(bigr,bigarr_len,res,n);
     else
        MaxK_2(bigr,bigarr_len,res,n);
}
void my_nth_element(int low,int high,int key[],int n)
{
     int i=low,j=high,mid=(i+j)>>1,tag=key[i];
     if(high-low+1<n){printf("ERROR");return;}
     if(i<j)
     {
            do
            {
              while(tag<key[j] && i<j) j--;
              if(i<j)
              {
                key[i]=key[j];
                i++;
                while(tag>=key[i] && i<j) i++;
                if(i<j)
                {
                  key[j]=key[i];
                  j--;
                }
              }
            }while(i<j);
            key[i]=tag;
            //if(i==n)return;
            if(i-low>n)
                my_nth_element(low,j-1,key,n);
            else if(i-low+1<n)
                my_nth_element(i+1,high,key,n-(i-low+1));
     }
}

//iterator.hpp

#ifndef ITERATOR_H_
#define ITERATOR_H_

#include <cstddef>
using std::ptrdiff_t;

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

template <class T, class Distance> struct input_iterator
{
  typedef input_iterator_tag iterator_category;
  typedef T                  value_type;
  typedef Distance           difference_type;
  typedef T*                 pointer;
  typedef T&                 reference;
};

struct output_iterator
{
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
};

template <class T, class Distance> struct forward_iterator
{
  typedef forward_iterator_tag iterator_category;
  typedef T                    value_type;
  typedef Distance             difference_type;
  typedef T*                   pointer;
  typedef T&                   reference;
};

template <class T, class Distance> struct bidirectional_iterator
{
  typedef bidirectional_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T, class Distance> struct random_access_iterator
{
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
struct iterator
{
  typedef Category  iterator_category;
  typedef T         value_type;
  typedef Distance  difference_type;
  typedef Pointer   pointer;
  typedef Reference reference;
};


template <class Iterator>
struct iterator_traits
{
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};

template <class T>
struct iterator_traits<T*>
{
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T>
struct iterator_traits<const T*>
{
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&)
{
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}

template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type* distance_type(const Iterator&)
{
  return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}

template <class Iterator>
inline typename iterator_traits<Iterator>::value_type* value_type(const Iterator&)
{
    return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

#endif

//improved.hpp
#ifndef ALGORITHM_H
#define ALGORITHM_H
#include <algorithm>
#include "iterator.hpp"
namespace myspace
{

template <class ForwardIterator1, class ForwardIterator2, class T>
inline void my_iter_swap_(ForwardIterator1 a, ForwardIterator2 b, T*)
{
  T tmp = *a;
  *a = *b;
  *b = tmp;
}

template <class ForwardIterator1, class ForwardIterator2>
inline void my_iter_swap(ForwardIterator1 a, ForwardIterator2 b) { my_iter_swap_(a, b, value_type(a)); }

template <class T>
inline const T& median(const T& a, const T& b, const T& c)
{
  if(a < b)
    if(b < c)
      return b;
    else if(a < c)
      return c;
    else
      return a;
  else if(a < c)
    return a;
  else if(b < c)
    return c;
  else
    return b;
}

template <class T, class Compare>
inline const T& median(const T& a, const T& b, const T& c, Compare comp)
{
  if(comp(a, b))
    if(comp(b, c))
      return b;
    else if(comp(a, c))
      return c;
    else
      return a;
  else if(comp(a, c))
    return a;
  else if(comp(b, c))
    return c;
  else
    return b;
}


template <class RandomAccessIterator, class T>
RandomAccessIterator unguarded_partition(RandomAccessIterator first,
                                         RandomAccessIterator last, T pivot)
{
  while(true)
    {
    while(*first < pivot) ++first;
    --last;
    while(pivot < *last) --last;
    if(!(first < last)) return first;
    my_iter_swap(first, last);
    ++first;
  }
}

template <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator unguarded_partition(RandomAccessIterator first,
                                         RandomAccessIterator last, T pivot, Compare comp)
{
  while(true)
    {
    while(comp(*first, pivot)) ++first;
    --last;
    while(comp(pivot, *last)) --last;
    if(!(first < last)) return first;
    my_iter_swap(first, last);
    ++first;
  }
}

template <class RandomAccessIterator, class T>
void _unguarded_linear_insert(RandomAccessIterator last, T value)
{
  RandomAccessIterator next = last;
  --next;
  while (value < *next)
    {
    *last = *next;
    last = next;
    --next;
  }
  *last = value;
}

template <class RandomAccessIterator, class T, class Compare>
void _unguarded_linear_insert(RandomAccessIterator last, T value, Compare comp)
{
  RandomAccessIterator next = last;
  --next;
  while (comp(value , *next))
    {
    *last = *next;
    last = next;
    --next;
  }
  *last = value;
}

//由于字数太多，只好分开贴出来，接上面的文件
template <class RandomAccessIterator, class T>
inline void _linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*)
{
  T value = *last;
  if (value < *first)
    {
    std::copy_backward(first, last, last + 1);
    *first = value;
  }
  else _unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator, class T, class Compare>
inline void _linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp)
{
  T value = *last;
  if (comp(value, *first))
    {
    std::copy_backward(first, last, last + 1);
    *first = value;
  }
  else _unguarded_linear_insert(last, value, comp);
}

template <class RandomAccessIterator>
void _insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    _linear_insert(first, i, value_type(first));
}

template <class RandomAccessIterator, class Compare>
void _insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    _linear_insert(first, i, value_type(first), comp);
}

const size_t threshold = 7;


template <class RandomAccessIterator, class T>
void partial_loop(RandomAccessIterator first, RandomAccessIterator nth,
                  RandomAccessIterator last, T*)
{
  const ptrdiff_t sz = 1 << threshold;
  RandomAccessIterator it = first;
  typename iterator_traits<RandomAccessIterator>::difference_type d = nth - first;
  typename iterator_traits<RandomAccessIterator>::difference_type d2 = last - first;
  while(d > 0)
  {
    if(sz < d2 / d)
    {
      std::partial_sort(first, nth, last);
      break;
    }
    for(; d2 > 3; d2 = last - first)
    {
      RandomAccessIterator cut = unguarded_partition(first, last,
        T(median(*first, *(first + (d2 >> 1)), *(last - 1))));
      if(cut <= nth)
      {
        first = cut;
        d = nth - first;
        break;
      }
      else
        last = cut;
    }
    if(d2 <= 3)
    {
      _insertion_sort(first, last);
      break;
    }
  }
  //std::sort(it, first);
}

template <class RandomAccessIterator, class T, class Compare>
void partial_loop(RandomAccessIterator first, RandomAccessIterator nth,
                  RandomAccessIterator last, T*, Compare cmp)
{
  const ptrdiff_t sz = 1 << threshold;
  RandomAccessIterator it = first;
  typename iterator_traits<RandomAccessIterator>::difference_type d = nth - first;
  typename iterator_traits<RandomAccessIterator>::difference_type d2 = last - first;
  while(d > 0)
  {
    if(sz < d2 / d)
    {
      std::partial_sort(first, nth, last, cmp);
      break;
    }
    for(; d2 > 3; d2 = last - first)
    {
      RandomAccessIterator cut = unguarded_partition(first, last,
        T(median(*first, *(first + (d2 >> 1)), *(last - 1), cmp)));
      if(cut <= nth)
      {
        first = cut;
        d = nth - first;
        break;
      }
      else
        last = cut;
    }
    if(d2 <= 3)
    {
      _insertion_sort(first, last, cmp);
      break;
    }
  }
  //std::sort(it, nth, cmp);
}

template <class RandomAccessIterator>
inline void partial_improved(RandomAccessIterator first,
                                  RandomAccessIterator nth, RandomAccessIterator last)
{
  if(nth == last)
    std::sort(first, last);
  else
    partial_loop(first, nth, last, value_type(first));
}

template <class RandomAccessIterator, class Compare>
inline void partial_improved(RandomAccessIterator first, RandomAccessIterator nth,
                                  RandomAccessIterator last, Compare cmp)
{
  if(nth == last)
    std::sort(first, last, cmp);
  else
    partial_loop(first, nth, last, value_type(first), cmp);
}
#endif

//random.hpp，测试用来产生随机数

#ifndef RANDOM_H_
#define RANDOM_H_
#include <ctime>

class random
{
public:
  explicit random(unsigned long s = 0) : seed(s)
  {
    if (0 == seed) seed = static_cast<unsigned long>(std::time(0));
    randomize();
  }
  void reset(unsigned long s = 0)
  {
    seed = s;
    if (0 == seed) seed = static_cast<unsigned long>(std::time(0));
    randomize();
  }
  unsigned long rand(unsigned long low = 0, unsigned long high = MAX_NUM)
  {
  //returns a random integer in the range [low,high)
  //if low > high, the result would be undefined
    randomize();
    unsigned long distance = high - low;
    if(0 == distance) ++distance;
    return seed % distance + low;
  }
  double real()
  {
  //returns a random real number in the range 0.0 to 1.0
    randomize();
    return (double)(seed) / MAX_NUM;
  }
private:
  unsigned long seed;
  static const unsigned long MAX_NUM = static_cast<unsigned long>(-1);
  void randomize() { seed = (1103515245UL * seed + 123456789UL) % MAX_NUM; }
};

class rand_help
{
  static random r;
public:
  rand_help() {}
  void operator()(unsigned long s) { r.reset(s); }
  unsigned long operator()() const { return r.rand() >> 1; }
  double operator()(double) { return r.real(); }
};
random rand_help:: r;

extern void srandom(unsigned long ns = 0) { rand_help()(ns); } //reset seed
extern unsigned long irand() { return rand_help()(); } //negative numbers disallowed
extern double drand() { return rand_help()(1.0); } //for real numbers

#endif  // RANDOM_H_

//maxk.cpp用来测试
/*
题目：求最大的K个数
随机给定10000000个数，请找出其中最大的K(1<=K<N)个数。测试时统计K=1，10，100，1000，10000，100000，1000000，5000000等8种情况的时间总和（每次测试重新生成数据），花费总时间最少的为冠军。
呵呵，这个题目比较简单，方法也比较多，估计很多人都做过。但要效率足够高还是稍有点难度的。希望总时间耗费能在1秒以内（当然以我的电脑为准啦，嘿嘿）。

函数原型如下：
*/
//测试，不好意思，没有使用题目的函数头。
#include <iostream>
#include <vector>
#include <functional>
#include <windows.h>
//#include <algorithm>
#include "improved.hpp"
#include "random.hpp"

int main()
{
  const size_t E = 10000000, LOOPS = 8; /*1, 10, 100, 1000, 10000, 100000, 1000000, 5000000*/
  const size_t C = 10;
  std::vector<size_t> vnth, v1(E);

    for(size_t i = 1; i < E; i *= 10)
        vnth.push_back(i);
    vnth.push_back(5000000);

  std::cout << "testing is in progress ..." << '\n';
  Sleep(1000);
  DWORD t = 0;
  for(size_t nth = 0; nth < C; ++nth)
  {
    DWORD t1, t2;

    t1 = GetTickCount();
    for(size_t i = 0; i < LOOPS; ++i)
    {
      for(size_t j = 0; j < E; ++j)
        v1[j] = irand();
            myspace::partial_improved(v1.begin(), v1.begin() + vnth[i], v1.end(), std::greater<size_t>());
      //std::nth_element(v1.begin(), v1.begin() + vnth[i], v1.end(), std::greater<size_t>());
    }
    t1 = GetTickCount() - t1;

    t2 = GetTickCount();
    for(size_t i = 0; i < LOOPS; ++i)
      for(size_t j = 0; j < E; ++j)
        v1[j] = irand();
    t2 = GetTickCount() - t2;

    t += t1 - t2;
  }
  std::cout << C << " times tested, on average: " << t / C << " ms\n";
  //std::cout << C << " times tested, nth_element on average: " << t / C << " ms\n";
  system("pause");
}

//partial_improved测试结果如下
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\Chipset>d:

D:\>cd maxk

D:\maxk>g++ -O3 -o maxk maxk.cpp

D:\maxk>maxk
testing is in progress ...
10 times tested, on average: 387 ms
Press any key to continue . . .

D:\maxk>maxk
testing is in progress ...
10 times tested, on average: 386 ms
Press any key to continue . . .

D:\maxk>maxk
testing is in progress ...
10 times tested, on average: 374 ms
Press any key to continue . . .

//nth_element测试结果如下
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\Chipset>d:

D:\>cd maxk

D:\maxk>g++ -O3 -o maxk maxk.cpp

D:\maxk>maxk
testing is in progress ...
10 times tested, nth_element on average: 664 ms
Press any key to continue . . .

D:\maxk>maxk
testing is in progress ...
10 times tested, nth_element on average: 698 ms
Press any key to continue . . .

D:\maxk>maxk
testing is in progress ...
10 times tested, nth_element on average: 684 ms
Press any key to continue . . .

/* 以上用g++ 4.3.2编译,单线程（CPU只用一个核心），操作系统Windows XP Professional SP2英文版，内存DDR667 1GB, CPU Intel(R) Core(TM)2 Duo CPU 2.09GHz Mobile*/

怎么内容都隐藏啊

我很想把这个程序编好,但是时间\耐心\实力不够,不过还是把我自己编的发上来,等待学习高手是怎么实现的.

int Partition(int b[], int low,int high)
{
    //交换顺序表b[low..high]的记录，枢轴记录到位，并返回其所在位置，此时
    //在它之前(后)的记录均不大(小)于它
    int pivotkey = b[low]; //用pivotkey作枢轴记录
    while(low < high)    //从表的两端交替地向中间扫描 
    {
        while(low < high && b[high] >= pivotkey)
        {
            --high;
        }
        b[low]=b[high];//将比枢轴记录小的记录移到低端

        while(low < high && b[low] <= pivotkey)
        {
            ++low;
        }
        b[high]=b[low]; //将比枢轴记录大的记录移到高端

    }

    b[low]=pivotkey;  //枢轴记录到位
    return low;                //返回枢轴记录
}

void QSort(int b[],int low,int high)
{    
    //对顺序表中的子序列b[low..high]作快速排序    
    if(low < high)         //长度大于1
    {
        int pivotloc = Partition(b,low,high); //将L.elemword[low..high]一分为二
        QSort(b, low, pivotloc-1);        //对低子表递归排序,pivotloc是枢轴位置
        QSort(b, pivotloc+1, high);       //对高子表递归排序
    }    
//    printf("low==%d\n", low);
}


void MaxK(int a[], int n, int k, int result[])
{
    if(k < 10000)
    {
        // 最小值 以及 最小值的位置
        int min = a[0];
        int min_pos = 0;

        for(int i = 0; i < k; i++)
        {
            result[i] = a[i];

            // min 记录 前k个数中 最小的数
            if(result[i] < min)
            {
                min = result[i];
                min_pos = i;
            }
        }

        for( ; i < n; i++)
        {
            if(a[i] > min)
            {
                result[min_pos] = a[i];
                min = a[i];

                // 重新查找最小值 及其 位置
                for(int j = 0; j < k; j++)
                {    
                    // min 记录 前k个数中 最小的数
                    if(result[j] < min)
                    {
                        min = result[j];
                        min_pos = j;
                    }
                }
            }
        }
    }
    else
    {
        QSort(a, 0, n-1);

        for(int i = 0; i < k; i++)
        {
            result[i] = a[i];
    //        printf("i==%d\n", i);
        }
    }
}