第 43 章排序全景——八种排序的对比与选择

🏗️ 前情回顾：M6 一共 6 章，你学完了复杂度分析（第 38 章）、三种 O(n²) 排序（第 39 章）、sort 与自定义排序（第 40 章）、归并和快排（第 41 章）、计数和基数排序（第 42 章）。现在你的"排序工具箱"里至少有八种工具——但它们各有各的性格和适用场景。最后一章，我们来做一次大总结，把所有的排序放到一张表里对比，再学习排序的经典应用——逆序对。

🎯 本章目标

学完这一章，你能：

用一张对比表记住八种排序的时间/空间/稳定性/适用场景
面对一道题，快速判断应该用哪种排序
理解竞赛中的黄金法则：sort 优先
理解逆序对的概念
掌握用归并排序求逆序对的方法
了解树状数组求逆序对的思路
完成几道排序综合题，巩固整个模块

📖 故事引入

小海在做 CSP-J 的历年真题。他发现一个规律：几乎每套卷子都有一道题需要排序。

有的题直接说"请输出排序后的结果"——简单的 sort 一行搞定。有的题说"求交换了多少次"——这就是在考逆序对。有的题说"求第 k 小的数"——既可以用 sort 后取第 k 个，也可以用快速选择。

小海意识到：排序不是终点，而是解题的起点。排序之后，很多问题迎刃而解。今天我们就来把整个排序工具箱清点一遍，看看什么武器对付什么敌人最有效。

🧱 知识讲解

43.1 八种排序全景对比表

排序算法	平均时间	最坏时间	空间	稳定性	适用场景
冒泡	O(n²)	O(n²)	O(1)	✅ 稳定	教学、小数据
选择	O(n²)	O(n²)	O(1)	❌ 不稳定	交换次数最少
插入	O(n²)	O(n²)	O(1)	✅ 稳定	基本有序时极快
归并	O(n log n)	O(n log n)	O(n)	✅ 稳定	求逆序对、稳定排序
快速	O(n log n)	O(n²)	O(log n)	❌ 不稳定	通用（sort 的基础）
sort()	O(n log n)	O(n log n)	—	❌ 不稳定	竞赛首选
计数	O(n+MAXV)	O(n+MAXV)	O(MAXV)	✅ 稳定	值域小的整数
基数	O(d×n)	O(d×n)	O(n)	✅ 稳定	值域大但位数少的整数

43.2 什么时候用什么排序——决策指南

第一步：看题目要求

题目说"请使用冒泡排序" → 必须手写冒泡
题目说"请输出排序结果" → 直接 sort()
题目没有要求指定算法 → sort() 优先！

第二步：看数据特征

n ≤ 1000，数据范围很大 → sort()（O(n log n) 足够快）
n = 10⁶，值域在 0~1000 → 计数排序（O(n) 更优）
n = 10⁶，值域在 0~10⁹ → sort()（计数开不出这么大的数组）
数据基本有序 → sort() 已经足够好，不需要特殊处理
字符串 → sort() + 自定义 cmp

第三步：看特殊需求

需要稳定性 → stable_sort() 或归并排序
需要在排序过程中做额外工作 → 归并排序（如求逆序对）
快速求前 k 小 → nth_element() 或快速选择

🏆 竞赛黄金法则：

能用 sort() 就用 sort()。
除非题目强迫你手写，否则不要自讨苦吃。
sort() 背后的内省排序已经帮你把快排、堆排、插入排序混合到最优。
你的任务不是发明轮子，而是用轮子造车。

43.3 逆序对——排序的经典应用

定义：在一个序列中，如果 i < j 但 a[i] > a[j]，则 (a[i], a[j]) 构成一个逆序对。

例如 [3, 1, 4, 2] 中的逆序对：

(3, 1)：3 在 1 前面但比 1 大 → 逆序
(3, 2)：3 在 2 前面但比 2 大 → 逆序
(4, 2)：4 在 2 前面但比 2 大 → 逆序
共 3 个逆序对

现实意义：逆序对的数量 = 用相邻交换使序列有序的最少交换次数（冒泡排序的交换次数）。

为什么用归并排序求逆序对？

在归并的"合并"阶段，当 a[i] > a[j]（左半的某个元素大于右半的某个元素）时，由于左右两半各自已经有序，a[i] 到 a[mid] 的所有元素都大于 a[j]，一下子贡献了 mid - i + 1 个逆序对！

归并排序求逆序对实现：

cpp

long long mergeCount(int l, int mid, int r) {
    long long inv = 0;                      // 逆序对可能很多，用 long long！
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            inv += (mid - i + 1);           // ✅ 核心：a[i..mid] 都 > a[j]
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
    return inv;
}

long long countInversions(int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long inv = 0;
    inv += countInversions(l, mid);       // 左半内部的逆序对
    inv += countInversions(mid + 1, r);   // 右半内部的逆序对
    inv += mergeCount(l, mid, r);         // 跨越左右的逆序对
    return inv;
}

📝 复杂度 O(n log n)，和归并排序一样。

树状数组求逆序对（简要介绍）：

另一种方法是用树状数组（M8 详细讲）：将数组元素的值作为树状数组的下标，从后往前遍历，查询比当前元素小的元素个数。时间复杂度也是 O(n log n)，但需要离散化处理大值域。两种方法竞赛中都会考，掌握归并法即可应对大部分题目。

43.4 排序综合题实战

例题：火柴排队（NOIP 2013 提高组简化版）

题意：有两个长度均为 n 的序列 A 和 B，你可以交换 A 中相邻两个元素的位置。问最少需要交换多少次，使得对应位置的差值之和最小。

思路：

要让差值之和最小 → A 和 B 的"大小排名"应该对齐
对 A 排序，记录每个元素原来的位置
对 B 排序，同样记录位置
构造一个数组 P：P[a 某元素原始位置] = b 对应排名元素的原始位置
求 P 的逆序对个数 = 答案

这就是一道把排序和逆序对结合在一起的综合题。

✋ 动手试试

试试 1：手动求 [5, 3, 1, 4, 2] 的逆序对数量。建议把数写下来，用冒泡排序的交换次数来验证。

试试 2：写一个程序，输入 n 个数，分别用以下方法求逆序对，对比结果：

方法 A：双重循环暴力 O(n²)（n ≤ 10000 验证小数据）
方法 B：归并排序 O(n log n)

试试 3：整理你的排序工具箱——用一句话描述每种排序，做成一张"速查卡片"，贴在笔记本上。

⚠️ 容易犯的错

错 1：逆序对结果用 int 存

❌ 10⁵ 个降序排列的数，逆序对数量 ≈ n²/2 ≈ 5×10⁹，超过 int 范围（约 2.1×10⁹）

✅ 逆序对数量用 long long 存储！

错 2：归并求逆序对写成 `a[i] < a[j]` 时计数

❌ 当 a[i] < a[j] 时才计数——这和逆序对的定义反了

✅ 当 a[i] > a[j] 时计数：inv += mid - i + 1

错 3：不知道什么场景用计数排序

❌ 值域 [0, 10⁹] 还要手写计数排序，结果 RE

✅ 判断值域！只有 MAXV 在可接受范围（一般 ≤10⁷）才适合

错 4：选择排序的交换次数不是逆序对数

❌ 以为选择排序的交换次数也等于逆序对数

✅ 只有冒泡排序的交换次数 = 逆序对数（因为冒泡每次交换相邻两个）。选择排序的交换可能一下子跨过好几个元素，和逆序对不是同一回事

📝 练习

基础题

1. 选择题

（1）以下哪种排序在任何情况下都是 O(n log n)？
A. 快速排序 B. 冒泡排序 C. 归并排序 D. 插入排序

（2）逆序对的定义是：
A. i<j 且 a[i] > a[j] B. i>j 且 a[i] < a[j] C. i<j 且 a[i] < a[j] D. a[i] 和 a[j] 符号不同

（3）序列 [1, 3, 5, 2, 4, 6] 有多少个逆序对？
A. 2 B. 3 C. 4 D. 5

2. 填空题

（1）竞赛中排序的黄金法则是 ____________。

（2）当 n=10⁵ 且值域在 [0, 10⁶] 时，可选 ______ 排序（O(n)）或 ______（O(n log n)）。

（3）求逆序对数量时，返回值类型要用 ______，防止溢出。

提高题

3. 编程题 — 逆序对计数

输入 n（1 ≤ n ≤ 10⁵）和 n 个整数，用归并排序计算序列中逆序对的总数，输出结果。

4. 编程题 — 排序综合

某竞赛有 n 名选手，每人有姓名（string）、年龄（int）、总分（int）。

按以下规则排名：

总分降序
总分相同按年龄升序
前两者相同按姓名升序

按要求输出排名结果，并在最后输出："冒泡排序如果能达到 O(n²)，交换次数至少为 _____ 次"（填这段序列按年龄升序排列时的逆序对数）。

挑战题

5. 编程题 — 最少交换次数

输入一个 1~n 的排列（每个数恰好出现一次）。每次操作可以交换任意两个位置的元素。问最少需要多少次交换才能将排列变为升序。

（提示：这和"最少相邻交换"（逆序对）不同！考虑排列中的"环"：每个元素指向它应该在的位置。一个长度为 k 的环需要 k-1 次交换。最终答案 = n - 环的数量。）

例如 [2, 3, 1, 5, 4]：环 1: 2→3→1 (长度3，需2次)，环 2: 5→4 (长度2，需1次)，共需 2+1=3 次交换。

🧠 本章小结

排序全景对比：
  O(n²)   → 冒泡、选择、插入        (小数据/有序)
  O(n log n) → 归并、快排、sort()   (通用/竞赛首选)
  O(n)     → 计数、基数              (特殊条件)

排序优先级：
  sort() > 计数排序 > 手写归并/快排 > O(n²)排序

逆序对：
  定义：i < j 且 a[i] > a[j]
  求法1：归并排序 → merge 时统计 mid-i+1
  求法2：树状数组（M8 详解）
  应用：冒泡排序交换次数 = 逆序对数

M6 模块总结：
  36→37 复杂度分析（衡量速度的工具）
  38    基础排序（理解排序的起点）
  39    sort 与自定义（竞赛中的主力）
  40    分治排序（理解 O(n log n) 的原理）
  41    非比较排序（见识 O(n) 的可能）
  42    全景对比与逆序对（融会贯通）

📝 配套练习

共6题。M6收官——不复用新题，用旧题在新视角下重新审视排序选择策略。。★核心（课堂必做） ◆拓展（课后练习） ★★★挑战（选做）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1059	https://hydro.ac/p/luogu-P1059	sort版vs手写版、对比
◆ 拓展	luogu-P1093	https://hydro.ac/p/luogu-P1093	sort+cmp（复用演示熟练度）
◆ 拓展	luogu-P1908	https://hydro.ac/p/luogu-P1908	归并排序（复用强调整体观）
◆ 拓展	luogu-P1271	https://hydro.ac/p/luogu-P1271	计数排序（复用演示值域条件）
◆ 拓展	—	—	八种排序选择决策树：给6个场景选最优排序
★★★ 挑战	luogu-P1177	https://hydro.ac/p/luogu-P1177	大数据排序、O(nlogn)极限测试
◆ 拓展	luogu-P7910	https://hydro.ac/p/luogu-P7910	CSP-J2021、sort应用
◆ 拓展	luogu-P7186	https://hydro.ac/p/luogu-P7186	CRCI、表格排序

💡 练习建议：先完成 2 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节；★★★挑战题建议在完成拓展题后再做，涉及多知识点综合。

配套练习

共6题。M6收官——不复用新题，用旧题在新视角下重新审视排序选择策略。★核心（课堂必做） · ◆拓展（课后练习） · ★★★挑战（选做）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1059	https://hydro.ac/p/luogu-P1059	sort版vs手写版、对比
◆ 拓展	luogu-P1093	https://hydro.ac/p/luogu-P1093	sort+cmp（复用演示熟练度）
◆ 拓展	luogu-P1908	https://hydro.ac/p/luogu-P1908	归并排序（复用强调整体观）
◆ 拓展	luogu-P1271	https://hydro.ac/p/luogu-P1271	计数排序（复用演示值域条件）
◆ 拓展	—	—	八种排序选择决策树：给6个场景选最优排序
★★★ 挑战	luogu-P1177	https://hydro.ac/p/luogu-P1177	大数据排序、O(nlogn)极限测试
◆ 拓展	luogu-P7910	https://hydro.ac/p/luogu-P7910	CSP-J2021、sort应用
◆ 拓展	luogu-P7186	https://hydro.ac/p/luogu-P7186	CRCI、表格排序

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节；★★★挑战题建议在完成拓展题后再做，涉及多知识点综合。

自查清单：

[ ] 我能默写八种排序的对比表（时间/空间/稳定性）
[ ] 我面对一道题能判断该用哪种排序
[ ] 我理解并遵循"sort 优先"原则
[ ] 我能用归并排序求逆序对
[ ] 我知道逆序对的结果要用 long long
[ ] 我知道树状数组也能求逆序对（M8 详细展开）

🚀 下章预告：M6 排序模块到此结束，你的基础能力又上了一个台阶！从 M7 开始，我们进入真正的"算法设计"世界——递归的深入应用、贪心策略、分治法的系统学习。准备好迎接更大的挑战了吗？M7《递归、贪心与分治》，我们马上见！

第 43 章 排序全景——八种排序的对比与选择 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

43.1 八种排序全景对比表 ​

43.2 什么时候用什么排序——决策指南 ​

43.3 逆序对——排序的经典应用 ​

43.4 排序综合题实战 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：逆序对结果用 int 存 ​

错 2：归并求逆序对写成 a[i] < a[j] 时计数 ​

错 3：不知道什么场景用计数排序 ​

错 4：选择排序的交换次数不是逆序对数 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​