上次讲了四种排序算法（没看过的点这里），但是在实际开发或是竞赛中可能没有足够的时间写出一个够用的排序函数，或是需要排序的并非数字，这时便是我们的大宝贝 ——std::sort () 函数登场的时候了。
用法
需要先引用 algorithm 库，不过我更倾向于在竞赛时直接使用万能库节省记忆时间。然后，需要使用 std 命名空间，或是直接调用 std::sort ()。
sort () 函数的原型如下：
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);对，std::sort () 是重载函数，其中包含了是否存在 comp 的两种版本。std::sort () 函数默认从小到大按字典顺序对数据进行排序，用法如下：
int arr[10] = {12, 10, 48, 28, 22, 33, 19, 13, 27, 38};
std::sort(arr, arr + 10);
for(int i = 0;i < 10;i++) std::cout<<arr[i]<<" ";此时 std::sort () 函数便会将 arr [0] 到 arr [9] 共 10 个元素进行排列并放回 arr 数组，所以上述程序运行结果如下：
10 12 13 19 22 27 28 33 38 48很容易就可以想到，对吧。
进阶
使用 std::sort () 对各类普通变量排序
对 std::string 类型变量排序
前面提到了，std::sort () 会对数组使用字典序从小到大排序，所以结果就很容易预想到。
看下列程序：
std::string arr[10] = {"apple", "Apple", "APPLE", "zen", "ordchaos", "OrdChaos", "happy", "x-ray", "xyz", "123aa"};
std::sort(arr, arr + 10);
for(int i = 0;i < 10;i++) std::cout<<arr[i]<<" ";想一想，结果会如何？
结果：123aa APPLE Apple OrdChaos apple happy ordchaos x-ray xyz zen
怎么样，是不是很简单。这种对 std::sort () 的使用方式可以做按照字母序排列姓名的题目，但是如果题目要求按长度排序怎么办？别着急，慢慢往下看。
使用 comp 自定义排序顺序
刚刚说过，std::sort () 是一个重载函数，有一个含有 comp 的变体，那么，comp 是什么？用来干什么呢？简单来说，comp 就是一个返回值为 bool 类型的函数，在这个函数里你可以自定义 sort 排序的顺序。这样说你可能不理解，那就来看看下面这个例子：
bool cmp(int a, int b) {
return a > b;
}
int main() {
int arr[2][10] = {{12, 10, 48, 28, 22, 33, 19, 13, 27, 38},{12, 10, 48, 28, 22, 33, 19, 13, 27, 38}};
std::sort(arr[0], arr[0] + 10);
std::sort(arr[1], arr[1] + 10, cmp);
for(int i = 0;i < 10;i++) std::cout<<arr[0][i]<<" ";
std::cout<<std::endl;
for(int i = 0;i < 10;i++) std::cout<<arr[1][i]<<" ";
return 0;
}在这里我定义了 bool 类型函数 cmp ()，其中若 a>b 则返回 true，否则为 false。然后两次调用 std::sort ()，分别为两个一模一样的数组 arr [0] 与 arr [1] 排序，不同的是第二次使用了我们定义的 cmp ()，那么，结果如何呢？
10 12 13 19 22 27 28 33 38 48
48 38 33 28 27 22 19 13 12 10没错，第二次排序变为了从大到小排序。利用这种方法，我们就可以轻松解决刚刚的问题，像这样：
bool cmp(std::string a, std::string b) {
return a.length() < b.length();
}把这个函数加入刚刚的程序，再次调用 std::sort ()，只不过要加入参数 cmp。很容易想到结果如下：
（动动脑哦）zen xyz apple Apple APPLE happy x-ray 123aa ordchaos OrdChaos
对 std::string 类型变量内部进行排序
联想到可以通过类似于 str [i] 的方式来访问字符串内字符，自认可以写出使用 std::sort () 排序字符串内字符的方法：
std::string str = "rhuMJKhwHefJkUIGuw394y49h";
std::sort(str.begin(), str.end());注意这里必须使用 str.begin () 与 str.end () 作为参数而非 str 与 str+str.str.length ()。
结果也就是可以料想的，编译运行，程序输出如下：
34499GHIJJKMUefhhhkruuwwy整 整 齐 齐.jpg
利用 comp 同样可以实现逆序排序，那就请你自己想想怎么写吧！
使用 std::sort () 对结构体进行排序
设想一个场景，有一个结构体叫做 student，其中含有单个学生的姓名和成绩。这时该如何通过学生成绩对学生姓名进行排序呢？这里用 std::sort () 就会使最快的方法。
先定义结构体：
struct student {
string name;
int score;
};然后写出对应的 comp：
bool cmp(student a, student b) {
return a.score > b.score;
}之后直接调用 std::sort () 就可以了，合起来代码如下：
#include<bits/stdc++.h>
using namespace std;
struct student {
string name;
int score;
};
bool cmp(student a, student b) {
return a.score > b.score;
}
int main() {
student stu[3] = {(student){"Tony", 98}, (student){"Betty", 97}, (student){"Lucy", 99}};
sort(stu,stu+3,cmp);
for(int i=0;i<3;i++){
cout<<stu[i].name<<endl;
}
return 0;
}输出可以料想：
Lucy
Tony
Betty这样做的好处是方便拓展，比如说现在结构体变了，存在四个科目的成绩与学生姓名，要求按平均分排序，从之前的程序上修改会非常容易：
#include<bits/stdc++.h>
using namespace std;
struct student {
string name;
int chinese;
int math;
int english;
int programming;
};
bool cmp(student a, student b) {
return (a.chinese + a.math + a.english + a.programming)/4 > (b.chinese + b.math + b.english + b.programming)/4;
}
int main() {
student stu[3] = {(student){"Tony", 98, 96, 100, 95}, (student){"Betty", 97, 80, 99, 95}, (student){"Lucy", 99, 96, 90, 100}};
sort(stu,stu+3,cmp);
for(int i=0;i<3;i++){
cout<<stu[i].name<<endl;
}
return 0;
}这时结果就会变为Tony Lucy Betty的顺序。比起手写排序，这种情景使用 std::sort () 会方便不少。
做道题吧
题目描述
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据 (每行输出两个数：学号、总分) 是:
77 279279
55 279279这两行数据的含义是：总分最高的两个同学的学号依次是 7 号 5 号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和)，但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是:
55 279279
77 279279则按输出错误处理，不能得分。
输入格式
共 n+1 行。
第 1 行为一个正整数 n（n≤300），表示该校参加评选的学生人数。
第 2 到 n+1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1~n（恰好是输入数据的行号减 1）。
所给的数据都是正确的，不必检验。
输出格式
共 5 行，每行是两个用空格隔开的正整数，依次表示前 5 名学生的学号和总分。
输入输出样例
输入 1
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98输出 1
6 265
4 264
3 258
2 244
1 237输入 2
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98输出 2
8 265
2 264
6 264
1 258
5 258分析
这是一道很好的练习结构体的题，核心就是刚刚说的使用 std::sort () 函数对结构体进行排序，只不过这次的 comp 会复杂那么一点点。
结构体定义与 comp 大致如下：
struct student {
int num, chinese, math, english;
};
bool cmp(student a,student b) {
if((a.chinese + a.math + a.english) > (b.chinese + b.math + b.english)) return 1;
else if((a.chinese + a.math + a.english) < (b.chinese + b.math + b.english)) return 0;
else {
if(a.chinese > b.chinese) return 1;
else if(a.chinese < b.chinese) return 0;
else {
if(a.num > b.num) return 0;
else return 1;
}
}
}剩下的部分就不必多说了吧，直接上代码：
int main() {
int n;
std::cin>>n;
student stu[n];
for(int i = 0;i < n;i++) {
stu[i].num = i + 1;
std::cin>>stu[i].chinese>>stu[i].math>>stu[i].english;
}
std::sort(stu,stu + n,cmp);
for(int i = 0;i < 5;i++) std::cout<<stu[i].num<<' '<<stu[i].chinese + stu[i].math + stu[i].english<<std::endl;
return 0;
}完成！
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
struct student {
int num, chinese, math, english;
};
bool cmp(student a,student b) {
if((a.chinese + a.math + a.english) > (b.chinese + b.math + b.english)) return 1;
else if((a.chinese + a.math + a.english) < (b.chinese + b.math + b.english)) return 0;
else {
if(a.chinese > b.chinese) return 1;
else if(a.chinese < b.chinese) return 0;
else {
if(a.num > b.num) return 0;
else return 1;
}
}
}
int main() {
int n;
cin>>n;
student stu[n];
for(int i = 0;i < n;i++) {
stu[i].num = i + 1;
cin>>stu[i].chinese>>stu[i].math>>stu[i].english;
}
sort(stu,stu + n,cmp);
for(int i = 0;i < 5;i++) cout<<stu[i].num<<' '<<stu[i].chinese + stu[i].math + stu[i].english<<endl;
return 0;
}附加内容
std::sort () 的平均时间复杂度是 O (nlog (n))，原理是在数据量大时采用快速排序进行分段递归排序，而一旦分段后的数据量小于某个门槛，为避免快速排序的递归调用带来过大的额外负荷，就改用直接插入排序（不是插入排序）。如果递归层次过深，还会改用堆排序。
sort 的速度够快，但若是追求极致速度且数据量很大，仍建议手写快速排序或归并排序。
题外话
写这篇文章真的累死…
写了足足一个小时啊啊啊啊啊
白里个白（逃