排序相关算法

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;
}