排序

前言

假设你手里有一副打乱的扑克牌，想快速找到最小的那张。如果牌是乱序的，你得一张一张翻——最坏翻 52 张。但如果先把牌从小到大排好，最小的一张就在最上面，一眼看到。

排序就是这么一个”先花时间建立秩序，后面所有操作都变快”的过程。找中位数？排好序直接取中间。去重？排好序相邻比较。找”差最小的数对”？排好序相邻的差就是候选。可以说排序是算法工具箱里的万能钥匙——先把数据排好序，很多问题自然就解决了。

问题的本质

排序的核心价值不是”得到一个有序的数组”本身，而是有序性带来的后续便利。排序后，数据有了单调性——从小到大递增（或从大到小递减）。单调性可以大幅降低搜索、匹配、统计的代价。

举个例子：给你 1000 个学生的成绩，问”成绩第 10 名是多少分”。乱序时要排序才知道（$O(n \log n)$），排序后直接看第 10 个位置（$O(1)$）。

理论 + 代码

C++ 中的排序

比赛中不需要手写排序算法，直接用 std::sort：

#include <algorithm>
using namespace std;

int a[100];

sort(a, a + n);                             // 升序（从小到大）
sort(a, a + n, greater<int>());             // 降序（从大到小）

// 自定义规则：先按成绩降序，成绩相同按学号升序
struct Student { int score, id; };
Student stu[100];

sort(stu, stu + n, [](const Student& l, const Student& r) {
    // ① lambda 表达式：定义"小于"的比较规则
    // 返回 true 表示 l 应该排在 r 前面
    if (l.score != r.score) return l.score > r.score;  // 成绩高的在前
    return l.id < r.id;                                  // 成绩相同，学号小的在前
});

• ① Lambda 表达式 [](const Student& l, const Student& r) { ... } 就是一个匿名的比较函数。sort 会反复调用它来决定两个元素谁该排在前面。返回 true 表示 l 排在 r 前面。

std::sort 的实现是 Introsort（快排 + 堆排的混合体），最坏 $O(n \log n)$。你只需要记住一件事：排序 $n$ 个数，时间 $O(n \log n)$。$n = 10^7$ 时 $n \log n \approx 2.3 \times 10^8$，1 秒内能跑完。

排序的应用：逆序对

逆序对是排序的一个重要应用。什么是逆序对？在一个数组中，如果 $i < j$ 但 $a_i > a_j$，那 $(i, j)$ 就是一个逆序对。比如数组 [3, 1, 2]：$(3,1)$ 和 $(3,2)$ 都是逆序对，共 2 个。

为什么逆序对重要？它衡量了数组”有多乱”——完全有序的数组逆序对为 0，完全逆序的数组逆序对最多。很多问题可以转化为”统计逆序对”。

怎么求？朴素做法是双重循环 $O(n^2)$，$n = 10^5$ 时太慢。聪明的做法是在归并排序的过程中统计。

归并排序的思想：把数组分成两半，分别排序，再合并。合并时，如果左半的当前元素 > 右半的当前元素，说明左半剩余的所有元素都和右半当前元素构成逆序对——因为左半已经有序了，剩余的元素只会更大。

long long merge_count(int a[], int l, int r) {
    // 对 a[l..r) 排序并统计逆序对
    if (r - l <= 1) return 0;    // ① 只有一个元素，没有逆序对

    int m = (l + r) / 2;
    long long cnt = merge_count(a, l, m)    // ② 左半的逆序对
                  + merge_count(a, m, r);   // ③ 右半的逆序对

    // ④ 合并两个有序半段，统计跨左右的逆序对
    int buf[200010];
    int i = l, j = m, k = 0;

    while (i < m && j < r) {
        if (a[i] <= a[j]) {
            buf[k++] = a[i++];    // ⑤ 左半元素更小，直接复制
        } else {
            // ⑥ 关键！a[i] > a[j]，而且左半已经有序
            // 所以 a[i], a[i+1], ..., a[m-1] 全都 > a[j]
            buf[k++] = a[j++];
            cnt += m - i;          // ⑦ 一次性加上 m-i 个逆序对
        }
    }
    while (i < m) buf[k++] = a[i++];   // ⑧ 左半剩余
    while (j < r) buf[k++] = a[j++];   // ⑨ 右半剩余

    for (int t = 0; t < k; t++)
        a[l + t] = buf[t];              // ⑩ 写回原数组

    return cnt;
}

走一遍具体过程：数组 [3, 1, 2]。

1. 分成 [3] 和 [1, 2]。
2. [3] 只有一个元素，逆序对 = 0。
3. [1, 2]：分成 [1] 和 [2]，合并时 $1 \le 2$，逆序对 = 0。
4. 合并 [3] 和 [1, 2]：
   • 比较 $3$ 和 $1$：$3 > 1$，所以 $3$ 和 $1$ 构成逆序对。左半剩余 $m-i = 1-0 = 1$ 个元素，cnt += 1。复制 $1$。
   • 比较 $3$ 和 $2$：$3 > 2$，所以 $3$ 和 $2$ 构成逆序对。cnt += 1。复制 $2$。
   • 左半还剩 $3$，复制 $3$。
5. 最终 cnt = 0 + 0 + 2 = 2。和手动数的一致。✓

例题

例题 1：M&A 027 — Sorting（★1）

题目：给定长度为 $N$ 的数组 $A_1, A_2, \ldots, A_N$，将其升序排列后输出。

数据范围：$2 \le N \le 200000$，$1 \le A_i \le 10^9$

—— AtCoder M&A 027

思路：裸排序。直接 std::sort，时间 $O(N \log N)$。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    long long a[200010];
    for (int i = 0; i < N; i++)
        scanf("%lld", &a[i]);

    sort(a, a + N);    // ① 排序。[a, a+N) 是待排序的范围

    for (int i = 0; i < N; i++) {
        if (i) printf(" ");    // ② 第一个数前面不加空格
        printf("%lld", a[i]);
    }
    printf("\n");
}

逐行解析：

• ① sort(a, a + N)：a 是数组首地址，a + N 是末尾之后的位置。sort 会原地排好序，不返回新数组。时间 $O(N \log N)$，$N = 200000$ 时约 $200000 \times 17 \approx 3.4 \times 10^6$，瞬间完成。
• ② 输出格式控制：第一个数前面不加空格，后面的数前面加空格。这是 AtCoder 常见的输出格式。

---

例题 2：M&A 013 — Divisor Enumeration（★1）

题目：给定整数 $N$，枚举 $N$ 的所有约数，按升序输出。

数据范围：$1 \le N \le 10^{13}$

—— AtCoder M&A 013

思路：约数的枚举方法：从 $1$ 到 $\sqrt{N}$ 试除，每找到一个约数 $i$，就同时得到了一对约数 $(i, N/i)$。最后把所有约数排序输出。

为什么只需要试到 $\sqrt{N}$？和02-02 素数判定同理：如果 $i \times j = N$ 且 $i \le j$，则 $i \le \sqrt{N}$。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    vector<long long> divs;
    for (long long i = 1; i * i <= N; i++) {   // ① 枚举到 √N
        if (N % i == 0) {
            divs.push_back(i);                  // ② i 是约数
            if (i != N / i)
                divs.push_back(N / i);           // ③ N/i 也是约数（避免重复）
        }
    }

    sort(divs.begin(), divs.end());              // ④ 排序

    for (int i = 0; i < (int)divs.size(); i++) {
        printf("%lld\n", divs[i]);               // ⑤ 逐行输出
    }
}

逐行解析：

• ① i * i <= N：等价于 i <= sqrt(N)，但避免浮点运算。i 是 long long——$N$ 最大 $10^{13}$，$\sqrt{N} \approx 3.2 \times 10^6$，i * i 最大约 $10^{13}$，用 int 会溢出。
• ③ 如果 $i \neq N/i$（即 $N$ 不是完全平方数，$i$ 不是 $\sqrt{N}$），则 $N/i$ 是另一个不同的约数。比如 $N = 12, i = 2$ 时，$N/i = 6$ 也要加入。
• ④ 约数是按 $i$ 从小到大找到的，但 $N/i$ 可能比 $i$ 大也可能已经乱序。所以全部加入 vector 后排序一次。

走一遍过程：$N = 12$。

$i$	$12 \% i$	约数	vector
1	0	1, 12	{1, 12}
2	0	2, 6	{1, 12, 2, 6}
3	0	3, 4	{1, 12, 2, 6, 3, 4}
4	$16 > 12$，循环结束

排序后：{1, 2, 3, 4, 6, 12}。✓

---

例题 3：Tessoku Book — A13 Close Pairs

题目：黑板上写着 $N$ 个整数，已按从小到大排列为 $A_1 < A_2 < \cdots < A_N$。从这 $N$ 个数中选两个不同的数，有多少种选法使得它们的差不超过 $K$（即 $A_j - A_i \le K$）？

数据范围：$1 \le N \le 100000$，$1 \le K \le 10^9$，$1 \le A_1 < A_2 < \cdots < A_N \le 10^9$

—— AtCoder Tessoku Book A13

思路：数据已经有序。对每个 $i$，找最大的 $j$ 使得 $A_j - A_i \le K$。因为数组有序，满足条件的 $j$ 是连续的一段，可以用二分搜索（upper_bound）或双指针。

用双指针：右指针 r 从 $i+1$ 开始，只要 $A_r - A_i \le K$ 就右移。最终 $r - i - 1$ 就是以 $i$ 为左端点、满足条件的数对数。

但注意这里 $N = 10^5$，双重循环+双指针的总时间是 $O(N)$（每个指针只往右走），绰绰有余。不过更简洁的写法是对每个 $i$ 用 upper_bound。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    long long K;
    scanf("%d%lld", &N, &K);
    long long A[100010];
    for (int i = 0; i < N; i++)
        scanf("%lld", &A[i]);

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        // ① 找第一个 > A[i] + K 的位置
        long long *p = upper_bound(A + i + 1, A + N, A[i] + K);
        // ② p - (A + i + 1) = 满足 A[j] - A[i] <= K 的 j 的个数
        ans += p - (A + i + 1);
    }
    printf("%lld\n", ans);
}

逐行解析：

• ① upper_bound(A + i + 1, A + N, A[i] + K)：在 $A_{i+1}$ 到 $A_{N-1}$ 中找第一个大于 $A_i + K$ 的位置。因为数据有序，$A_j \le A_i + K$ 等价于 $A_j - A_i \le K$。
• ② p - (A + i + 1)：从 $A_{i+1}$ 到 $p$ 之前的位置都满足 $A_j - A_i \le K$。个数 = 指针之差。

走一遍过程：$N = 7, K = 10$，$A = [11, 12, 16, 22, 27, 28, 31]$。

• $i=0, A[0]=11$：找 $\le 21$ 的。12, 16 满足。贡献 2。
• $i=1, A[1]=12$：找 $\le 22$ 的。16, 22 满足。贡献 2。
• $i=2, A[2]=16$：找 $\le 26$ 的。22 满足。贡献 1。
• $i=3, A[3]=22$：找 $\le 32$ 的。27, 28, 31 满足。贡献 3。
• $i=4, A[4]=27$：找 $\le 37$ 的。28, 31 满足。贡献 2。
• $i=5, A[5]=28$：找 $\le 38$ 的。31 满足。贡献 1。

总计 $2+2+1+3+2+1 = 11$。✓

---

例题 4：M&A 074 — Sum of difference Easy（★2）

题目：给你 $N$ 个整数 $A_1 < A_2 < \cdots < A_N$（已排序）。求 $\displaystyle\sum_{i=1}^{N}\sum_{j=i+1}^{N}(A_j - A_i)$ 的值。

数据范围：$2 \le N \le 200000$，$1 \le A_1 < A_2 < \cdots < A_N \le 10^6$

—— AtCoder M&A 074

思路：数据已经有序，所以 $A_j > A_i$（$j > i$），绝对值可以直接去掉。对每个 $j$，它对总和的贡献是 $\sum_{i=1}^{j-1}(A_j - A_i) = (j-1) \times A_j - S_{j-1}$，其中 $S_{j-1}$ 是前 $j-1$ 个数的前缀和。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    long long a[200010];
    for (int i = 0; i < N; i++)
        scanf("%lld", &a[i]);

    // ① 前缀和
    long long S[200010];
    S[0] = 0;
    for (int i = 1; i <= N; i++)
        S[i] = S[i - 1] + a[i - 1];

    // ② 对每个 j，计算它和左边所有数的差之和
    long long ans = 0;
    for (int j = 1; j <= N; j++) {
        ans += (long long)(j - 1) * a[j - 1] - S[j - 1];
    }
    printf("%lld\n", ans);
}

逐行解析：

• ① 前缀和 $S[i] = a[0] + \cdots + a[i-1]$。
• ② (j-1) * a[j-1] - S[j-1]：$A_j$ 和左边 $j-1$ 个数的差之和。左边有 $j-1$ 个数，每个和 $A_j$ 的差是 $A_j - A_i$，差之和 = $(j-1) \times A_j - \text{前 } j-1 \text{ 个数的和}$。

验证：$A = [1, 3, 5]$。

• $j=1$：左边 0 个，贡献 $0$。
• $j=2$：$1 \times 3 - 1 = 2$（$3-1=2$）✓
• $j=3$：$2 \times 5 - 4 = 6$（$(5-1)+(5-3)=6$）✓

总和 $= 0 + 2 + 6 = 8$。手动验证：$(3-1)+(5-1)+(5-3) = 2+4+2 = 8$。✓

---

例题 5：M&A 076 — Sum of difference（★3）

题目：给你 $N$ 个整数 $A_1, A_2, \ldots, A_N$（不一定有序）。求所有数对的差的绝对值之和：$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i - A_j|$。

数据范围：$2 \le N \le 2 \times 10^5$，$|A_i| \le 10^8$

—— AtCoder M&A 076

思路：和例题 4 几乎一样，但数据不一定有序，还有负数。解法：先排序，排序后绝对值直接去掉，变成和例题 4 一样的前缀和问题。

$N = 2 \times 10^5$，双重循环 $O(N^2) \approx 4 \times 10^{10}$ 绝对 TLE。排序 + 前缀和是 $O(N \log N)$，绰绰有余。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    long long a[200010];
    for (int i = 0; i < N; i++)
        scanf("%lld", &a[i]);

    sort(a, a + N);    // ① 先排序——这是关键一步

    long long S[200010];
    S[0] = 0;
    for (int i = 1; i <= N; i++)
        S[i] = S[i - 1] + a[i - 1];

    long long ans = 0;
    for (int j = 1; j <= N; j++)
        ans += (long long)(j - 1) * a[j - 1] - S[j - 1];
    // ② (j-1) 最大 ~2×10^5，a[j-1] 最大 10^8
    //    乘积最大 ~2×10^13，必须用 long long

    printf("%lld\n", ans);
}

逐行解析：

• ① 排序是这道题的灵魂。排序前 $|A_i - A_j|$ 里有绝对值，没法化简。排序后 $A_j \ge A_i$（当 $j > i$），$|A_j - A_i| = A_j - A_i$，绝对值消失。这就把问题转化成了例题 4。
• ② (long long)(j - 1) * a[j - 1]：隐式类型转换。(j-1) 最大约 $2 \times 10^5$，a[j-1] 最大 $10^8$，乘积约 $2 \times 10^{13}$，远超 int 的 $2 \times 10^9$。不加强转就会溢出，答案错误。

这道题展示了排序的核心价值：数据有序后，绝对值可以去掉，问题立刻变简单。类似地，00-03 累积和与差分 中前缀和的应用也需要先排序作为前提。

参考文献

教材讲解 — 競技プログラミングの鉄則

• 第 3 章 3.1 B11 Binary Search 2（sort + lower_bound 解说）
• 排序在教材中作为工具使用（如二分前先 sort），非独立章节

基础练习 — アルゴリズムと数学 演習問題集

• 027 Sorting（归并排序实现）【例题】
• 013 Divisor Enumeration（约数排序输出）【例题】
• 074 Sum of difference Easy（排序+前缀和）【例题】
• 076 Sum of difference（排序+前缀和）【例题】
• 077 Distance Sum（排序坐标+前缀和）
• 094 Maximal Value（贪心+取min）

系统练习 — 競技プログラミングの鉄則

• A13 Close Pairs（排序+双指针）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化