首先是看啦一下这个人的开头归并还是有点用的（虽然被喷的很惨）。 博客链接 首先说明一下什么是逆序数，下面是百度的定义：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2431中，21，43，41，31是逆序，逆序数是4。
①如何求逆序数
方法如下：
考察每一位，判断从这一位往后有多少小于该位的，结果累加，得到最后结果。
例如，2,4,3,1 先判断2，之后有1是小于2的，结果+1，再判断4，之后3,1都小于4，结果+2，判断3时，结果再+1，最后得到结果4.
至于为什么，我也不知道，反正我感觉挺好理解的。
②如何用算法实现
当然，对于上述简单的过程，我们可以用两个for循环直接暴力，但是，这种方法一般都太low了，复杂度太高。
高效的方法有 ： 归并排序、线段树、树状数组。
个人建议使用线段树求解，因为线段树在很多地方都有应用。
对于归并排序和树状数组，我就不解释了，因为归并排序一搞就忘记了而且用处不大 记录一下归并排序求逆序数字；；；；；；；；；
#include <iostream> using namespace std; #define MAX 500000 #define SENTINEL 2000000000 int l[MAX/2+2],r[MAX/2+2]; long long int merge(int a[], int n, int left, int mid, int right) { long long int cnt=0; int n1 =mid - left; int n2= right - mid; for( int i=0; i<n1; i++)l[i]=a[left+i]; for( int i=0; i<n2; i++)r[i]=a[mid+i]; l[n1]=r[n2]=SENTINEL; int i=0,j=0; for(int k=left; k<right; k++) { if(l[i]<=r[j]) { a[k]=l[i++]; } else { a[k]=r[j++]; cnt+=n1-i;//这里一定有n1>=i;因为i下标指的左边的数组。 //这里else就是右边的数组里的要进来啦，所以判断一下是否左边的数还有几个比它大的， } } return cnt; } long long int mergesort(int a[],int n, int left, int right){ long long int v1, v2, v3; if(left+1<right){ int mid=(left+right)/2; v1=mergesort(a, n, left, mid); v2=mergesort(a, n, mid, right); v3=merge(a,n,left, mid, right); return v3+v1+v2; } return 0; } int main() { int a[MAX],n,i; cin >> n; for(i=0;i<n;i++) { cin >> a[i]; } long long int ans = mergesort(a, n, 0, n); for(i=0;i<n;i++){ if(i)cout << " "; cout << a[i]; } cout << endl; cout<< ans << endl; return 0; }