sort的使用技巧——酷町堂学员张瑀涵分享

sort的使用技巧

By 张瑀涵

 

2012年,CCF正式宣布允许C++选手在CCF NOI系列赛事中使用STL(Standard Template Library ,标准模板库 )。这个消息导致大量Pascal选手转型为C++选手。

STL里有许多实用的函数,在此我不多说。今天,我专门讲STL里最有用的一个函数—sort。

 

What is sort?

sort是一个排序函数,它接受两至三个参数,使用时需要调用头文件#include<algorithm>。

我们先举个例子:

  1. sort(a+1,a+1+n)

设a为一个数组,n为a数组的长度,第一个参数中a+1表示以a数组的第一个数为排序区间下界,第二个参数中a+1+n表示以a数组的最后一个数为排序区间下界。

Q:这里的排序之后数组是什么顺序?

A:如果没有外界的设定,sort的排序顺序自动为从小到大。

Q:如何设定数组以从大到小的顺序排序?

A:别急,下面就会讲到——

 

2.sort(a+1,a+1+n,cmp)

这就涉及到定义排序顺序的问题了。 cmp是一个bool型函数,它的返回值依据你的排序顺序。

从小到大的cmp函数(虽然没什么用):

bool cmp(const 数据类型& 变量名,const 数据类型& 变量名){

return a<b;

}

从大到小的cmp函数:

bool cmp(const 数据类型& 变量名,const 数据类型& 变量名){

return a>b;

}

在两个函数中,都有 const 数据类型& 变量名,const 数据类型& 变量名的代码片段。如果你嫌麻烦,你可以直接改为 数据类型 变量名,数据类型 变量名。

vector中的排序

Q:What is vector?

A:vector是STL里提供的一种数据结构,名称为不定长数组,使用需要调用头文件#include<vector>。

Vector是一个很有用的数据结构,使用方便,在图论中有极大的作用。

Q:如何对vector排序?

A:vector并不像数组有一定的上界和下界,所以不能像数组一样排序。

Vector的排序模板是:

Sort(vector名.begin(),vector名.end());

这里的begin()和end()属于vector的函数,这里的sort表示从vector的第一个元素开始,一直排序到最后一个元素。

注意,这里的排序还是从小到大的排序,如需修改,需要自己编写cmp函数,其编写cmp函数的方法与普通数据类型的编写方法相同。

在这里,有可能有不少同学不知道vector的使用方法,我没有太多的空间介绍vector,所以给大家一个网址:

https://blog.csdn.net/zhuxiaoping54532/article/details/56012627

 

结构体的排序

Q:What is 结构体?

A:结构体是一种特殊的数据结构,里面可以包含多种普通数据结构,如int,string,char,double等等。

Q:如何对结构体数组进行排序?

A:结构体的sort调用基本与普通数据类型类似,但是每个sort都需要编写cmp函数(因为结构体内含有多个变量,排序就没有一定的标准)。

让我们再举个例子:

给定一种结构体,输入该结构体数组,再依照如下标准排序:

结构体有int类型的a,b;char类型的c,排序标准为:先按int型的a从小到大排,再按char型的c从大到小排,最后按int型的b从小到大排。

首先,先按照题目定义一个结构体Point和Point型的数组:

struct Point{

int a,b;

char c;

}point[100010];

接着,定义排序标准对应的cmp函数:

bool cmp(const Point& p1,const Point& p2){

/*if判断是避免如果p1和p2的某个变量相等而直接return,不继续按照正常的排序标准继续比较*/

if(p1.a!=p2.a)

return p1.a<p2.a;

if(p1.c!=p2.c)

return p1.c>p2.c;

return p1.b<p2.b;

}

最后,调用sort:

sort(point+1,point+1+n,cmp)//n为point数组长度

这种编造cmp函数办法属于正常的结构体排序办法,当然还有更高端的办法,名字叫做

     重载运算符!!

下面,我来介绍一下What is 重载运算符。

重载运算符,顾名思义,就是把原有运算符的定义改变。它主要运用于排序。

结构体里的重载运算符出现次数最多,模板为:

bool operator 运算符 (const 结构体名& 变量名) const {

排序标准

}

注意,重载运算符都需要编写在结构体内。

再把刚刚的题目写一遍:

定义结构体并编写重载运算符函数:

struct Point{

int a,b;

char c;

bool operator < (const Point& rhs) const {

/*重载小于号是因为原本sort从小到大进行排序,就是依靠小于号来比较的*/

if(a!=rhs.a)

return a<rhs.a;

if(c!=rhs.c)

return c>rhs.c;

return b<rhs.b;

}

}point[100010];

直接调用sort函数(这里由于小于号已经被重载,所以不需要添加cmp函数):

sort(point+1,point+1+n);

Q:如果重载了小于号,那么在别的地方使用小于号时,会不会出现bug?

A:不会的。因为这里的重载只针对于结构体,并不会影响别的地方的使用。

其他

Q:sort的时间复杂度是多少?

A:sort采用快速排序(quick-sort)为模板,时间复杂度即为快排的时间复杂度。快排的平均时间复杂度为,最坏情况为,但是在实践中很少会达到最坏情况。

Q:除了CCF NOI系列赛事,其余的国内信息学竞赛是否允许使用sort?

A:基本上都允许了。因为CCF NOI系列赛事是国内知名度最高的信息学竞赛,基本上都以它为标杆。CCF什么标准,各个地区基本上都会执行。

Q:排序除了sort和quick-sort之外,还有别的排序算法吗?

A:有,例如归并排序、堆排序、选择排序、冒泡排序、插入排序。其中,选择排序、冒泡排序、插入排序的时间复杂度为

归并排序、堆排序的时间复杂度为

 

 

完结撒花!!!