sort 函数

排序，就是按一定规则重新排列数据。

sort 默认从小到大排，需要头文件 <algorithm>。

从小到大排序

例如，3 1 2 1 排成 1 1 2 3，重复的数会保留。这里 0 <= n <= 100。

#include <iostream>
#include <algorithm>

using namespace std;

int a[110];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}

起点包含，终点不包含。 sort(a, a + n) 排的是 a[0] 到 a[n-1]，不是排到 a[n]。

sort 会修改原数组，不会返回一个新数组。

从大到小排序

自己写比较函数 cmp。cmp(a, b) 返回 true，表示 a 排在 b 前面。

bool cmp(int a, int b) {
    return a > b;
}

a > b 从大到小，a < b 从小到大。把 cmp 写在 main 前面，再这样调用：

sort(a, a + n, cmp);

传进去的是 cmp，不是 cmp()。 比较过程由 sort 调用，不是我们在这里先调用一次。

排序范围

下标从 1 开始

如果把数据存到 a[1] 至 a[n]：

for (int i = 1; i <= n; i++) cin >> a[i];

sort(a + 1, a + n + 1);

for (int i = 1; i <= n; i++) cout << a[i] << ' ';

起点是 a + 1，终点是 a + n + 1，仍然不包含终点。

只排一段

数组下标从 0 开始，想对 [l, r] 这一段排序，写成：

sort(a + l, a + r + 1);

这里保证 0 <= l <= r < n，其他位置不动。

字符串排序

给一个字符串里的字符排序

string s = "cab";
sort(s.begin(), s.end()); // s变成abc

给一组字符串排序

string s[110];
int n;
cin >> n; // 0 <= n <= 100

for (int i = 0; i < n; i++) cin >> s[i];

sort(s, s + n);

for (int i = 0; i < n; i++) cout << s[i] << '\n';

使用 string，还需要头文件 <string>。默认按字典序排，不按长度排。

字符串按字符比较，不按数值大小。 比如 "10" 排在 "2" 前面，因为第一个字符 '1' 小于 '2'。

常见错误

先读入，再排序，最后输出。 别把 sort 写进读入循环，每读一个数就排一次。

比较函数，不能用 >= 或 <=。

两个值相等时，比较结果应当是 false。想从大到小，写 a > b，不能写 a >= b。

区间末尾，别多一位或少一位。

排序范围与实际存储下标对应，别把没输入的元素排进去，也别漏掉最后一个元素。