一，定义
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。
也就说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。二，求解方法 --- 暴力求解
时间复杂度 O(n^2)
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
int i,j;
int* a;
int cnt=0;
scanf("%d",&n);
a = (int*) calloc(n, sizeof(int));
for(i=0; i<n; ++i) {
scanf("%d",&a[i]);
}
for(i=0; i<n; ++i)
for(j=i; j<n; ++j) {
if(a[i] > a[j]) ++cnt;
}
printf("%d\n",cnt);
return 0;
}三，求解方法 ---分治法
// 分治法 o(nlogn) 逆序数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//其中b记录序列排序后的结果
long long Calc(int* a, int* b, int first, int last)//long long是关键
{
if(first >= last) // 一个元素的情况下没有逆序数
return 0;
int i,j,k,mid;
k=i=first;
long long res=0;//逆序数个数
mid=(first+last)/2;
j=mid+1;
res=Calc(a,b,i,mid)+Calc(a,b,j,last); // 递归计算两边的逆序数
while((i<=mid) && (j<=last))// 计算两边相关联的数据的逆序数
{
if(a[i]<=a[j]) //如果前面数小于后面的 （移动前面一个数，记录一下 前面 < 后面 的所有后面数）
{
b[k++]=a[i++];//记录排序后结果
res += j-mid-1; //如果j没有往后走，说明后面没有小的。res =0
printf("res=%d\n",res);
}
else
b[k++]=a[j++]; // 是不是没有考虑a[i]=a[j]的问题
}
while(i<=mid)//后面走完，前面的数还没有走完 (说明后面的数小)
{
b[k++]=a[i++];
res+=j-mid-1; //(计算的是每一个前面的数 对应所有后面的数)
}
while(j<=last) //如果前面数先走完，说明所有前面数小
b[k++]=a[j++];
for(i=first; i<=last;++i)//b排序完，让a也变成有序
a[i]=b[i];
return res;
}
int main()
{
int n;
scanf("%d",&n);
int* a=(int*) calloc(n, sizeof(int));//在内存的动态存储区中分配n个长度为size的连续空间
int* b=(int*) calloc(n, sizeof(int));
int i=0;
for(i=0;i<n;++i) //输入数字序列
scanf("%d",(a+i));
printf("%lld\n",Calc(a,b,0,n-1));
for(i=0;i<n;++i) //输入数字序列
printf("%d ",*(a+i));
return 0;
}
四，求解方法 --- 归并法
#include <iostream>
using namespace std;
int a[100], b[100]; // a 为输入序列，b 为辅助内存块
/* 归并 a[p..q] 和 a[q+1..r]，并返回其逆序数 */
int merge(long p, long q, long r)
{
int inv = 0;
long i, j = 0;
long beginA = p, endA = q, beginB = q+1, endB = r;
while(beginA <= endA && beginB <= endB)
{
if(a[beginA] <= a[beginB])
{
b[j++] = a[beginA++];
}
else
{
b[j++] = a[beginB++];
inv += (q - beginA + 1); //走一个后面的 记录 跟走一个前面的记录 都一样
}
}
while(beginA <= endA)
{
b[j++] = a[beginA++];
inv += (r - q);
}
while(beginB <= endB)
{
b[j++] = a[beginB++];
}
for(i = 0; i < j; i++)
a[p+i] = b[i];
return inv;
}
/* 对 a[first..last] 排序，并返回其逆序数 */
int mergeSort(long first, long last)
{
if (first < last)
{
long mid = (first + last) / 2;
int inv = mergeSort(first, mid);
inv += mergeSort(mid+1, last);
inv += merge(first, mid, last);
return inv;
}
else
return 0;
}
int main()
{
a[0]=2;
a[1]=3;
a[2]=1;
a[3]=4;
int res=mergeSort(0,3);
cout<<"res="<<res<<endl;
}