逆序数介绍以及算法实现
前言 线性代数中对于一段数字序列的排列情况有这样一个定义：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。(摘自 百度百科)
对于逆序数通俗的理解：对于序列中每个位置的的数，其之前比他的值大的个数之和，或者在其之后比他的值小的个数之和，如此称为逆序数。
实现 实现手段：线段树、树状数组、离散化、归并排序、枚举
我们容易根据逆序数的理解写出O(n^2)的模拟算法，是一个普通冒泡排序类似物： int ans = 0; //逆序数个数
int num[maxn];
for (int i = 1; i < n; i++) {
for (int j = n - i; j > 0; j--) {
if (num[j + 1] < num[j]) {
swap(num[j + 1], num[j]);
ans++;
}
}
}
如果当一段数字集中在某个范围中，还可以利用hash的特性，复杂度O(n*num(max))，但这个仍然是个暴力算法: #include
using namespace std;
int a[100005];//存储有多少比它大的数字在它之前
int main()
{
int n, m, i, j, k;
cin >> n;
long long int sum = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", &m);
sum = sum + a[m];// 有多少比它大的数字在他之前，就要加上多少组
for (j = 0; j { a[j]++; } } cout << sum << endl; } 上面那步的思想其实就是每次将数字压入数据集时，查询比当前数字排名来得大得数字数量，这个数字就是当前下标数字得逆序数。但是这个写法不足地方有两点：1，数据分散时空间复杂度高；2，每次都要执行一个O(num)大小的前缀操作。我们这是就可以利用线段树，树状数组的树形结构将前缀操作以及查询操作都均摊到O(logn)级别，从而提高效率。 细节 关于sum的含义是求得1~idx下标得前缀和，在这里根据方法2得思路就是rank <= idx的前缀数量，这里就要利用到一点容斥的思想：我们的目标是考虑当前有多少个比当前数排名大的数，当前全集为i,rank <= idx的数量为sum(idx)，则当前 rank > idx 的数量为i-sum(idx)。其实c维护的就是rank的数量。举例：{7,4,3,8,6} 目前数据集 目前下标得到的逆序数 说明 { } 初始化 逆序数为0，数据集为空 {7} 0 加入7，排名为4，逆序数为0，前面没有排名比他高的数字 {7，4} 1 加入4，排名为2，逆序数为1，前面排名有1个比他高的数字，分别为7 {7，4，3} 2 加入3，排名为1，逆序数为2，前面排名有2个比他高的数字，分别为7，4 {7，4，3，8} 0 加入8，排名为5，逆序数为0，前面排名有0个比他高的数字 {7，4，3，8，6} 2 加入6，排名为3，逆序数为2，前面排名有2个比他高的数字，分别为7，8 观察C数组的变化 #include #include #include #include #define ll long long using namespace std; int n,c[100010]; int lowbit(int x) { return x&(-x); } void add(int k,int num) { while(k<=n) { c[k]+=num; k+=lowbit(k); } } int query(int k) { int sum=0; while(k) { sum+=c[k]; k-=lowbit(k); } return sum; } typedef struct nodee { int x,i; }node; node maze[100010]; bool cmp(node u,node v) { if(u.x==v.x) return u.i>v.i; return u.x } int b[100010]; int main(void) { int i,j,x,y; while(~scanf("%d",&n)) { ll sum = 0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { scanf("%d",&maze[i].x); maze[i].i = i; } sort(maze+1,maze+1+n,cmp); int cnt = 1; for(i=1;i<=n;i++){ if(i!=1&&maze[i].x!=maze[i-1].x) cnt++; b[maze[i].i] = cnt; } for(i=1;i<=n;i++) { add(b[i],1); ll tmp = (i-query(b[i])); sum += tmp; cout << "\n逆序数 = " << tmp << " 排名 = " << b[i] << '\n'; cout << "C数组：\n"; for (int j = 1; j <= n; j++) { cout << c[j] << " "; } } printf("\n\n排列的逆序数为 = %lld\n",sum); } return 0; } 对于逆序数还有归并排序的求法，注意归并排序是稳定的排序算法，写法有细节要注意。 #include #include using namespace std; const int maxn = (int)1e5+5; typedef long long ll; typedef double db; typedef long double ldb; int val[maxn],tmp[maxn]; ll cnt; void Merge (int l, int m, int r) { int i = l; int j = m + 1; int k = l; //归并排序为稳定排序，稳定的关键是mid后面那部分只有在小于前面的时候才往前提，相等不提!!! while (i <= m && j <= r) { if (val[i] > val[j]) { cnt += j-k; // 每当后段的数组元素提前时，记录提前的距离 tmp[k++] = val[j++]; }else { tmp[k++] = val[i++]; } } while (i <= m) { tmp[k++] = val[i++]; } while (j <= r) { tmp[k++] = val[j++]; } for (int i = l; i <= r; i++) { val[i] = tmp[i]; } } void MergeSort(int l, int r) { if (l < r) { int mid = l + ((r - l) >> 1); MergeSort(l, mid); MergeSort(mid + 1, r); Merge(l, mid, r); } return ; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> val[i]; } cnt = 0; MergeSort(1, n); cout << cnt << '\n'; return 0; } 题目链接 NowCoder PKU2299 HDU1394