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

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

输出逆序数。

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

45

思路

首先我们清楚的是逆序对这个概念，很容易理解，其实我们选择用选择排序都能来做这道题，但是时间上肯定是不行的
然后我们想想前面已经说过的一些排序，快排？好像不行，不知道从哪里插入一串代码从而能够计数逆序对的个数。
堆排序？好像也不可以
为了保证时间复杂度比较小，而且也能满足这个需求，我们就采用归并排序：
我们来看看归并排序

void sort(int arr[],int left,int right){
    if(left>=right)
        return;
    else{
        int mid; 
        mid=(left+right)/2;
        sort(arr,left,mid);//对左边排序 
        sort(arr,mid+1,right);//对右边排序
        merge(arr,left,mid,right,temp);
      }
  }
void merge(int arr[],int left,int mid,int right,int temp[]){
    int i=left;
    int j=mid+1;
    int t=0;        
    while(i<=mid&&j<=right){
        if(arr[i]<arr[j])
            temp[t++]=arr[i++];
        else{          
            temp[t++]=arr[j++];     
            sum+=mid-i+1;//逆序对的个数 
        }
       }//看做是两副牌花色向上的牌，不断拿走第一张，直到最后一副牌为空 ,注意要考虑相等的情况（这种小细节尤为重要，如果没考虑相等，那么这个元素就不会被保存） 
    while(i<=mid)
        temp[t++]=arr[i++];//我们要把两副牌其中一幅不是空的所有牌都放到temp中，注意，这两幅牌肯定已经排好序了，可以自己推导为什么 
    while(j<=right)
        temp[t++]=arr[j++];//这里如果用if语句就多此一举了    ，要记住while也算是一种条件语句而且循环 
    
    //然后我们把合并并且排好序了的牌全部放回arr中
    t=0;
    while(left<=right)      
        arr[left++]=temp[t++];             
   }

其实很简单，就是采用分治法的思想，然后再往上合并，这里就不多讲了，可以慢慢看一下代码，仔细思考一下

那么怎么去求逆序对呢？

我们就是要去利用合并的操作，在合并时，我们把两个分支看作两堆牌，而且要知道，这样两堆牌肯定是排好序了的，然后我们把两堆各自第一张牌（从小到大排序），进行比较，如果出现大于关系的话，说明接下来这一堆牌都会比那一张大，所以逆序对就是下面这一堆牌的数量

要注意的就是要考虑等于的情况，等于肯定是不算逆序对，所以在if else那个地方要注意是小于等于

题破：

#include<stdio.h>
#include<iostream>
  using namespace std;
  int a[100010];
  int temp[100010];
  long long sum=0;
  void sort(int arr[],int left,int right);
  void merge(int arr[],int left,int mid,int right,int temp[]);
  int main(){
    int t;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    scanf("%d",&a[i]);      
    sort(a,0,t-1);      
    printf("%lld\n",sum);   
  }
  void sort(int arr[],int left,int right){
    if(left>=right)
        return;
    else{
        int mid; 
        mid=(left+right)/2;
        sort(arr,left,mid);//对左边排序 
        sort(arr,mid+1,right);//对右边排序
        merge(arr,left,mid,right,temp);
      }
  }
   void merge(int arr[],int left,int mid,int right,int temp[]){
    int i=left;
    int j=mid+1;
    int t=0;        
    while(i<=mid&&j<=right){
        if(arr[i]<=arr[j])
            temp[t++]=arr[i++];
        else{          
            temp[t++]=arr[j++];     
            sum+=mid-i+1;//逆序对的个数 
        }
       }//看做是两副牌花色向上的牌，不断拿走第一张，直到最后一副牌为空 ,注意要考虑相等的情况（这种小细节尤为重要，如果没考虑相等，那么这个元素就不会被保存） 
    while(i<=mid)
        temp[t++]=arr[i++];//我们要把两副牌其中一幅不是空的所有牌都放到temp中，注意，这两幅牌肯定已经排好序了，可以自己推导为什么 
    while(j<=right)
        temp[t++]=arr[j++];//这里如果用if语句就多此一举了    ，要记住while也算是一种条件语句而且循环 
    
    //然后我们把合并并且排好序了的牌全部放回arr中
    t=0;
    while(left<=right)      
        arr[left++]=temp[t++];             
   }
/***************************************************
52
User name: lin99
53
Result: Accepted
54
Take time: 44ms
55
Take Memory: 984KB
56
Submit time: 2018-09-15 16:42:48
57
****************************************************/