本文共 1091 字，大约阅读时间需要 3 分钟。

m-p1+1表示 此时p1到中点m位置有多少个数（这些数都可以以a[p2]构成逆序对）

#include
   
    using namespace std;int a[11];int tmp[11];int ans;void merge(int a[],int s,int m, int e, int tmp[])//归并 把每一小部分归为有序 	{		int pt = 0;		int p1 = s,p2 = m+1;		while(p1 <= m && p2 <= e){			if(a[p1] < a[p2]){				tmp[pt++] = a[p1++];			}			else{				tmp[pt++] = a[p2++];				ans += (m-p1+1);//对每个右半的逐个进行考虑 			}		}		while(p1 <= m)//把剩余可能部分的加入归并结果 			tmp[pt++] = a[p1++];		while(p2 <= e)			tmp[pt++] = a[p2++];		for(int i = 0; i < e-s+1; ++i){//把此部分归并（排序）结果重新赋值到a中 			a[s+i] = tmp[i];		}		}void mergeSort(int a[],int s, int e,int tmp[])	{		if(s < e){			int m = s + (e-s)/2;//记录中点 			mergeSort(a,s,m,tmp);			mergeSort(a,m+1,e,tmp);			merge(a,s,m,e,tmp);		}	}int main()	{		ans = 0;		int n;		scanf("%d",&n);		for(int i = 0; i < n; ++i){			scanf("%d",&a[i]);		}		mergeSort(a,0,n-1,tmp);		printf("逆序数为: %d\n",ans);		for(int i = 0; i < n; ++i){			printf("%3d",a[i]);		}		return 0;		}
   

转载地址：http://iqimi.baihongyu.com/