SDUTACM 数据结构实验之排序五：归并求逆序数

青旅半醒 2022-07-16 23:13 173阅读 0赞

## 题目描述 ##

对于数列a1,a2,a3…中的任意两个数ai,aj (i < j)，如果ai > aj,那么我们就说这两个数构成了一个逆序对；在一个数列中逆序对的总数称之为逆序数，如数列 1 6 3 7 2 4 9中，(6,4)是一个逆序对，同样还有(3,2),(7,4),(6,2)，(6,3)等等，你的任务是对给定的数列求出数列的逆序数。

## 输入 ##

输入数据N(N <= 100000)表示数列中元素的个数，随后输入N个正整数，数字间以空格间隔。

## 输出 ##

输出逆序数。

## 示例输入 ##

10
    10 9 8 7 6 5 4 3 2 1

## 示例输出 ##

## 提示 ##

#include<stdio.h>
    long long int count;
    void merge(int a[],int l,int mid,int r)
    {
        int i,j,k,n1,n2;
    	int left[100010],right[100010];
    	n1=mid-l+1;
    	n2=r-mid;
    	for(i=0;i<n1;i++)
            left[i]=a[l+i];
    	for(i=0;i<n2;i++)
    		right[i]=a[mid+1+i];
    	left[n1]=right[n2]=0x7fffffff;
            i=j=0;
    	for(k=l;k<=r;k++)
    	{
                    if(left[i]<=right[j])
    		{
    			a[k]=left[i];
    			i++;
    		}
    		else
    		{
    			a[k]=right[j];
    			j++;
                            count=count+n1-i;
    		}
    	}
    	return;
    }
    void mergesort(int a[],int l,int r)
    {
    	int mid=(l+r)/2;
    	if(l>=r) return ;
    	mergesort(a,l,mid);
    	mergesort(a,mid+1,r);
    	merge(a,l,mid,r);
    }
    int main()
    {
    	int i,n,a[100010];
    	count=0;
            scanf("%d",&n);
    	for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
            mergesort(a,0,n-1);
    	printf("%lld\n",count);
    	return 0;
    }