数据结构之排序，归并求逆序数

阳光穿透心脏的1/2处 2022-06-10 12:24 187阅读 0赞

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

Time Limit: 50MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

对于数列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)等等，你的任务是对给定的数列求出数列的逆序数。

#### Input ####

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

#### Output ####

输出逆序数。

#### Example Input ####

10
    10 9 8 7 6 5 4 3 2 1

#### Example Output ####

#### 链接：http://blog.csdn.net/acdreamers/article/details/16849761博客上看到的，讲了为什么用归并求逆序数， ####

知道了还有一种求逆序数的方法，等有时间了再整理。这里先整理归并排序求逆序数的代码。

#include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100005
    long long int count = 0;//这里long long int 还是很有必要的。！！！
    int a[maxsize],temp[maxsize];
    void merge(int s1,int f1,int s2,int f2)//每次传过来的都是两个有序序列，实现两个有序序列的归并
    {
        int p1 = s1,p= 0;//所以每次都是从0开始。归并之后放到temp里面
        while(p1<=f1&&s2<=f2)
            {
            if(a[p1]<=a[s2])//从小到大进行排序
                temp[p++]=a[p1++];
            else
            {
                temp[p++]=a[s2++];
                count = count+f1-p1+1;//此时a[s2]比前面的数组f1-p1+1个数都大,即p1后面的数。
            }
        }
        while(p1<=f1)//第二个序列已经排完，第一个序列还有剩余。把剩余的元素都排到temp里
            temp[p++]=a[p1++];
        while(s2<=f2)//同上
            temp[p++]=a[s2++];
        int i;
        for(i=s1;i<=f2;i++)//把排序好的temp数组放到a对应的区间。
        a[i]=temp[i-s1];
    }
    
    
    void mergesort(int l,int r)//不断递归，实现归并排序。
    {
        if(l<r)
        {
           int  m=(l+r)/2;
            mergesort(l,m);//左半部分
            mergesort(m+1,r);//右半部分
            merge(l,m,m+1,r);//两部分进行排序，l是左半部分的第一个元素下标，m是左半部分的最后一个元素的下标，m+1是右半部分的字一个元素的下标，r是右半部分的最后一个元素的下标
        }
    }
    
    
    int main()
    {
            int n,i;
            scanf("%d",&n);
            for(i=0;i<n;i++)
                scanf("%d",&a[i]);
            mergesort(0,n-1);//归并排序
            printf("%lld\n",count);
            return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2218/pid/3402.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2218/pid/3402.html