NOIP学习小站STL提供的算法几乎都在algorithm头文件中（还有一些在numeric、functional两个头文件中），在竞赛中合理使用这些函数，可以提高编码的效率，并且执行效率往往比自己写的算法更高效！
使用时要注意这些函数的工作方式，有些函数是会修改容器的内容，例如用于排序的sort函数；有些函数并不修改内容，而是返回值，例如判断是否有序的is_sorted函数。
先来看排序。STL中提供了丰富的排序或者与排序相关的函数，可以高效实现排序操作。
一、排序函数sort
前面已经详细介绍过sort函数的使用，sort函数排序的对象往往是数组或者vector。这里再总结一下sort函数的用法：
1.简单排序
sort函数前两个参数指定了排序开始位置和结束位置，两个参数均为指针类型（普通指针或者迭代器），需要注意的是指定的区域左闭右开，也就是不包含第二个参数指向的元素。其实STL中涉及到两个参数指定一段区域时，几乎都遵循左闭右开的规则。sort函数默认按照非降序（升序）排序，sort函数排序后，数组或者容器中的元素会按照排序规则重新排列。
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<deque>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
int a[10] = {6,4,5,9,1,3,8,7,2,0};
//调用vector/list/deque构造函数，容器初始数据来源于数组a
vector<int> ve(a,a+10);
list<int> li(a,a+10);
deque<int> de(a,a+10);
//sort对数组排序
sort(a,a+10);
list_elements(a,a+10);
//sort对vector排序
sort(ve.begin(),ve.end());
list_elements(ve.begin(),ve.end());
//使用反向迭代器排序（实现降序排序）
sort(ve.rbegin(),ve.rend());
list_elements(ve.begin(),ve.end());
//sort函数不能对list排序
//不过list有专门的成员函数sort可以实现对list元素排序
li.sort();
list_elements(li.begin(),li.end());
//sort对deque排序
sort(de.begin(),de.end());
list_elements(de.begin(),de.end());
//使用反向迭代器排序（实现降序排序）
sort(de.rbegin(),de.rend());
list_elements(de.begin(),de.end());
return 0;
}2.自定义排序规则
可以通过第三个参数指定比较函数来设置sort函数的排序规则，最简单的方法是使用less<T>()和greater<T>()两个仿函数：
sort(a,a+10,greater<int>()); sort(ve.begin(),ve.end(),less<int>()); li.sort(greater<int>()); sort(de.begin(),de.end(),greater<int>());
还可以自定义比较函数，或者借助结构体（或类）自定义类似于 less<T>()和greater<T>()的仿函数，来实现自定义排序：
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<deque>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
//自定义用于排序的比较函数
bool mycmp(const int &x,const int &y){
return x>y;
}
//自定义实现仿函数的结构体
struct cmp{
bool operator() (const int &x,const int &y){
return x>y;
}
};
int main()
{
int a[10] = {6,4,5,9,1,3,8,7,2,0};
//调用vector/list/deque构造函数，初始数据来源于数组a
vector<int> ve(a,a+10);
list<int> li(a,a+10);
deque<int> de(a,a+10);
//使用自定义比较函数指定排序规则
sort(a,a+10,mycmp);
list_elements(a,a+10);
//使用自定义比较函数指定排序规则
sort(ve.begin(),ve.end(),mycmp);
list_elements(ve.begin(),ve.end());
//使用自定义仿函数指定排序规则
li.sort(cmp());
list_elements(li.begin(),li.end());
//使用自定义仿函数指定排序规则
sort(de.begin(),de.end(),cmp());
list_elements(de.begin(),de.end());
return 0;
}3.对结构体排序
对于元素是结构体的数组或者容器，可以重载结构体运算符，或者指定比较函数来实现排序：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct Point{
int x,y;
Point(int x,int y){
this->x = x;
this->y = y;
}
};
//重载<运算符
bool operator <(const Point& a,const Point& b){
return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
//重载>运算符
bool operator >(const Point& a,const Point& b){
return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y;
}
void print(vector<Point> &v){
for(size_t i=0;i<v.size();i++)
cout<<"("<<v[i].x<<","<<v[i].y<<") ";
cout<<endl;
}
bool mycmp(const Point &a,const Point &b){
return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
struct cmp{
bool operator()(const Point &a,const Point &b){
return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y;
}
};
int main(){
vector<Point> ve;
ve.push_back(Point(2,2));
ve.push_back(Point(1,1));
ve.push_back(Point(1,2));
ve.push_back(Point(-3,2));
ve.push_back(Point(2,1));
ve.push_back(Point(0,0));
print(ve);
//因为Point重载了<运算符，所以可以使用默认的less<Point>()排序
sort(ve.begin(),ve.end());
print(ve);
//因为Point重载了>运算符，所以可以使用greater<Point>()排序
sort(ve.begin(),ve.end(),greater<Point>());
print(ve);
//使用自定义比较函数排序
sort(ve.begin(),ve.end(),mycmp);
print(ve);
//使用自定义仿函数排序
sort(ve.begin(),ve.end(),cmp());
print(ve);
return 0;
}4.稳定排序
sort()函数排序是不稳定排序，如果要求排序结果稳定，可以使用stable_sort()函数，使用方法与sort函数一致。当然也可以通过结构体改造要参加排序的元素，在结构体中记录下原始数据的出现序号来实现稳定排序。具体可参考：稳定排序与不稳定排序
二、判断是否有序is_sorted
可以使用is_sorted()函数来判断一个区域内的元素是否有序，使用时参数和sort函数一致。不过这个函数在Dev C++中无法使用，在标准环境中可以正常使用（竞赛NOILinux2.0测试过）。
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(const int &x,const int &y){
return abs(x)<abs(y);
}
int main()
{
//数组元素升序排列
int a[5] = {-2,-1,0,1,5};
//判断是否有序（默认按照升序规则判断）
if(is_sorted(a,a+5)) cout<<"sorted"<<endl;
else cout<<"unsorted"<<endl;
//判断是否有序（指定greater<int>()，按照降序规则判断）
if(is_sorted(a,a+5,greater<int>())) cout<<"sorted"<<endl;
else cout<<"unsorted"<<endl;
sort(a,a+5,greater<int>());
if(is_sorted(a,a+5,greater<int>())) cout<<"sorted"<<endl;
else cout<<"unsorted"<<endl;
//判断是否有序（指定按照cmp函数比较规则判断）
if(is_sorted(a,a+5,cmp)) cout<<"sorted"<<endl;
else cout<<"unsorted"<<endl;
sort(a,a+5,cmp);
if(is_sorted(a,a+5,cmp)) cout<<"sorted"<<endl;
else cout<<"unsorted"<<endl;
return 0;
}
三、部分排序partial_sort
假设我们想找出存放在数组中的100000个数据中最小的50个数据，如果使用sort函数将所有数据全部排序后再取前50个，效率是很低的。这个时候可以使用部分排序函数partial_sort，这里可以使用：partial_sort(a,a+50,a+100000)，第1个参数begin和第3个参数end与sort函数的前两个参数对应，表示在 \( [begin,end) \) 区间内排序，第2个参bound就是排序的中间点，函数执行后，\([begin,bound) \) 会包含 \( [begin,end) \) 中最小的 \( bound- begin\) 个元素，且 \( [begin, bound) \) 有序，但不保证 \( [bound,end) \) 有序。因为partial_sort函数内部进行了优化，对于本例，排序过程中只要已经实现了最小的50个数据有序存放在了a[0]~a[49]中，部分排序就结束了，比起sort全排序，效率大大提高。同样地， partial_sort 还可以有第4个参数，像sort函数一样指定排序的比较函数。
n位选手参加比赛，我们想输出前m名选手的成绩，这是典型的部分排序应用场景：
#include<iostream>
#include<algorithm>
using namespace std;
int a[1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
partial_sort(a,a+m,a+n,greater<int>());
for(int i=0;i<m;i++) cout<<a[i]<<" ";
return 0;
}四、求第n小的数nth_element
假设我们想找出存放在数组中的100000个数据中第n小的数（最小的是第0小的数），为了提高效率，可以使用nth_element函数：nth_element(a,a+n,a+100000)。执行函数后，第n小的数存放在a[n]中，并且a[0] ～ a[n-1]均不大于a[n]，a[n+1]～a[99999]均不小于a[n]。 同样地，nth_element还可以有第4个参数，像sort函数一样指定排序的比较函数。
n位选手参加比赛，要找出第m名选手的成绩（这里规定最好成绩是第1名，注意与前面描述的从0计数的不同），可以使用nth_element函数来实现：
#include<iostream>
#include<algorithm>
using namespace std;
int a[1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
nth_element(a,a+m-1,a+n,greater<int>());
cout<<a[m-1]<<endl;
return 0;
}五、分组函数partition
partition函数对指定范围内元素重新排列，这里需要指定一个判断函数function，每个元素作为判断函数function的参数会返回bool值， partition函数把结果为true的元素放在结果为false的元素之前。用法： partition(begin,end,function);，函数的返回值是一个指针（或迭代器）bound。函数执行后，整个区间\([begin,end)\)被分成两个部分： \([begin,bound) \) （这部分所有元素经过函数function处理结果都是true）和\([bound,end) \) （ 这部分所有元素经过函数function处理结果都是false）。
#include<iostream>
#include<algorithm>
using namespace std;
bool judge(const int &n){
return n%2==0;
}
int main()
{
int a[10];
for(int i=0;i<10;i++) a[i] = i+1;
int *p = partition(a,a+10,judge);
int *it = a;
while(it!=p) cout<<*it<<" ",it++;
cout<<endl;
while(it!=a+10) cout<<*it<<" ",it++;
return 0;
}上面程序，数组所有元素原始值为{1,2,3,4,5,6,7,8,9,10}，经过partition函数处理后数组所有元素为{10,2,8,4,6,5,7,3,9,1}，函数的返回值其实是a+5。可见 partition只是将数组分成了两个部分，处理后的形成的两个部分并不保证组内元素有序排列，并且组内的元素也不保证保留开始的相对位置。
如果想分组后两组的元素在组内维持原先的相对位置，可以使用stable_partition函数，方法和partition函数相同，两者的区别有点类似于stable_sort和sort的区别。还是上面的程序，如果使用stable_partition函数，处理后数组所有元素为{2,4,6,8,10,1,3,5,7,9}。
六、合并并排序merge
merge函数用于将两个原本有序的容器（排序方式一致）合并到一个新容器中，并确保合并后新容器中的元素也有序：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
vector<int> a;
int sa[5] = {3,7,9,2,4};
for(int i=0;i<5;i++) a.push_back(sa[i]);
vector<int> b;
int sb[5] = {10,5,8,1,6};
for(int i=0;i<5;i++) b.push_back(sb[i]);
//使用merge合并的前提是要合并的两个序列都有序，并且排序方式相同
sort(a.begin(),a.end());
sort(b.begin(),b.end());
list_elements(a.begin(),a.end());
list_elements(b.begin(),b.end());
//用于保存合并结果的c，需要确保其长度能放下合并结果
vector<int> c(a.size()+b.size());
//将原本有序的[a.begin(),a.begin())和[b.begin(),b.begin())合并并排序
//合并结果从c.begin()开始存储
merge(a.begin(),a.end(),b.begin(),b.end(),c.begin());
list_elements(c.begin(),c.end());
sort(a.begin(),a.end(),greater<int>());
sort(b.begin(),b.end(),greater<int>());
list_elements(a.begin(),a.end());
list_elements(b.begin(),b.end());
vector<int> d(a.size()+b.size());
merge(a.begin(),a.end(),b.begin(),b.end(),d.begin(),greater<int>());
list_elements(d.begin(),d.end());
return 0;
}七、逆序reverse
reverse函数用来将指定区间的所有元素逆序排列；reverse_copy函数将逆序后的结果拷贝到另一个容器，原容器内容不变：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
int a[10],b[10];
for(int i=0;i<10;i++) a[i] = i+1;
//调用vector构造函数，容器初始数据来源于数组a
vector<int> ve(a,a+10);
reverse(a,a+10);
list_elements(a,a+10);
reverse(ve.begin(),ve.end());
list_elements(ve.begin(),ve.end());
cout<<endl;
//reverse_copy函数将[a,a+10)逆序结果拷贝到b指针开始的区域
//数组a的内容不会改变
reverse_copy(a,a+10,b);
list_elements(a,a+10);
list_elements(b,b+10);
return 0;
}八、旋转元素rotate
函数rotate(begin,newbegin,end);将区间\([begin,end)\)内的元素进行旋转，执行后原来的*newbegin成为新的第0元素； rotate _copy函数将旋转后的结果拷贝到另一个容器，原容器内容不变：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main(){
int a[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve(a,a+10);
list_elements(a,a+10);
//rotate函数将[a,a+10)旋转，旋转后原来的a+3成为第0个元素
rotate(a,a+3,a+10);
list_elements(a,a+10);
rotate(ve.begin(),ve.begin()+3,ve.end());
list_elements(ve.begin(),ve.end());
int b[10];
//rotate_copy函数将[a,a+10)旋转结果拷贝到b指针开始的区域
//数组a的内容不会改变
rotate_copy(a,a+3,a+10,b);
list_elements(a,a+10);
list_elements(b,b+10);
return 0;
}九、随机排列random_shuffle
random_shuffle函数可以将指定的区域内的元素随机打乱重新排列：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[10];
for(int i=0;i<10;i++) a[i] = i+1;
for(int i=0;i<10;i++) cout<<a[i]<<" ";
cout<<endl;
random_shuffle(a,a+10);
for(int i=0;i<10;i++) cout<<a[i]<<" ";
cout<<endl;
return 0;
}