这个函数的意义是，对于序列a[0:len-1]将第n大的数字，排在a[n],同时a[0:n-1]都小于a[n],a[n+1:]都大于a[n],但a[n]左右的这两个序列不一定有序。该算法的平均复杂度为线性。
但是今天看c++ primer第三版(中文版)附录中关于nth_element的注解，发现是不对，而且句子也有点不通，困扰了好久。
再经过测试，发现vs2005的stl实现做了点优化，在序列数小于32时，直接全排列，而大于或等于32时，才会调用线性的算法。g++没有此优化。
测试程序如下:
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 using namespace std;
5
6 bool myfunction (int i,int j) { return (i<j); }
7
8 int main () {
9 vector<int> myvector;
10 vector<int>::iterator it;
11
12 // set some values:
13 for (int i=1; i<32; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
14
15 random_shuffle (myvector.begin(), myvector.end());
16 for (it=myvector.begin(); it!=myvector.end(); ++it)
17 cout << " " << *it;
18
19 it = myvector.begin() + 6;
20 cout << " " <<endl<< *it << endl;
21 // using default comparison (operator <):
22 nth_element (myvector.begin(), myvector.begin()+6, myvector.end());
23
24 // using function as comp
25 //nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);
26
27 // print out content:
28 cout << "myvector contains:";
29 for (it=myvector.begin(); it!=myvector.end(); ++it)
30 cout << " " << *it;
31
32 cout << endl;
33
34 return 0;
35 }
posted on 2010-10-06 11:57
高峰 阅读(1036)
评论(0) 编辑 收藏 引用