思路：
分治法 归并排序的过程中，有一步是从左右两个数组中，，每次都取出小的那个元素放到tmp[]数组中
右边的数组其实就是原数组中位于右侧的元素。当不取左侧的元素而取右侧的元素时，说明左侧剩下的元素均比右侧的第一个元素大，即均能构成一个逆序对。假设现在左侧剩余n个元素，则逆序对数+n。
另外，如果当所有右侧的元素都取完，但是左侧仍然有元素剩余时，左侧剩余的元素已经在之前的运算中加到了逆序对中，不需要再添加一次
下面给出 归并排序 和 求逆序对数 两份代码：
code1：
归并排序
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;int a[20];void query(int a[], int first, int mid, int last, int tmp[]){int i = first, j = mid+1;int k = 0;while(i <= mid && j <= last){if(a[i] < a[j]) tmp[k++] = a[i++];else tmp[k++] = a[j++];}while(i <= mid){tmp[k++] = a[i++];}while(j <= last){tmp[k++] = a[j++];}for(int id = 0; id < k; id++){a[first + id] = tmp[id];}}void merge_sort(int* a, int L, int R, int* tmp){if(L < R){int M = L + (R-L)/2;merge_sort(a,L,M,tmp);merge_sort(a,M+1,R,tmp);query(a,L,M,R,tmp);}}int main(){scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d",&a[i]);}int tmp[20];merge_sort(a,0,n-1,tmp);for(int i = 0; i < n; i++){printf("%d ",a[i]);}printf("\n");return 0;}code2：
求逆序对数：
cnt 表示逆序对数的个数
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;int a[20];int cnt;void query(int a[], int first, int mid, int last, int tmp[]){int i = first, j = mid+1;int k = 0;while(i <= mid && j <= last){if(a[i] <= a[j]) tmp[k++] = a[i++];else{tmp[k++] = a[j++];cnt += mid-i+1;}}while(i <= mid){tmp[k++] = a[i++];}while(j <= last){tmp[k++] = a[j++];}for(int id = 0; id < k; id++){a[first + id] = tmp[id];}}void merge_sort(int* a, int L, int R, int* tmp){if(L < R){int M = L + (R-L)/2;merge_sort(a,L,M,tmp);merge_sort(a,M+1,R,tmp);query(a,L,M,R,tmp);}}int main(){scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d",&a[i]);}int tmp[20];cnt = 0;merge_sort(a,0,n-1,tmp);for(int i = 0; i < n; i++){printf("%d ",a[i]);}printf("cnt = %d\n",cnt);printf("\n");return 0;}LRJ给的代码不好理解….
就微笑着同清风合力染绿大地，这样才算善待生命，不负年华。
