逆序对和置换环

我们先假设没有哪两个数是一样的，这样比较方便。

冒泡排序的时候我们会交换一些相邻的数字，最小交换次数就是逆序对数。这是因为，相邻两个数之外的逆序对数不会改变，只有两个数本身 \((i, j)\) 这一对的一定会发生 \(1\) 的变化。没有排好序的时候我们一定能够找到 \(i > j\) 进行交换，逆序对 \(-1\)。

如果我们可以交换任意两个数字，那么排序的最小次数是什么？是置换环个数。考虑对于某一个置换环，我们交换一条环边，可以让 \(a_x = y, a_y = z\) 变成 \(a_y = y, a_x = z\)，增加了一个连通块。最后要 \(n\) 个连通块，所以 $n - $ 连通块个数 \(=\) 操作次数。

交换任意两个数还有一个性质：考虑逆序对数奇偶性。对于夹在 \(i,j\) 中间的数 \(k\)，考虑 \(k, i, j\) 的四种关系，可以推出，交换 \(i,j\) 之间的位置不会使得 \(ik, jk\) 的逆序对和奇偶性变化；所以所有中间的数不会对奇偶性造成影响。只有 \((i,j)\) 影响了。

因此序列的逆序对个数奇偶性可以看置换环个数，因为任意构造一组交换序列变成 \(1 \sim n\) 都可以，准确来说 $n - $ 连通块个数 \(=\) 逆序对数。