排序的一些性质
通过比较操作来给同类元素排序。
可排序性
要求比较规满足可排序性:
任意两个待排序的元素都可以进行比较
比较规则满足传递性
例如，石头剪刀布不满足可排序性。这谁都知道
稳定性
排序后相等元素的位置是否发生变化
如果一定不发生变化，那么我们称它为稳定的排序
如果可能发生变化，那我们称它为不稳定的排序
逆序对
处于逆序关系的一对元素:存在下标\(i,j,(i < j)\)，满足\(a_{i} > a_{j}\)，称\((i,j)\)为一对逆序对
例题:逆序对统计
题目让我们求出\(n\)个不重复的数中有多少个逆序对
既然这题数据够小，那我们就可以……手打暴力（我为什么想到了柠季手打柠檬茶！）
示例Code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int n,ret,a[MAXN];
int main(){
cin >>n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int i = 1; i <= n; i++){
for (int j = i + 1; j <= n; j++){
ret += a[i] > a[j] ? 1 : 0;
}
}
cout << ret;
return 0;
}
排序函数
C++ STL(Standard Library,标准库)中通过<algorithm>头文件中的函数sort()和stable_sort()预先实现了一些排序算法，只不过，sort()不稳定，而stable_sort()是稳定的。
用法：函数名(起始地址，结束地址，比较器);,表示按比较器函数实现的排序规则对(起始地址，结束地址)做排序，其中比较器是可选参数
sort()和stable_sort()都是基于比较的排序，平均需要\(n \cdot \log(n)\)次的元素比较和移动，其中\(n\)表示待排序元素的数量。基于比较的排序时间复杂度至少为\(O(n \cdot \log(n))\)。
例题:数字排序1
题目让我们从小到大排序，我们就可以用sort函数啦~
示例Code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n,a[MAXN];
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
stable_sort(a + 1,a + n + 1);
for (int i = 1; i <= n; i++){
cout << a[i] <<' ';
}
return 0;
}
比较器
用函数实现的自定义比较规则。
在\(C++\)中，比较器接受两个同类型参数，第一个参数靠前时返回\(true\)，否则返回\(false\)（包括相等的情况）
例如：大数靠前的比较器:
bool cmp(int i,int j){
return i > j;
}
例题:数字排序2
题目让我们从小到大排序，我们又可以用sort函数啦~（
当然我们需要一个cmp函数
示例Code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n,a[MAXN];
bool cmp(int x,int y){
return x > y;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
stable_sort(a + 1,a + n + 1,cmp);
for (int i = 1; i <= n; i++){
cout << a[i] << ' ';
}
return 0;
}
结构体排序！
重点终于来了（
结构体排序是指开一个结构体，这知道吧，在写一个cmp函数，这也知道吧，然后修改一下cmp，把里面的return语句改一下，假设是这样的：
const int MAXN = 1e5 + 10;
struct Student{
int c,id;
}a[MAXN];
可见这是一个结构体，确切地说，是一个用来存储学生的某某某东西的结构体，然后我们要对它进行排序，怎么排呢？如果你要排的是\(c\)（默认小数靠前），那么cmp就这么写：
bool cmp(const Student &a, const Student &b){
return a.c < b.c;
}
然后如果你要排的是\(id\)（还是小数靠前），就这么写：
bool cmp(const Student &a, const Student &b){
return a.id < b.id;
}
例题1:排序与编号
题目让我们给长度为\(n\)的数组排序，然后输出排序后的编号，那么我们可以这样，先写一个结构体，里面有\(c,id\)两个值，还有一个用来存储数据的\(Node\)类型的\(a\)数组：
const int MAXN - 1e5 + 10;
struct Node{
int c,id;
}a[MAXN];
然后，就是刚刚讲的结构体排序，因为题目给的是让我们从小到大排序
bool cmp(const Node a, const Node b){
return a.c < b.c;
}
注意：这里要写的是\(a.c\)，而不是\(a.id\)，因为不是给\(id\)排序。
完整示例Code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n;
struct node{
int id,c;
}a[MAXN];
bool cmp(node x,node &y){
return x.c < y.c;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i].c;
a[i].id = i;
}
sort(a + 1, a + n + 1,cmp);
for (int i = 1; i <= n; i++){
cout << a[i].id << ' ';
}
return 0;
}
例题2:多关键字排序
题目让我们给同学们的\(m\)课成绩排序，并按顺序输出排序后的学号，我们还是写结构体排序，注意是有\(m\)科，所以结构体里面还需要一个数组。
示例Code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10,maxn = 1e1 + 10;
int n,m;
struct Student{
int km[maxn];
}stu[MAXN];
bool cmp(Student &a,Student &b){
for (int i = 1; i <= m; i++){
if (a.km[i] != b.km[i]){
return a.km[i] > b.km[i];
}
}
return false;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> stu[i].km[j];
}
}
sort(stu + 1,stu + n + 1,cmp);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cout << stu[i].km[j] << ' ';
}
cout << '\n';
}
return 0;
}
重载<运算符
排序函数使用<符号来比较。通过在结构体内重载<运算符，可以让排序函数支持结构体排序的比较规则，类似于比较器。
格式:
bool operator < (const Node & i) const{
//...
}
//Node为结构体类型名称，i为对象名
//在大括号中实现比较规则，const表示该运算符不能对成员进行修改操作
例题:区间排序
题目让我们按照左边界和右边界排序，这里分为两种情况：
1，左边界不同
2，左边界相同
这两个东西要写一个||符号，左边界相同和另一个条件（右边界不同）要写&&。
示例Code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n;
struct node{
int l,r;
bool operator < (const node &k) const {
return l < k.l ||l == k.l && r < k.r;
}
}a[MAXN];
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i].l >> a[i].r;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++){
cout << a[i].l << ' ' << a[i].r << '\n';
}
return 0;
}