#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <time.h>

using namespace std;

int Random(int low=0, int high=RAND_MAX)
{
    return rand()%(high-low+1)+low;
}


bool exam(int x)
{
    return x>=60;
}
   
int main()
{
    int i;
    vector<int> a;
    vector<int> b;
    srand((unsigned)time(0));
    for (i=0; i<10; i++)
        a.push_back(Random(1,100));
    copy(a.begin(),a.end(),ostream_iterator<int>(cout,","));
    cout<< endl;

    b=a;
    sort(b.begin(), b.end());
    cout<< "sort: ";
    copy(b.begin(),b.end(),ostream_iterator<int>(cout,","));
    cout<< endl;

    b=a;
    sort(b.begin(), b.end(), greater<int>());
    cout<< "sort(greater): ";
    copy(b.begin(),b.end(),ostream_iterator<int>(cout,","));
    cout<< endl;

    b=a;
    nth_element(b.begin(), b.begin()+3, b.end());    // 为什么结果和sort一样？
    cout<< "nth_element: ";
    copy(b.begin(),b.end(),ostream_iterator<int>(cout,","));
    cout<< endl;

    b=a;
    partial_sort(b.begin(), b.begin()+3, b.end());
    cout<< "partial_sort: ";
    copy(b.begin(),b.end(),ostream_iterator<int>(cout,","));
    cout<< endl;

    vector<int> c(3);
    b=a;
    partial_sort_copy(b.begin(), b.end(), c.begin(), c.end());
    cout<< "partial_sort_copy: ";
    copy(c.begin(),c.end(),ostream_iterator<int>(cout,","));
    cout<<"   b: ";
    copy(b.begin(),b.end(),ostream_iterator<int>(cout,","));
    cout<< endl;

    b=a;
    partition(b.begin(), b.end(), exam);
    cout<< "partition: ";
    copy(b.begin(),b.end(),ostream_iterator<int>(cout,","));
    cout<< endl;
   
    return 0;
}

应该不一样吧。
你运行的结果是什么？发一个上来看看。

下面是我的一次运行结果：


[ 本帖最后由 pangding 于 2009-10-8 10:51 编辑 ]

4,70,49,62,32,32,83,38,2,72,
sort: 2,4,32,32,38,49,62,70,72,83,
sort(greater): 83,72,70,62,49,38,32,32,4,2,
nth_element: 2,4,32,32,38,49,62,70,72,83,     // 一样啊，郁闷
partial_sort: 2,4,32,70,62,49,83,38,32,72,
partial_sort_copy: 2,4,32,   b: 4,70,49,62,32,32,83,38,2,72,
partition: 72,70,83,62,32,32,49,38,2,4,
list::sort:  2,4,32,32,38,49,62,70,72,83,
Press any key to continue

多试几次每次都一样吗？如果是那样的话，你那个库用的算法就不太好

确实一样啊，我运行了5次，发现nth_element和sort按升序排列得到的结果是一样的

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

……

// nth_element() and its auxiliary functions.  

template <class _RandomAccessIter, class _Tp>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                   _RandomAccessIter __last, _Tp*) {
  while (__last - __first > 3) {
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1))));
    if (__cut <= __nth)
      __first = __cut;
    else 
      __last = __cut;
  }
  __insertion_sort(__first, __last);
}

template <class _RandomAccessIter>
inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                        _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
                 _LessThanComparable);
  __nth_element(__first, __nth, __last, __VALUE_TYPE(__first));
}

这是一种 nth_element 的实现。从中我们可以看出，它使用的是一种很类似快排的方法，对容器进行排序。但它不全部排序，只要排序可以确定第n大的元素是多少就停止。理论上，在效率方面它比全排一个容器要好很多。 当然由于我只给了部分代码，你可能无法直接使用。比如 __unguarded_partition 和 __insertion_sort 以及一些宏的定义我没给。你要有兴趣可以自己去找相关的实现。或者你可以根据这个算法，自己实现一个来看看效果~