【高级篇】C++中的sort函数详解
0.简介
sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include<algorithm>的c++标准库中
1.sort的参数
start:表示排序数组起始的位置
end:表示排序数组结束的位置
cmp：用于排序的方法，可以不填，不填默认升序
2.数组中的用法
当我们加上cmp函数后，下面这种写法和上面的结果一样
可以这样理解，sort中的第三个参数，会去进行两两元素的比较，
函数这个地方是个bool类型的函数。
如果返回值结果为假，那么函数会互换他们的位置
如果返回结果为真，就保持原来的位置不变函数
那么，如果把cmp中的函数改成 return x>y; 那么默认就是 从大到小排序。
3.结构体中的用法
平常做题的时候可能会遇到下面几种情况：
一个结构体需要排序，里面属性太多，只根据一个属性进行排序，其余属性需要同步更改位置，单纯使用冒泡需要交换的东西太多
一个结构体需求排序，但是排序依据不唯一。例如下面结构体
要求先按照总成绩排序，如果总成绩相同，则按照数学成绩排序，如果数学成绩相同，则按照英语成绩排序，如果英语成绩相同则按照语文成绩排序。
。。。。。。
先来解决第一个问题，假如只按照总成绩排序，总成绩相同的不做任何排序处理。
可以看出是按照总计成绩进行排序的。可以看出，我们在cmp函数中只要写一个结构体中的参数就可以了。
那么第二个问题来了。我们可以继续改cmp中的写法
可以看出，首先按照总成绩排序，如果总成绩相同，则按照数学成绩排序，如果数学成绩相同，则按照英语成绩排序。题目的样例不够完善，没有体现出如果在上面的条件下，如果英语成绩也相同的情况。
4.字典序问题
一些题目中，可能会要求按照字典序排序，一般多见于字符串的类型。
比如
例题1—单词排序：
【题目描述】输入一行单词序列，相邻单词之间由1个或者多个空格间隔，请按照字典序输出这些单词。
【输入】一行单词序列，最少1个单词，最多100个单词，每个单词长度不超过50，单词之间用至少1个空格间隔。数据不含除字母、空格外的其他字符。
【输出】按字典序输出这些单词。
【样例输入】
She wants to go to Peking University to study Chinese
【样例输出】
Chinese Peking She University go study to wants
首先，这个题目简单一点的做法就是，直接for循环，按照ASCII码比较。但是，我们学了sort，用起来就比较简单了。
做法1：sort+结构体+字符数组
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct student{
char name[50];
}s[100];
bool cmp(student x, student y){
return x.name > y.name;
}
int main(){
int n;
cin>>n; //确定长度
for(int i=0;i<n;i++){
cin>>s[i].name;
}
//sort(s,s+n); //因为是结构体，所以不加第三个参数，这里会报错
sort(s,s+n,cmp);
cout<<"-----结果-----"<<endl;
for(int i=0;i<n;i++){
cout<<s[i].name<<endl;
}
}
/*
输入：
4
aa
bs
cf
ck
输出：
ck
cf
bs
aa
*/可以看出，我们如果结构体中只是用字符数组排序的话，只能按照输入的正序或者倒序排，但是没有按照字典序排。（但是如果是类似按照总成绩进行排序，那么名字会同步变化）
如果是结构体+字符串呢
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct student{
string name;
}s[100];
bool cmp(student x, student y){
return x.name < y.name;
}
int main(){
int n;
cin>>n; //确定长度
for(int i=0;i<n;i++){
cin>>s[i].name;
}
//sort(s,s+n); //因为是结构体，所以不加第三个参数，这里会报错
sort(s,s+n,cmp);
cout<<"-----结果-----"<<endl;
for(int i=0;i<n;i++){
cout<<s[i].name<<endl;
}
}
/*
输入：
4
aa
bs
cf
ck
输出：
aa
bs
cf
ck
*/可以看出这种是没有问题的。
也就是说，如果是成绩排序+字典序排序的话， 那么类似于名字这样的，要用字符串而不是字符数组。
做法2：sort+字符串数组
除了结构体之外，我们还可以用字符串数组来
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
string s[100];
int main(){
int n;
cin>>n; //确定长度
for(int i=0;i<n;i++){
cin>>s[i];
}
sort(s,s+n);
cout<<"-----结果-----"<<endl;
for(int i=0;i<n;i++){
cout<<s[i]<<endl;
}
}
/*
输入：
4
Ajl
dsa
Bdr
rgk
输出：
Ajl
Bdr
dsa
rgk
*/可以看出，字符串数组可以不用加sort的第三个参数，默认按照字典序输出。当然，我们也可以加上第三个参数。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
string s[100];
bool cmp(string x, string y){
return x>y;
}
int main(){
int n;
cin>>n; //确定长度
for(int i=0;i<n;i++){
cin>>s[i];
}
sort(s,s+n,cmp);
cout<<"-----结果-----"<<endl;
for(int i=0;i<n;i++){
cout<<s[i]<<endl;
}
}
/*
输入：
4
Ajl
dsa
Bdr
rgk
输出：
rgk
dsa
Bdr
Ajl
*/5.总结
不论是单纯的数组还是结构体，sort函数的第三个参数是用来决定两个元素是否要进行交换位置的。
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
