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

超、凢脫俗 2022-08-18 12:27 121阅读 0赞

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

####  ####

##### Time Limit: 20ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

对于数列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

## 示例输出 ##

## 提示 ##

## 来源 ##

xam

## 示例程序 ##

#include<stdio.h>
    #include<stdlib.h>
    long long ans;
    int a[100010],temp[100010];
    void merge(int s1,int e1,int s2,int e2)
    {
        int p1,p2,p;
        p=0;p1=s1;p2=s2;
        while(p1<=e1&&p2<=e2)
            {
            if(a[p1]<=a[p2])
                temp[p++]=a[p1++];
            else
            {
                temp[p++]=a[p2++];
                ans+=e1-p1+1;
            }
        }
        while(p1<=e1)
            temp[p++]=a[p1++];
        while(p2<=e2)
            temp[p++]=a[p2++];
        int i;
        for(i=s1;i<=e2;i++)
        a[i]=temp[i-s1];
    }
    
    void merge_sort(int s,int e)
    {
        int m;
        if(s<e)
        {
            m=(s+e)/2;
            merge_sort(s,m);
            merge_sort(m+1,e);
            merge(s,m,m+1,e);
        }
    }
    
    int main()
    {
            int n,i;
            ans=0;
            scanf("%d",&n);
            for(i=0;i<n;i++)
                scanf("%d",&a[i]);
            merge_sort(0,n-1);
            printf("%lld\n",ans);
    }