sort函数介绍
背景
sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include的c++标准库中。
功能
sort函数用于C++中，对给定区间所有元素（不仅可对数据型元素，也可对字符型元素，不过同一个排序数组只能有一种类型元素）进行排序，默认为升序，也可进行降序排序。
语法
sort(start,end,cmp);
start:表示要排序数组的起始地址;
end:表示数组结束地址的下一位；
cmp:用于规定排序的方法，可不填，默认升序（从小到大）。
例如：将一个int型的起始下标为0的总元素为n的数组中元素从小到大排序，则可写为：sort(a,a+n)
cmp函数编写
（1）升序（从小到大）
bool cmp(int x,int y)
{
return x<y;
}
（2）降序（从大到小）
bool cmp(int x,int y)
{
return x>y;
}
便捷函数
less<数据类型>()
同例：sort(a,a+n,less< int >());
greater<数据类型>()
同例：sort(a,a+n,greater< int >());
sort函数应用
普通排序
例题：来自洛谷P1271题,学会了之后可以自己写一下，交一下，点击链接进去做：link
【深基9.例1】选举学生会
题目描述
学校正在选举学生会成员，有
n
(
n
≤
999
)
n(n\le 999)
n(n≤999) 名候选人，每名候选人编号分别从 1 到
n
n
n，现在收集到了
m
(
m
<
=
2000000
)
m(m<=2000000)
m(m<=2000000) 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。
输入格式
输入
n
n
n 和
m
m
m 以及
m
m
m 个选票上的数字。
输出格式
求出排序后的选票编号。
样例 #1
样例输入 #1
5 10
2 5 2 2 5 2 2 2 1 2
样例输出 #1
1 2 2 2 2 2 2 2 5 5
思路：这个题通读一下，就知道，其实应该跟n没啥关系，就是把m个元素进行升序排序，把m个元素存进数组里，然后sort一下就行了，写不写cmp函数都没关系，主要也是升序
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+7;
int a[N];
//bool cmp(int x,int y)
//{
// return x>y;
//}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>a[i];
}
sort(a,a+m);//sort(a,a+m,cmp);
for(int i=0;i<m;i++)
{
cout<<a[i]<<' ';
}
return 0;
}
洛谷P1923题，链接link
【深基9.例4】求第 k 小的数
题目描述
输入
n
n
n（
1
≤
n
<
5000000
1 \le n < 5000000
1≤n<5000000 且
n
n
n 为奇数）个数字
a
i
a_i
ai（
1
≤
a
i
<
10
9
1 \le a_i < {10}^9
1≤ai<109），输出这些数字的第
k
k
k 小的数。最小的数是第
0
0
0 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入格式
输出格式
样例 #1
样例输入 #1
5 1
4 3 2 1 5
样例输出 #1
2
思路：本题也是直接用sort，找第k小的数，题目又说了最小的数是第0小，如果最小的数是第1小的话，sort直接用成sort(a+1,a+n+1)（ps：使用条件是输入时数组下标从1开始）;
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e8+9;
int a[N];
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
printf("%d\n",a[k]);
return 0;
}
结构体排序
对结构体的排序需要查看题目中所给的排序条件，有可能不止一个排序条件，这时我们就需要好好写一下cmp函数了。
例题：link
洛谷P1104题
生日
题目描述
cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。
输入格式
输入共有
2
2
2 行，
第
1
1
1 行为 OI 组总人数
n
n
n；
第
2
2
2 行至第
n
+
1
n+1
n+1 行分别是每人的姓名
s
s
s、出生年
y
y
y、月
m
m
m、日
d
d
d。
输出格式
输出共有
n
n
n 行，
即
n
n
n 个生日从大到小同学的姓名。（如果有两个同学生日相同，输入靠后的同学先输出）
样例 #1
样例输入 #1
3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1
样例输出 #1
Luowen
Yangchu
Qiujingya
提示
数据保证，
1
<
n
<
100
1<n<100
1<n<100，
1
≤
∣
s
∣
<
20
1\leq |s|<20
1≤∣s∣<20。保证年月日实际存在，且年份
∈
[
1960
,
2020
]
\in [1960,2020]
∈[1960,2020]。
思路：
本题要求按照年龄从大到小排序，即是将出生日期早的人列在前面，但如果年龄一样大，就要将在后面输入的人排在前面。比较年龄，首先比较出生年份，年份越小，年龄越大，然后再比较月份，再比较日期，最后还要比较输入顺序，这时候我们单用数组肯定不容易，所以我们采用结构体来进行比较。
代码:
#include <iostream>
#include <algorithm>
using namespace std;
struct stu{
string s;//名字
int year;//年
int month;//月
int day;//日
int num;//输入的序号，即第几个输入的
}a[107];
bool cmp(stu x,stu y)//stu为数据类型，这里是我们自己定义的结构体类型
{
if(x.year!=y.year)//先比较年龄
return x.year<y.year;//返回年份小的，即年龄大的
else if(x.year==y.year&&x.month!=y.month)//年份相同，比较月份，返回月份小的
{
return x.month<y.month;
}
else if(x.year==y.year&&x.month==y.month&&x.day!=y.day)//与上同理
{
return x.day<y.day;
}
else if(x.year==y.year&&x.month==y.month&&x.day==y.day&&x.num!=y.num)
{
return x.num>y.num;//返回序号大的，即后输入的
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i].s>>a[i].year>>a[i].month>>a[i].day;
a[i].num=i;//标记输入顺序
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
cout<<a[i].s<<endl;
}
return 0;
}
在cmp函数里，可以根据题目按照正确的想法进行改变排序的方法，从而是题目得到题解。sort函数在相关排序题中还是挺好用的，希望大家能快乐学习sort函数吧！
