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

partial_sort(first , middle , last)排序算法模板函数，”partial“意为”部分“，该排序算法指的是在指定区间[first , last)按排序规则找出前（middle-first)个元素并存放进排序区间[first , middle)中。

使用partial_sort(first , middle , last)时需要包含头文件<algorithm>。

使用partial_sort()函数进行排序也有以下三点要求：

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

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

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

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

/*此处first意为排序的起始范围，middle意为有效排序的终止位置，last意为排序的终止范围，三者可为数组指针或迭代器，有效排序区间为[first,middle)，未排序区间为[middle,last)*/ 
   partial_sort(first , middle , last);//默认是升序排序
   partial_sort(first , middle , last , cmp());//额外增加仿函数cmp进行自定义比较

我们通过partial_sort()分别对普通数组和vector容器进行基础数据排序和自定义数据排序。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>//包含算法头文件！
#include<iterator> //使用迭代器函数进行切割，复习前面知识 next(it,n) 
/* 对普通数组和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;
}
};
/*--基本数据类型&&默认升序排序&&排序区间为[0,3)--*/ 
void test1()
{
cout << "---------------------------------------------\n" ;
cout<< "处理基本数据类型，排序区间为[0,3)且遵循默认排序规则：\n";
   cout << "无序状态：{2,5,1,4,3}\n" ; 
   int a[]={2,5,1,4,3};
   vector<int> v{2,5,1,4,3};
   partial_sort(&a[0],&a[3],&a[4]+1);//数组 
   partial_sort(v.begin(),next(v.begin(),3),v.end());//vector容器 
   cout << "a数组："; 
   for(int i=0;i<5;++i)cout << a[i]  << " ";
   cout << '\n'; 
   cout << "vector容器："; 
   for(auto i=v.begin();i!=v.end();++i)cout << *i  << " ";
   cout << '\n';
   cout << "---------------------------------------------\n" ;
} 
/*--基本数据类型&&自定义降序排序&&排序区间为[0,3)--*/ 
void test2()
{
cout << "---------------------------------------------\n" ;
cout<< "处理基本数据类型，排序区间为[0,3)且自定义降序排序：\n";
   cout << "无序状态：{2,5,1,4,3}\n" ; 
   int a[]={2,5,1,4,3};
   vector<int> v{2,5,1,4,3};
   partial_sort(&a[0],&a[3],&a[4]+1,cmp_basic());//数组 
   partial_sort(v.begin(),next(v.begin(),3),v.end(),cmp_basic());//vector容器 
   cout << "a数组："; 
   for(int i=0;i<5;++i)cout << a[i]  << " ";
   cout << '\n'; 
   cout << "vector容器："; 
   for(auto i=v.begin();i!=v.end();++i)cout << *i  << " ";
   cout << '\n';
   cout << "---------------------------------------------\n" ;
} 
/*--自定义数据类型&&默认升序排序&&排序区间为[0,3)--*/ 
void test3()
{
cout << "---------------------------------------------\n" ;
cout<< "处理自定义数据类型，排序区间为[0,3)且遵循默认排序规则：\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};
   vector<dotcpp_user> v{u2,u5,u1,u4,u3};
   partial_sort(&a[0],&a[3],&a[4]+1);//数组 
   partial_sort(v.begin(),next(v.begin(),3),v.end());//vector容器 
   cout << "a数组："; 
   for(int i=0;i<5;++i)cout << a[i].name  << " ";
   cout << '\n'; 
   cout << "vector容器："; 
   for(auto i=v.begin();i!=v.end();++i)cout << i->name << " ";
   cout << '\n';
   cout << "---------------------------------------------\n" ;
} 
/*--自定义数据类型&&自定义降序排序&&排序区间为[0,3)--*/ 
void test4()
{
cout << "---------------------------------------------\n" ;
cout<< "处理自定义数据类型，排序区间为[0,3)且自定义降序排序：\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};
   vector<dotcpp_user> v{u2,u5,u1,u4,u3};
   partial_sort(&a[0],&a[3],&a[4]+1,cmp_diy());//数组 
   partial_sort(v.begin(),next(v.begin(),3),v.end(),cmp_diy());//vector容器 
   cout << "a数组："; 
   for(int i=0;i<5;++i)cout << a[i].name  << " ";
   cout << '\n'; 
   cout << "vector容器："; 
   for(auto i=v.begin();i!=v.end();++i)cout << i->name << " ";
   cout << '\n';
   cout << "---------------------------------------------\n" ;
} 
int main(){
system("title dotcpp.com");
    test1();
    test2();
    test3();
    test4();
    return 0;
}

编译结果如下：

观察输出结果，我们成功在5个元素中按照指令要么找出前3个最大的数，要么找出前三个最小的数，并进行排序放在有效排序区间[0 , 3)中。

总结：对于partial_sort(first , middle , last)，理解它的功能最重要。该函数模板的功能是在指定区间[first , last)按排序规则找出前（middle-first)个元素并存放进排序区间[first , middle)中，该类排序算法主要运用于比赛排名和资源调度中，把重要的元素”置顶“，才能做出更好的决策！