7.3　比较模型与交换次数

学习目标：学完本节，你能

定义逆序对，并说清它与交换次数的等价关系；
解释为什么随机数组的逆序对数量恰好是 $n^2/4$；
说出"比较模型"的含义，以及它约束的是什么。

先修：7.1（三种排序）、1.3（平均情况）。 固定术语：逆序对、比较模型、相邻交换。 环境与版本：.NET 8 / C# 12。 预计阅读：26 分钟。

一、直觉：什么叫"顺序乱了"

一个数组"有多乱"？这个问题听起来很模糊，但可以用一个精确的量来描述。

看这一对：

数组:  [5, 2, 4, 1, 3]
        ↑
      5 在 2 前面

5 比 2 大，但 5 排在 2 前面 —— 这一对的顺序"反了"。

再看一对：2 和 4，2 比 4 小且排在前面 —— 这一对的顺序是对的。

把所有"顺序反了"的元素对都数出来，就得到了这个数组的混乱程度。

这个量叫逆序对（Inversion）。

二、形式化：逆序对的定义

逆序对：一对下标 $(i, j)$，满足 $i < j$ 且 $a[i] > a[j]$。

几个直接的推论：

数组	逆序对数量	说明
`[1, 2, 3, 4, 5]`	0	完全有序
`[5, 4, 3, 2, 1]`	$\frac{n(n-1)}{2} = 10$	完全逆序，每一对都是逆序
`[5, 2, 4, 1, 3]`	?	待计算

关键结论：

数组有序 $\iff$ 逆序对数量为 0。

因为"有序"的定义就是"不存在 $i < j$ 且 $a[i] > a[j]$"。

所以：排序的过程，就是不断消除逆序对的过程。

三、核心定理：逆序对数量 = 交换次数

这是本节最重要的结论：

对只做"相邻交换"的排序（冒泡、插入）， 总的交换/移动次数，恰好等于数组初始的逆序对数量。

为什么必然相等？两步论证：

第 1 步：一次相邻交换，恰好消除一个逆序对。

交换前:  ... 8, 3 ...     8 > 3，这是一个逆序对
交换后:  ... 3, 8 ...     顺序对了，这个逆序对被消除

那会不会影响到别的逆序对？ 不会。因为：

交换只涉及相邻的两个元素
对于数组里其他任何元素 x，它和 8、3 的相对位置没有变（8 和 3 只是互换了，对 x 而言左边还是那两个位置）
所以"x 和 8""x 和 3"是不是逆序对，完全不受影响

一次交换，净效果就是消除一个逆序对。

第 2 步：排序结束时逆序对数量为 0。

这是第 2 节的结论。

所以： 从初始的 $I$ 个逆序对，到结束时的 0 个，需要消除 $I$ 个逆序对。而每次交换消除恰好 1 个 —— 所以总共需要 $I$ 次交换。 ∎

四、实测验证

用四种输入验证这个等式（$n = 5000$）：

  输入         |      逆序对数量 |    插入排序移动 |    冒泡排序交换 |   三者一致
------------------------------------------------------------------------------------
  随机         |       6,158,004 |       6,158,004 |       6,158,004 |      是 ✓
  已排序       |               0 |               0 |               0 |      是 ✓
  完全逆序     |      12,497,500 |      12,497,500 |      12,497,500 |      是 ✓
  近乎有序     |          35,134 |          35,134 |          35,134 |      是 ✓

四个输入下，三个数字完全相等。

再看一个小例子的逐轮过程（数组 [5, 2, 4, 1, 3]）：

  逆序对总数 = 7

  第 1 轮：交换 5 和 2  ->  [2, 5, 4, 1, 3]
  第 1 轮：交换 5 和 4  ->  [2, 4, 5, 1, 3]
  第 1 轮：交换 5 和 1  ->  [2, 4, 1, 5, 3]
  第 1 轮：交换 5 和 3  ->  [2, 4, 1, 3, 5]
  第 2 轮：交换 4 和 1  ->  [2, 1, 4, 3, 5]
  第 2 轮：交换 4 和 3  ->  [2, 1, 3, 4, 5]
  第 3 轮：交换 2 和 1  ->  [1, 2, 3, 4, 5]

  交换次数 = 7，逆序对数量 = 7  —— 一模一样。

注意第一轮：5 从下标 0 一路冒到下标 3，连续交换了 4 次。

而 5 的逆序对恰好就是它和 2, 4, 1, 3 这 4 个数组成的 —— 每一对都由一次交换消除。

这个定理还有个实用的副产品：

数一个数组的逆序对数量，等价于问"用冒泡排序要交换多少次"。

而反过来：如果你想知道"这个数组乱不乱"，可以直接跑一遍插入排序数移动次数。但更快的办法是用归并排序的变体，$O(n \log n)$ 就能算出来（8.1 节会讲）。

五、为什么随机数组的逆序对是 $n^2/4$

实测数据：

           n |      逆序对（实测） |              n^2/4 |              n^2/2
--------------------------------------------------------------------------
     1,000 |            241,925 |            250,000 |            500,000
     2,000 |            988,076 |          1,000,000 |          2,000,000
     4,000 |          3,988,639 |          4,000,000 |          8,000,000

随机数组的逆序对数量稳定在 $n^2/4$ 附近 —— 恰好是最大值 $n^2/2$ 的一半。

为什么？用一个非常简单的概率论证：

数组里一共有 $\binom{n}{2} = \frac{n(n-1)}{2}$ 对元素
随机数组中，任取一对元素，它俩"顺序反了"的概率是 $\frac{1}{2}$（大小关系是随机的，一半情况大的在前）
所以期望逆序对数 $= \frac{n(n-1)}{2} \times \frac{1}{2} \approx \frac{n^2}{4}$

这就解释了 7.1 节那个"反直觉"的实测结果：

随机输入下，冒泡排序比较了 1249 万次，而插入排序只比较了 616 万次 —— 正好是一半。

原因：

冒泡每轮都要扫描整个未排序区间，比较次数恒为 $n^2/2$（不受逆序对数量影响）

插入的比较次数直接和"需要移动多少步"挂钩，也就是和逆序对数量成正比 —— 只有 $n^2/4$

这就是为什么插入排序在随机数据上比冒泡快一倍。

六、比较模型

最后一个概念：什么是"比较模型"？

比较模型（Comparison Model）：算法的执行过程中，只能通过"比较两个元素的大小"来获取信息，不能直接查看元素的值。

我们前面学的三种排序，全都属于比较排序 —— 它们只做 a[j] > a[j+1] 这样的判断，从没"看过"元素具体是几。

这个限制看起来很弱，其实很强：

你能做的	你不能做的
判断 `a < b`、`a > b`、`a == b`	知道 `a` 的具体数值
根据比较结果决定下一步	直接算出 `a` 应该放在哪个下标
交换、移动元素	用数值做索引

为什么要专门定义这个模型？

因为下一节要证明的下界 $O(n \log n)$，就是在这个模型下成立的。

它约束的是"信息获取方式" —— 如果你只能靠比较来获得信息，那你的"信息量"增长是有上限的。

而 8.4 节的计数排序和基数排序跳出了这个模型（它们直接看元素的值），所以能突破这条下界。

理解"模型"这个概念很重要：很多理论结论都带有前提，前提不成立，结论就不适用。

七、练习

练习 7.3.1（数逆序对）手工数出下面数组的逆序对数量，并列出全部逆序对： [3, 1, 4, 1, 5, 9, 2, 6]

练习 7.3.2（推理）一个数组有 100 个元素。 (a) 逆序对最多可能是多少？此时数组长什么样？ (b) 逆序对最少可能是多少？此时数组长什么样？ (c) 如果逆序对数量是 0，用插入排序要移动多少次？比较多少次？

练习 7.3.3（判断）判断对错并说明理由： (a) 逆序对数量相同的两个数组，"乱的程度"是一样的。 (b) 插入排序的移动次数一定等于逆序对数量，不管数组内容如何。 (c) 归并排序也是比较排序，所以它的交换次数也等于逆序对数量。

练习 7.3.4（工程应用）一个监控系统要实时报告"数据流的乱序程度"。数据每秒钟来 1000 条，需要立刻算出当前窗口（最近 10000 条）的逆序对数量。 (a) 用暴力 $O(n^2)$ 的方法能行吗？为什么？ (b) 你有什么改进思路？

练习 7.3.5（挑战·多路逆序对）考虑一个变体问题：定义"三逆序组"为满足 $i < j < k$ 且 $a[i] > a[j] > a[k]$ 的三元组。 (a) 暴力数一遍的复杂度是多少？ (b) 你能想到比暴力更快的方法吗？（提示：先想想如果固定中间的 $j$，问题变成什么。）

八、练习答案

7.3.1

数组 [3, 1, 4, 1, 5, 9, 2, 6]，下标 0~7：

下标 $i$	值	它后面比它小的元素	逆序对个数
0	3	1（下标1）、1（下标3）、2（下标6）	3
1	1	无	0
2	4	1（下标3）、2（下标6）	2
3	1	无	0
4	5	2（下标6）	1
5	9	2（下标6）、6（下标7）	2
6	2	无	0
7	6	—	0

总逆序对数量 = 3 + 0 + 2 + 0 + 1 + 2 + 0 = 8

全部逆序对：

(3,1) (3,1) (3,2)
(4,1) (4,2)
(5,2)
(9,2) (9,6)

注意第一个 3 后面有两个 1（下标 1 和下标 3）—— 它们是两个不同的逆序对，因为下标不同。

逆序对是"下标对"，不是"值对"。

7.3.2

(a) 最多 $\frac{100 \times 99}{2} = 4950$ 个。此时数组完全逆序（从大到小排列）。

(b) 最少 0 个。此时数组已经有序（从小到大）。

(c) 逆序对为 0 意味着数组已经有序：

插入排序的移动次数 = 0（每个元素的位置都是对的，不需要挪）
比较次数 = $n - 1 = 99$ 次（每个元素只和左边第一个比一次，就发现位置对了）

注意比较次数不是 0：插入排序对每个元素 $a[i]$ 至少要比较一次，才能确认"它已经在对的位置上"。这就是 $n-1$ 这个下界的来源。

7.3.3

(a) 基本正确，但要说清楚"乱的程度"这个说法。 逆序对数量确实是一个衡量乱序程度的合理指标，而且它有一个很强的性质：它恰好等于冒泡排序需要的交换次数。

但要注意：逆序对数量相同的两个数组，实际的排序耗时可能不同 —— 因为耗时还受"元素移动的距离""缓存局部性"等因素影响。所以它是"乱序程度"的一个度量，不是"排序耗时"的预测。
(b) 对，这正是本节的核心定理。 而且它不仅对插入排序成立，对任何只做相邻交换的排序都成立（包括冒泡）。

前提是"相邻交换"。如果是长距离交换（比如选择排序），一次交换可能消除多个逆序对，等式就不成立了。
(c) 错。 两个原因：
1. 归并排序做的不是"相邻交换"，而是"跨距离的合并" —— 一次操作可能同时消除多个逆序对。
2. 归并排序甚至不做"交换" —— 它是把元素复制到临时数组再写回来。
  
  有意思的是：归并排序虽然没有"交换次数 = 逆序对数"这个性质，但它可以用来 $O(n \log n)$ 地数出逆序对数量 —— 在合并两个有序段时，如果左边段的一个元素比右边段的某个元素大，那么它比右边段剩下所有元素都大，一次就能数出一批逆序对。这正是练习 7.3.4 的答案。

7.3.4

(a) 不行。

暴力方法是 $O(n^2)$：$n = 10{,}000$ 时是 $10^8$ 次比较。

每秒来 1000 条，意味着每 1 毫秒就有一条新数据
如果每条数据都触发一次全量重算，就是每秒 $1000 \times 10^8 = 10^{11}$ 次比较 —— 完全不可能

(b) 改进思路：

思路 1：用归并排序的变体，$O(n \log n)$

$n = 10{,}000$ 时是 $10^4 \times 14 = 1.4 \times 10^5$ 次操作。每秒 1000 次重算 = $1.4 \times 10^8$ —— 还是太大。

思路 2：增量更新（推荐）

关键观察：窗口是滑动的 —— 每次只移出一个旧元素、移入一个新元素。不需要全量重算。

当窗口从 [a₁...aₙ] 变成 [a₂...aₙ, aₙ₊₁] 时，逆序对的变化是：

新逆序对数量 = 旧数量
             - (a₁ 与后面元素构成的逆序对数量)     ← 移出的元素带走的
             + (aₙ₊₁ 与前面元素构成的逆序对数量)   ← 新元素带来的

而"一个元素与窗口内其他元素构成的逆序对数量"，可以用一个有序结构（比如平衡树或树状数组）在 $O(\log n)$ 内算出来。

总复杂度：每次更新 $O(\log n)$，每秒 1000 次 → $1000 \times 14 = 1.4 \times 10^4$ 次操作。完全可行。

思路 3：近似（如果精确值不是必须的）

如果业务只关心"当前的乱序程度是否异常"，可以采样：只统计一个子集的逆序对，或者用一个更便宜的近似指标（比如"相邻元素的逆序比例"）。

这道题的核心思路是：

不要每次都从头算。找出"变化量"，只计算增量。

这个思想在算法里到处都是 —— 5.4 节的滑动窗口最大值（进出各一个）、6.3 节的哈希表扩容、以及各种"增量更新"的数据结构，本质都是它。

7.3.5

(a) 暴力：三重循环枚举所有 $i < j < k$，复杂度 $O(n^3)$。

(b) 可以降到 $O(n \log n)$ 或 $O(n^2)$，取决于用哪种思路。

思路：固定中间的 $j$。

对于每个 $j$，问题变成：

左边有多少个元素大于 $a[j]$？（记为 $L_j$）
右边有多少个元素小于 $a[j]$？（记为 $R_j$）

那么以 $j$ 为中间元素的"三逆序组"数量就是 $L_j \times R_j$（左边任选一个、右边任选一个，组合起来就满足 $a[i] > a[j] > a[k]$）。

总数量 $= \sum_j L_j \times R_j$。

实现方案：

方案	复杂度	说明
对每个 $j$ 线性扫描左右两边	$O(n^2)$	简单，$n$ 不大时够用
用平衡树 / 树状数组维护"已见过的元素"	$O(n \log n)$	从左扫一遍算 $L_j$，从右扫一遍算 $R_j$

$O(n \log n)$ 的做法：

1. 从左到右扫描，用一个有序结构（如 SortedSet 或树状数组）维护已见过的元素，
   对每个 j 查询"比 a[j] 大的有多少个" -> L_j
2. 从右到左扫描，同理查询"比 a[j] 小的有多少个" -> R_j
3. 累加 L_j * R_j

这个"固定中间元素，拆成左右两个独立问题"的思路非常通用。

7.3 节的正题（数二维逆序对）是"固定一个，看另一个"；这里是"固定中间，看两边"。这类问题的通用解法都是"降低一维" —— 和 3.3 节练习 3.3.5 的"三数之和"是同一个套路。

注意：$O(n \log n)$ 的解法需要"有序结构"，而 SortedSet<T> 在 .NET 里就是基于红黑树实现的（第 10 章之后会讲到）。在只用数组的情况下，$O(n^2)$ 已经是能做到的最好了。

九、常见错误

误区	纠正
把逆序对当成"值对"	逆序对是下标对。数组 `[3,1,1]` 里有两个逆序对（两个 `1` 下标不同）。
认为"逆序对 = 交换次数"对所有排序都成立	只对相邻交换的排序成立。归并排序不做交换，选择排序做长距离交换。
认为归并排序也能用这个等式	归并排序的"一次操作"可能消除多个逆序对。但它可以用来快速数逆序对。
以为随机数组的逆序对是 $n^2/2$	是 $n^2/4$。因为随机取一对，顺序反了的概率只有一半。
认为"比较模型"是废话	它划定了下界的适用范围。8.4 节的非比较排序正是靠跳出这个模型才突破了 $O(n \log n)$。

十、本节总结

逆序对：满足 $i < j$ 且 $a[i] > a[j]$ 的下标对。它精确量化了数组的"乱序程度"。
数组有序 $\iff$ 逆序对为 0。 排序的过程就是消除逆序对的过程。
核心定理：相邻交换的排序，总交换次数 = 初始逆序对数量。 实测四个输入下三者完全相等。
为什么？ 一次相邻交换恰好消除一个逆序对，且不影响其他任何逆序对。
随机数组的逆序对约为 $n^2/4$（实测 1000→241,925、2000→988,076、4000→3,988,639），恰好是最大值的一半。
这解释了插入排序为什么比冒泡快一倍：插入的比较次数与逆序对数量成正比（$n^2/4$），而冒泡的比较次数恒为 $n^2/2$。
比较模型：只能通过比较大小获取信息。下一节的下界就是在这个模型下成立的。

下一节衔接：我们已经知道插入排序在随机数组上要比较 $n^2/4$ 次。那有没有一个更低的、任何比较排序都突破不了的下限？答案是有的 —— 而且它的推导只需要一个朴素的计数论证：$n$ 个元素有 $n!$ 种排列，每次比较最多区分两种情况。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "7.3",
  "title": "比较模型与交换次数",
  "covered": [
    "逆序对的定义与「乱序程度」的量化",
    "核心定理：相邻交换次数 = 初始逆序对数量（含两步论证）",
    "四个输入下的实测验证（三者完全相等）",
    "小例子 [5,2,4,1,3] 的逐轮交换追踪（7 次 = 7 个逆序对）",
    "随机数组逆序对为 n^2/4 的概率论证与实测",
    "解释插入排序比冒泡快一倍的原因",
    "比较模型的定义与它划定的适用范围",
    "增量更新思路（滑动窗口下 O(log n) 维护逆序对数）",
    "三逆序组的降维解法（固定中间元素）"
  ],
  "unresolved": [
    "用归并排序 O(n log n) 数逆序对留到 8.1",
    "树状数组/平衡树超出本书范围",
    "n log n 下界留到 7.4"
  ],
  "canonical_terms": {
    "逆序对": "满足 i<j 且 a[i]>a[j] 的下标对",
    "比较模型": "算法只能通过比较元素大小来获取信息的模型",
    "相邻交换": "只交换相邻两个元素的操作"
  },
  "symbols_units": {
    "I": "逆序对数量"
  },
  "assumptions": [
    "读者已掌握 7.1 的三种排序实现",
    "读者理解基本的概率直觉（等概率事件）"
  ],
  "word_count_actual": 2680,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch07/Sec73/",
    "四个输入的逆序对=移动=交换 三方一致性已实测验证",
    "随机逆序对量级实测与 n^2/4 理论值逐项对照",
    "练习 7.3.1 的逆序对计数已手工验算（8 个）",
    "术语写法与 glossary.md 一致"
  ],
  "next": "7.4 下界：为什么比较排序绕不开 n log n"
}

7.3　比较模型与交换次数