求解，c++ 关于nth_element()的问题，具体详情请看下面？

Question

#include<iostream>#include<cstdlib>#include<vector>#include<string>#include<algorithm>using namespace std;//typedeftypedef int I;typedef char C;typedef int ARR[10];//宏定义#define N 3#define X(a,b) (((a)+(b))*3)//自定义函数声明void f1();void output(const string &);void f2();//主函数int main(int argc,char * argv[]){f1();cout<<endl;f2();cout<<endl;cout<<argc<<ends<<* argv<<endl;system("pause");return 0;}//自定义函数 在output函数里不能改变x的值，因为constvoid output(const string & x){cout<<x<<endl;}void f1(){//定义vector对象vector<string> strVect1;vector<string> strVect2;//push_back()strVect1.push_back("Sunday");strVect1.push_back("Monday");strVect1.push_back("Over");strVect1.push_back("Wednesday");strVect2.push_back("Monday");strVect2.push_back("Sunday");strVect2.push_back("Over");strVect2.push_back("Saturday");//sort()sort(strVect1.begin(),strVect1.end());sort(strVect2.begin(),strVect2.end());cout<<"Vect1:"<<endl;//for_each()for_each(strVect1.begin(),strVect1.end(),output);cout<<endl;cout<<"Vect2:"<<endl;for_each(strVect2.begin(),strVect2.end(),output);cout<<endl;cout<<"bool result=includes(strVect1.begin(),strVect1.end(),strVect2.begin(),strVect2.begin()+2):"<<endl;//includes()bool result=includes(strVect1.begin(),strVect1.end(),strVect2.begin(),strVect2.begin()+2);if(result)cout<<"result:OK"<<endl;elsecout<<"result:ERROR"<<endl;}void f2(){//定义vector对象vector<I> intVect;//push_back()intVect.push_back(7);intVect.push_back(3);intVect.push_back(9);intVect.push_back(1);intVect.push_back(0);intVect.push_back(6);intVect.push_back(5);cout<<"intVect"<<endl;//定义iterator对象vector<I>::iterator it;for(it=intVect.begin();it!=intVect.end();it++)cout<<* it<<ends;cout<<endl;//nth_element()nth_element(intVect.begin(),intVect.begin()+3,intVect.end());for(it=intVect.begin();it!=intVect.end();it++)cout<<* it<<ends;cout<<endl;}

Answer 1

nth_element()是一个典型的部分排序算法。

它的第1和第3个参数，定义的是排序的范围（或则说nth_element这个算法或函数的作用范围），称着first和last，是一个[ )区间。在你的例子，分别对应那个vector的begin和end；

第2个参数的意思是：如果一个序列的first和last半包含的范围内，如果这个序列被排序了，那个第n个位置上的元素应该是什么。---- 白话的解释就是：如果给你一堆数据，我想看看中间值是多少，第2大的数是什么？ 你该如何解决呢？ 全排序当然可以，但如果数据多，效率也许就差了。这是只有部分排序即可，也就是说只有这第n个的位置被排对了，那么其他的就不管了，排序就可以解释了。-- 这是nth_element的应用意义。

以你的代码为例：你的第2个参数是intVect.begin()+3，就是想看看intVect这个序列中，【如果排序的话】，它的第4个应该是多少？这个intVect如果全排序，应该是：

0 1 3 5 6 7 9，

因此nth_element在确保第4个元素=5的时候，就停止排序了。 因此你后面输出intVect的值是：

1 0 3 5 9 6 7

就是第4个=5后，当时intVect的值。

一般在nth_element()后，都有一个类似这样的语句：

12	nth_element(intVect.begin(),intVect.begin()+3,intVect.end());cout << intVect[3]<< endl;

给你添加一点代码，体会一下nth_element的概念，它其实可以有【第4个参数】的：

1234	nth_element(intVect.begin(), intVect.begin() + intVect.size()/2, intVect.end());cout << "The median is " << intVect[intVect.size()/2] << endl;nth_element(intVect.begin(), intVect.begin() + 1, intVect.end(), greater<int>());cout << "The second largest is " << intVect[1] << endl;

之后在看看intVect的输出：

123	The median is 5The second largest is 79 7 6 5 3 1 0