Math Reference Notes: 逆序数

逆序数（inversion number）是描述排列中元素相对顺序的一个重要量度。它用来衡量排列中元素的“乱序程度”，即大元素出现在小元素前面的次数。逆序数在很多数学问题中扮演着重要角色，特别是在排列的奇偶性和排序算法的分析中。

1. 逆序数的定义

对于一个排列 $a_1, a_2, \dots, a_n$ ，如果 $i < j$ 且 $a_i > a_j$ ，则称 $a_i, a_j)$ 是一个逆序对。逆序数就是排列中所有逆序对的个数。

逆序对的解释：

逆序对是指在排列中较大的数字出现在较小数字前面的位置。
如果 $a_i$ 和 $a_j$ 是逆序对，那么它们满足 $i < j$ 且 $a_i > a_j$ 。

2. 逆序数的计算方法

计算排列的逆序数就是计算排列中所有逆序对的个数。一般的做法是：

从排列的第一个元素 $a_1$ 开始，遍历排列中的每一个元素 $a_i$ 。
对于每个 $a_i$ ，遍历它后面所有的元素 $a_j$ ，其中 $j > i$ 。
如果 $a_i > a_j$ ，那么 $a_i, a_j)$ 就是一个逆序对，逆序数增加 1。

计算逆序数的步骤：

遍历每个元素 $a_i$ 。
对于每个 $a_i$ ，遍历它后面的所有元素 $a_j$ ，判断是否有 $a_i > a_j$ 。
计数所有满足 $a_i > a_j$ 的情况，得到逆序对的个数。
逆序数就是这些逆序对的总数。

3. 逆序数的示例

示例 1：计算逆序数

假设有排列 $3, 1, 2$ ，我们计算它的逆序数。
- 比较 $3$ 和 $1$ ，因为 $3 > 1$ ，所以 $(3, 1)$ 是一个逆序对。
- 比较 $3$ 和 $2$ ，因为 $3 > 2$ ，所以 $(3, 2)$ 是一个逆序对。
- 比较 $1$ 和 $2$ ，因为 $1 < 2$ ，所以它们不是逆序对。
总的逆序数为 2（逆序对是 $(3, 1)$ 和 $(3, 2) \））。
示例 2：逆序数计算更复杂的排列

考虑排列 $245136987$ 。我们要计算它的逆序数。
1. 第一个元素 2：它后面有 $4, 5, 1, 3, 6, 9, 8, 7$ 。
  - 逆序对：2 和 1，因为 $2 > 1$ 。
  - 逆序数增加 1。
2. 第二个元素 4：它后面有 $5, 1, 3, 6, 9, 8, 7$ 。
  - 逆序对：4 和 1，4 和 3（ $4 > 1$ ， $4 > 3$ ）。
  - 逆序数增加 2。
3. 第三个元素 5：它后面有 $1, 3, 6, 9, 8, 7$ 。
  - 逆序对：5 和 1，5 和 3（ $5 > 1$ ， $5 > 3$ ）。
  - 逆序数增加 2。
4. 第四个元素 1：它后面有 $3, 6, 9, 8, 7$ ，没有逆序对。
  - 逆序数增加 0。
5. 第五个元素 3：它后面有 $6, 9, 8, 7$ ，没有逆序对。
  - 逆序数增加 0。
6. 第六个元素 6：它后面有 $9, 8, 7$ 。
  - 逆序对：6 和 8，6 和 7（ $6 > 8$ ， $6 > 7$ ）。
  - 逆序数增加 0。
7. 第七个元素 9：它后面有 $8, 7$ 。
  - 逆序对：9 和 8，9 和 7（ $9 > 8$ ， $9 > 7$ ）。
  - 逆序数增加 2。
8. 第八个元素 8：它后面有 $7$ 。
  - 逆序对：8 和 7（ $8 > 7$ ）。
  - 逆序数增加 1。
9. 第九个元素 7：没有比它小的元素。
  - 逆序数增加 0。
最终的逆序数是：
$1 + 2 + 2 + 0 + 0 + 0 + 2 + 1 + 0 = 8$
因此，排列 $245136987$ 的逆序数是 8。

4. 逆序数与排列的奇偶性

逆序数与排列的奇偶性密切相关。排列的奇偶性是通过排列中的逆序数来定义的：

偶排列：如果排列的逆序数是偶数，那么该排列就是偶排列。
奇排列：如果排列的逆序数是奇数，那么该排列就是奇排列。

示例：
假设排列 $3, 1, 2$ ，其逆序数为 2（偶数），所以它是偶排列。

5. 逆序数在排序算法中的应用

逆序数在很多排序算法中扮演着重要角色，尤其是在冒泡排序和选择排序等交换排序算法中。它在排序的复杂度分析中也起到关键作用。

冒泡排序与逆序数：

在冒泡排序中，逆序数表示了需要交换的次数。在每一趟排序中，两个相邻的元素会交换位置，如果它们的顺序不正确（即形成逆序对），那么就需要交换。通过计算排列的逆序数，可以知道该排列的排序需要多少交换次数。
选择排序与逆序数：

选择排序通过每一趟从未排序部分选择最小的元素，依次将其交换到已排序部分。在最坏情况下，选择排序的交换次数也与排列中的逆序数相关。