C++ sort()函数用法详解（附带实例）

在算法竞赛中，99% 需要排序的情况都可以通过 STL 中的 sort() 函数解决，因此我们要熟练掌握如何使用 sort() 函数，并学会自定义比较函数。

在少数情况下，可能需要使用桶排序、归并排序等算法，其他排序方法几乎用不到，仅需了解其他排序法的基本思想即可。

sort() 函数的时间复杂度为 O(nlogn)，这已经是一种极为出色的性能了，因此通常不需要自己编写排序算法。

下面将展示一些示例程序，通过这些示例程序，读者可以直观地了解如何调用 sort() 函数。

【实例 1】将元素排为升序，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int a[N];
int main() {
    // 输入数据
    // 将 a[1] ~ a[n] 的数据进行排序，默认为升序，传入的两个参数分别是起始地址和终止地址，左闭右开
    sort(a + 1, a + 1 + n);
    return 0;
}

【实例 2】对 vector 中的元素进行排序，代码如下：

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
    // 输入数据
    // 对 v[0] ~ v[v.size()-1] 的数据进行排序，默认为升序
    sort(v.begin(), v.end());
    return 0;
}

sort()自定义比较函数

常用的自定义比较函数的方法有以下几种。

1) 自定义函数

通过编写一个自定义的比较函数，可以灵活地定义排序规则。例如，下面的代码展示如何创建一个降序排序的比较函数：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int a[N];

// 自定义比较函数
bool cmp(int x, int y) {
    // 大于号，得到的结果是降序的
    return x > y;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
    return 0;
}

2) 重载小于运算符（常用于结构体）

对于结构体或类，可以通过重载小于运算符来定义排序规则。例如，下面的代码将展示了如何对一个包含两个整数的结构体数组进行排序：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

struct Node {
    int x, y;
    // 重载小于运算符，定义排序规则
    // 以 y 为第一关键字升序，如果 y 相等，就按照 x 升序
    bool operator < (const Node &u) const {
        return y == u.y ? x < u.x : y < u.y;
    }
} a[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n);   // 不写第三个参数，就默认使用重载 < 运算符进行排序
    // 输出排序后的结果
    for (int i = 1; i <= n; ++i) cout << a[i].x << ' ' << a[i].y << '\n';
    return 0;
}

3) Lambda表达式

使用 Lambda 表达式可以更简洁地定义比较函数。例如，下面的代码展示如何使用 Lambda 表达式实现降序排序：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int a[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n, [](int x, int y) {
        return x > y;   // 大于号，得到的结果是降序的
    });
    // 输出排序后的结果
    for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
    return 0;
}