总目录

sort

今天我们来看一个STL中基本上是最常用的一个函数：sort
为什么他这么常用呢？因为他真的太香了，虽然他的时间复杂度在一些情况下未必是最优的，但是它是真的方便（懒癌晚期患者狂喜）

功能

说了这么多，sort到底是干什么的?

答曰：排序

没错，简单粗暴，就是排序，并且需要注意的是，升序排序，即从小到大。
去掉多余的废话，直接上干货：

格式

1.最基本的用法

sort(起点，终点)
对于sort最基本的使用就是对一个数组（或者动态数组什么的简单数据结构）进行升序排序了，只需要用它本身的功能便可以了。
需要注意的是此处的起点和终点是通过数组名+起点位置和数组名+终点位置的方式传入的，另外需要注意的，起点位置和终点位置构成了一个左闭右开的区间，起点位置的数据会参与排序而终点位置的数据不会参与；更具体的说，当你想对数组$a$中第$x$个到第$y$个数据进行排序时，sort函数的写法便是：sort(a + x, a + y + 1)
比如：

#include <iostream>
#include <algorithm>//STL函数必备
using namespace std;
int main() {

    int a[5] = {1, 5, 4, 2, 3};
    //先定义一个无序的数组
    sort(a, a + 5);
    //排序
    //对数组a中[0,5)数据排序，即对a[0],a[1],a[2],a[3],a[4]排序
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    //输出：1 2 3 4 5

    return 0;
}

2.对结构体排序

如果你尝试用sort直接对一个自己定义的结构体排序，他会无情的报错并打开一个你看不懂的东西（devc+ +）。
比如：

#include <iostream>
#include <algorithm>
using namespace std;
struct Num {
    int num1, num2;
} num[5];
int main() {
    for (int i = 0; i < 5; i++) {
        cin >> num[i].num2;
        num[i].num1 = i;
    }
    sort(num, num + 5);
    return 0;
}

当你高高兴兴的按下编译按钮。你的编译器也高高兴兴的为你报了个错并打开了一个文件......

这是什么意思呢，其实我也不知道大概就是告诉你：你这数据类型我不认识，我sort不知道怎么比大小，上哪去给你排序！
那解决方案也就很明显了，告诉sort如何进行比较大小就行了呗，一般分为如下两种方式：

方法一：重载比较运算符

sort不会比，比较运算符肯定得背锅，谁让你没有比较我的结构体的功能呢，所以我们的任务就是要告诉sort比较运算符在我们的结构体中怎么用。重载的知识点说起来实在太多了，在这里暂且略过，使用sort时，我们重载的基本格式如下：

bool operator < (const 结构体类型& a) const {
    return 排序数据关键字 < a.排序数据关键字;
}

这样，我们就给$<$在对结构体比较时提供了新的定义，即对两个结构体类型的数据，以关键字数据的大小作为比较内容，这么看可能比较抽象，让我们再看一段代码：

#include <iostream>
#include <algorithm>
using namespace std;
struct Num {
    int num1, num2;

    bool operator < (const Num& a) const {
        return num2 < a.num2;
    }
    //重载部分，一定是在结构体中进行的

} num[5];
int main() {
    for (int i = 0; i < 5; i++) {
        cin >> num[i].num2;
        num[i].num1 = i + 1;
    }

    sort(num, num + 5);

    for (int i = 0; i < 5; i++) {
        cout << num[i].num1 << " ";
    }
    return 0;
}

这段代码便是刚刚报错那段的改进，当我们在结构体中重载了$<$后，我们的程序在对两个$Num$类型的数据进行比较大小时，便能够知道，两个结构体中$num2$这一数据较大者大的数据。此时使用sort进行排序也就是对结构体按照$num2$的大小顺序进行升序排序。

方法二：

除了比较符号，还有谁应该背锅呢？毋庸置疑，这锅当然要甩给sort函数自身了，还是你不够强啊。（吃着碗里的，还骂着厨子）
不过你还别说，sort早就想到了这种问题，这时候我们就要利用到sort提供的第三个参数位置了。没错！sort其实有三个参数，但是第三个参数不是必须的，这是一个bool类型的参数，一般传入一个提供比较条件的函数，比如降序排序（下面会说到）还有对结构体排序等等。
那我们来看看这个比较函数该怎么写：

bool cmp (Node a, Node b) {
    return a.x < b.y;
}

如上的代码，我们便定义了一个名为cmp的比较函数（名字不固定，一般为代码的可读性写为cmp，表示compare，即比较），这是一个有固定格式的函数，传入两个参数，Node处均为想要排序的数据类型（结构体排序时直接把Node替换成结构体的名字即可）。返回一个比较的值，返回$<$即为升序排序。
老样子，我们再用这种方式对前面的错误代码进行改正：

#include <iostream>
#include <algorithm>
using namespace std;
struct Num {
    int num1, num2;
} num[5];

bool cmp (Num a, Num b) {
    return a.num2 < b.num2;
}

int main() {
    for (int i = 0; i < 5; i++) {
        cin >> num[i].num2;
        num[i].num1 = i + 1;
    }

    sort(num, num + 5, cmp);

    for (int i = 0; i < 5; i++) {
        cout << num[i].num1 << " ";
    }
    return 0;
}

3.降序排序呢？

sort为我们提供了方便的升序排序，当我们如果想对数据降序排序呢？刚刚已经讲过了结构体排序，那降序排序可以大概类比思考一下。

方法一

既然你会升序，那就升序排吧，倒着输出不就完了？
代码略（懒了属于是）

方法二

我们当然也可以通过重载比较运算符的方式来改变排序的顺序啦，只要把小于号重载成大于号就🆗
重载代码:

bool operator < (const Num& a) const {
    return num2 > a.num2;
}

方法三

写一个比较函数又有何不可？
只要把里面的符号颠倒一下就可以喽
比较函数：

bool cmp (Num a, Num b) {
    return a.num2 > b.num2;
}

4.特殊要求的排序

还有一些变态的题目对排序给了一堆要求，比如
洛谷P1104 生日
这种时候，我们发现，题目要求的不仅仅是对一组数据进行排序，而是对多组数据的综合结果进行排序，这时候，排序函数的功能就体现出来了，因为我们可以在排序数组中规定我们想要的任何排序条件。比如例题的代码：

#include <iostream>
#include <algorithm>

using namespace std;

int n;
struct ClassMate {
    string name;
    int year, month, day, in;
} classmate[105];
bool cmp(ClassMate a, ClassMate b) {
    if (a.year != b.year) { //先比较年
        return a.year < b.year;
    } else if (a.month != b.month) { //如果年份相同，再比较月
        return a.month < b.month;
    } else if (a.day != b.day) { //月份都一样，比较日
        return a.day < b.day;
    } else { //连日都一样，那就看输入顺序吧
        return a.in > b.in;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> classmate[i].name >> classmate[i].year >> classmate[i].month >> classmate[i].day;
        classmate[i].in = i;
    }
    sort(classmate, classmate + n, cmp);
    //排序
    for (int i = 0; i < n; i++) {
        cout << classmate[i].name << endl;
    }
    return 0;
}

时间复杂度

$O_{(n log n)}$

sort的基本知识点基本上就这些了吧，至少一般来讲是够用了，也可能是我孤陋寡闻，欢迎补充。
在平时的刷题过程中，还是建议大家多用手写的排序（虽然我几乎没写过），这样一方面能提高代码能力，另一方面也是复习提高的过程，况且有些情况下一些手写函数的时间复杂度还要低于sort呢~
那这篇文章就写到这里吧

点赞！收藏！关注！（可怜可怜这个快秃了的up吧QAQ，拜托）

拜拜ヾ(•ω•`)o