排列的逆序数

article/2025/9/22 5:27:49

百度百科：

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的实际先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

例如序列： 3, 4, 5, 2, 1
规定升序为标准次序
则逆序对为32, 31, 42, 41, 21
所以逆序数为5，排列为奇排列

求逆序数的方法

最简单的是直接计数法，简单直观，时间复杂度为 $O(n^{^{2}})$ 。冒泡排序也可以用来求逆序数，统计swap的交换次数即可。冒泡排序算法循环中的swap交换次数即是逆序数，每次交换一次，逆序数就减一，当逆序数减为零时，整个序列就有序了，但是时间复杂度也是 $O(n^{^{2}})$ 。那有更快的方法求逆序数吗？答案是肯定的，那就是使用归并排序来求逆序数。

利用归并排序求逆序数

int reverseNumbers(vector<int> &v, int l, int r)
{if (l >= r) return 0;int res = 0;int mid = (l + r) >> 1;res += reverseNumbers(v, l, mid);res += reverseNumbers(v, mid + 1, r);static vector<int> tmp;tmp.clear();int i = l, j = mid + 1;while (i <= mid && j <= r) {if (v[i] <= v[j]) {tmp.push_back(v[i++]);} else {res += mid - i + 1;tmp.push_back(v[j++]);}}while (i <= mid) { tmp.push_back(v[i++]); }while (j <= r)  { tmp.push_back(v[j++]); }for (int i = l, j = 0; i <= r; ++i, ++j) v[i] = tmp[j];return res;
}