C++ STL 排序算法std::nth_element()函数入门

nth_element(beg , pos , end)排序算法模板函数，”nth“意为”第几个“，该排序算法指的是在指定区间[beg , end)按排序规则找出位置在pos上的元素是谁并进行填充，此函数会打乱原有序列。

使用nth_element(beg , pos , end)时需要包含头文件<algorithm>。

使用nth_element(beg , pos , end)函数进行排序也有以下三点要求：

1. 由于nth_element(beg , pos , end)对容器进行排序时，需要对元素进行随机访问，所以要求排序容器为随机访问迭代器，也就是array容器、vector容器、deque容器，C风格数组（将指针作迭代器使用）。

2. 如果元素为自定义数据，由于nth_element(beg , pos , end)默认是升序排序，所以要求自定义数据重载“<”比较运算符。

3. 如果元素为自定义数据，由于nth_element(beg , pos , end)需要对元素进行高效移动，所以需要自定义数据提供移动构造函数和移动赋值运算符。

nth_element(beg , pos, end)排序有两个重载函数，下面我们通过代码向读者简要展示其参数和功能：

 /*此处beg意为排序的起始范围，pos意为求取排序后元素的位置(基于0-based)，end意为排序的终止范围，三者皆可为数组指针或迭代器*/ 
   nth_element(beg , pos , end);//默认是升序排序
   nth_element(beg , pos , end , cmp());//额外增加仿函数cmp进行自定义比较

我们通过nth_element(beg , pos, end)分别求出普通数组和vector容器的第三个元素：

#include<iostream>
#include<vector>
#include<string>
#include<iterator> //使用迭代器函数进行切割，复习前面知识 next(it,n) 
#include<algorithm>//包含算法头文件！
/* nth_element(beg , pos , end)分别求出普通数组和vector容器排序后的第二个元素 */
using namespace std;
/*自定义数据*/ 
struct dotcpp_user
{
bool operator<(const dotcpp_user&u)const
{
return grade<u.grade;
}
string name;//姓名 
int age;//年龄 
int grade;//做题个数 
bool is_online;//是否在线 
};
/*基础数据类型仿函数*/ 
struct cmp_basic
{
bool operator()(const int &a,const int &b)const
{
return a>b;
}
};
/*自定义数据类型仿函数*/ 
struct cmp_diy
{
bool operator()(const dotcpp_user &u1,const dotcpp_user &u2)const
{
return u1.grade>u2.grade;
}
};
/*--基本数据类型&&默认升序排序--*/ 
void test1()
{
cout << "---------------------------------------------\n" ;
cout<< "处理基本数据类型，遵循默认排序规则：\n";
   cout << "无序状态：{2,5,1,4,3}\n" ; 
   int a[]={2,5,1,4,3};
   nth_element(&a[0],&a[1],&a[4]+1);
   vector<int> v{2,5,1,4,3};
   nth_element(v.begin(),next(v.begin(),1),v.end());
   cout << "a数组的第2个元素是：【"<<a[1]<< "】\n"; 
   cout << "vector容器的第2个元素是：【"<< *next(v.begin(),1)<< "】\n"; 
   cout << "---------------------------------------------\n" ;
} 
/*--基本数据类型&&自定义降序排序--*/ 
void test2()
{
cout << "---------------------------------------------\n" ;
cout<< "处理基本数据类型，自定义降序排序：\n";
   cout << "无序状态：{2,5,1,4,3}\n" ; 
   int a[]={2,5,1,4,3};
   nth_element(&a[0],&a[1],&a[4]+1,cmp_basic());
   vector<int> v{2,5,1,4,3};
   nth_element(v.begin(),next(v.begin(),1),v.end(),cmp_basic());
   cout << "a数组的第2个元素是：【"<<a[1]<< "】\n"; 
   cout << "vector容器的第2个元素是：【"<< *next(v.begin(),1)<< "】\n"; 
   cout << "---------------------------------------------\n" ;
} 
/*--自定义数据类型&&默认升序排序--*/ 
void test3()
{
cout << "---------------------------------------------\n" ;
cout<< "处理自定义数据类型，遵循默认排序规则：\n";
   cout << "无序状态：{2,5,1,4,3}\n" ; 
   /*创建复杂对象*/
dotcpp_user u1{"user01",18,100,true};
dotcpp_user u2{"user02",18,200,true};
dotcpp_user u3{"user03",18,300,true};
dotcpp_user u4{"user04",18,400,true};
dotcpp_user u5{"user05",18,500,true};
   dotcpp_user a[]={u2,u5,u1,u4,u3};
   nth_element(&a[0],&a[1],&a[4]+1);
   vector<dotcpp_user> v{u2,u5,u1,u4,u3};
   nth_element(v.begin(),next(v.begin(),1),v.end());
   cout << "a数组的第2个元素是：【"<<a[1].name<< "】\n"; 
   cout << "vector容器的第2个元素是：【"<< next(v.begin(),1)->name<< "】\n"; 
   cout << "---------------------------------------------\n" ;
} 
/*--自定义数据类型&&自定义降序排序--*/ 
void test4()
{
cout << "---------------------------------------------\n" ;
cout<< "处理自定义数据类型，自定义降序排序：\n";
   cout << "无序状态：{2,5,1,4,3}\n" ; 
   /*创建复杂对象*/
dotcpp_user u1{"user01",18,100,true};
dotcpp_user u2{"user02",18,200,true};
dotcpp_user u3{"user03",18,300,true};
dotcpp_user u4{"user04",18,400,true};
dotcpp_user u5{"user05",18,500,true};
  dotcpp_user a[]={u2,u5,u1,u4,u3};
   nth_element(&a[0],&a[1],&a[4]+1,cmp_diy());
   vector<dotcpp_user> v{u2,u5,u1,u4,u3};
   nth_element(v.begin(),next(v.begin(),1),v.end(),cmp_diy());
   cout << "a数组的第2个元素是：【"<<a[1].name<< "】\n"; 
   cout << "vector容器的第2个元素是：【"<< next(v.begin(),1)->name<< "】\n"; 
   cout << "---------------------------------------------\n" ;
} 
int main(){
system("title dotcpp.com");
    test1();
    test2();
    test3();
    test4();
    return 0;
}

编译结果如下：

观察输出结果，升序排序下，第二个元素是2；降序排序下，第二个元素是4，完全符合预给指令。

总结：对于nth_element(beg , pos, end)，理解它的功能最重要。该函数模板的功能是在指定区间[beg , end)按排序规则找出位置在pos上的元素是谁并进行填充，此函数会打乱原有序列，该类排序算法主要运用于求取中位数，分析数据的总体水平。