51Nod1019 逆序数（归并排序详解）

逆序对

给定一个1-N的排列A1, A2, ... AN，如果Ai和Aj满足i < j且Ai > Aj，我们就称(Ai, Aj)是一个逆序对。  

求A1, A2 ... AN中所有逆序对的数目。

input

第一行包含一个整数N。  

第二行包含N个两两不同整数A1, A2, ... AN。(1 <= Ai <= N)  

对于60%的数据 1 <= N <= 1000  

对于100%的数据 1 <= N <= 100000

output

一个整数代表答案

Sample Input

5
3 2 4 5 1

Sample Output

5

Time limit

10000 ms

Memory limit

262144 kB

本题由于n可能等于100000，如果用普通思想的遍历整个数据，时间复杂度最坏为0（n^2），时间必然超时。所以本题要用归并排序算法。

下面简单介绍一下归并算法的逻辑：

例如一个数组5 ，3， 4， 6 ，9， 1。

其中用到了分治算法，分成两边同时进行，增加算法效率，归并算法必然是分了lgn次。算法的时间复杂度最坏最好平均都是lgn。

具体思路是：先找到一个mid,分成两边同时拆分成有序数组（一个数，必然是有序的，所以就拆成一个数）：先拆成2个数组分别是:5 ，3 ，4 。    6  ，9  ，1。

然后拆成4个数组 5，3。   4。   6，9。    1。

继续拆成6个数组5 3 4 6 9 1

拆完之后就是合并，定义一个空的数组用于盛装：5和3比较，5大，先将3赋给新定义的数组，然后是5。3,5.和4比较，3大，将3赋给数组，然后是4和5比较，4大，将4赋给数组，最后将5赋给数组。同时6 9 1进行相同的操作。最后是3 4 5 和1 6 9比较得到1 3 4 5 6 9.将这个数组复制给原来的数组，就完成了排序。

这样先用递归拆分数组，在合并数列就完成了归并排序。

归并排序的代码：

拆分：

void mergesort(int *a,int first,int last,int *temp)
{
  if(first<last)
  {
    int mid=(first+last)/2;
    mergesort(a,first,mid,temp);//左边有序 
    mergesort(a,mid+1,last,temp);//右边有序 
    MergeArray(a,first,mid,last,temp);//在将二个有序数列合并 
  }
}

合并：

void MergeArray(int *a,int first,int mid,int last,int *temp)
{//将有二个有序数列a[first...mid]和a[mid...last]合并。
  int k=0;
  int i=first,j=mid+1;
  int n=mid,m=last;
  while(i<=n&&j<=m)
  {
    if(a[i]<a[j])
      temp[k++]=a[i++];
    else
      temp[k++]=a[j++];
  }
  while(i<=n)
    temp[k++]=a[i++];
  while(j<=m)
    temp[k++]=a[j++];
  for(i=0;i<k;i++)
    a[first+i]=temp[i];
}

定义新的数组：

bool MergeSort(int *a,int n)
{
  int *temp;
  temp=(int *)malloc(sizeof(int)*n);
  mergesort(a,0,n-1,temp);
  free(temp);
}

实现一个n长度的数组排序：

#include<stdio.h>
#include<stdlib.h>
void MergeArray(int *a,int first,int mid,int last,int *temp)
{//将有二个有序数列a[first...mid]和a[mid...last]合并。
  int k=0;
  int i=first,j=mid+1;
  int n=mid,m=last;
  while(i<=n&&j<=m)
  {
    if(a[i]<a[j])
      temp[k++]=a[i++];
    else
      temp[k++]=a[j++];
  }
  while(i<=n)
    temp[k++]=a[i++];
  while(j<=m)
    temp[k++]=a[j++];
  for(i=0;i<k;i++)
    a[first+i]=temp[i];
}
void mergesort(int *a,int first,int last,int *temp)
{
  if(first<last)
  {
    int mid=(first+last)/2;
    mergesort(a,first,mid,temp);//左边有序 
    mergesort(a,mid+1,last,temp);//右边有序 
    MergeArray(a,first,mid,last,temp);//在将二个有序数列合并 
  }
}
bool MergeSort(int *a,int n)
{
  int *temp;
  temp=(int *)malloc(sizeof(int)*n);
  mergesort(a,0,n-1,temp);
  free(temp);
}
int main()
{
  int i,n;
  scanf("%d",&n);
  int *a;
  a=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  MergeSort(a,n);
  for(i=0;i<n;i++)
    printf("%d ",a[i]);
  free(a);
}

谈回逆序对这道题。

通过对归并算法的合并比较两个数大小的操作，可以记录逆序对。

具体操作为（合并环节里）：

void MergeArray(long long int *a,int first,int mid,int last,int *temp)
{
  int k=0;
  int i=first,j=mid+1;
  int n=mid,m=last;
  while(i<=n&&j<=m)
  {
    if(a[i]<=a[j])
    {     
      temp[k++]=a[i++];
    }   
    else
    {
      l+=n-i+1;
      temp[k++]=a[j++];
    }
                
  }
  while(i<=n)
    temp[k++]=a[i++]; 
  while(j<=m)
    temp[k++]=a[j++];
  for(i=0;i<k;i++)
    a[first+i]=temp[i];
}

AC代码：

#include<stdio.h>
#include<stdlib.h>
long long int l=0;
void MergeArray(long long int *a,int first,int mid,int last,int *temp)
{
  int k=0;
  int i=first,j=mid+1;
  int n=mid,m=last;
  while(i<=n&&j<=m)
  {
    if(a[i]<=a[j])
    {     
      temp[k++]=a[i++];
    }   
    else
    {
      l+=n-i+1;
      temp[k++]=a[j++];
    }
                
  }
  while(i<=n)
    temp[k++]=a[i++]; 
  while(j<=m)
    temp[k++]=a[j++];
  for(i=0;i<k;i++)
    a[first+i]=temp[i];
}
void mergesort(long long int *a,int first,int last,int *temp)
{
  if(first<last)
  {
    int mid=(first+last)/2; 
    mergesort(a,mid+1,last,temp);
    mergesort(a,first,mid,temp);
    MergeArray(a,first,mid,last,temp);
  }
}
bool MergeSort(long long int *a,int n)
{
  int *temp;
  temp=(int *)malloc(sizeof(int)*n);
  mergesort(a,0,n-1,temp);
  free(temp);
}
int main()
{
  int i,n;
  while(scanf("%d",&n)!=EOF){ 
  long long int *a;
  a=(long long int *)malloc(sizeof(long long int)*n);
  for(i=0;i<n;i++)
    scanf("%lld",&a[i]);
  MergeSort(a,n);
  free(a);
  printf("%lld\n",l);
  }
  return 0;
}

注意：本题的数据很大，需要定义一个long long int存储逆序对，定义一个long long int的数组存储需要排序的数。

（一直AC不了，就是因为这个范围错了。。。。。）