编辑代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
#define MAXSIZE 11
 
typedef int ElemType;
int merge[MAXSIZE];
 
int count=0;
void Merge(int merge[],int a[],int left,int right,int middle){
	int i=left,j=middle+1;
	int k=left;
	while(i<=middle&&j<=right){
		if(a[i]<=a[j]){
			merge[k++]=a[i++];
		}else{
			merge[k++]=a[j++];
			count+=middle-i+1;
		}
	}
	while(i<=middle)merge[k++]=a[i++];
	while(j<=right)merge[k++]=a[j++];
	i=0;
	for(i=left;i<=right;i++)a[i]=merge[i];
}

void Mergesort(int a[],int left,int right){
	if(left<right){
		int middle=(left+right)>>1;
		Mergesort(a,left,middle);
		Mergesort(a,middle+1,right);
		Merge(merge,a,left,right,middle);
    }
}
void display(int a[],int n){
	for(int i=0;i<n;i++){
		printf("%d\t",a[i]);
	}
}
 
int main(){
	int array[MAXSIZE];
	int n;
	for(int i=0;i<MAXSIZE;i++){
		array[i]=0;
	}
	printf("请输入待排关键字个数: ");
	scanf("%d",&n);
	printf("请输入关键字: ");
	for(int i=0;i<n;i++){
		scanf("%d",&array[i]);
	}
	Mergesort(array,0,n-1);
	display(array,n);
	printf("\n");
	printf("逆序对: %d\n",count);
	return 0;
}