归并排序求逆序数

poj 2299

一个乱序序列的 逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数

归并排序的思想：先递归把序列拆分，然后合并

mergetsort(int start,int last)
{
   if(start<last)
   {
         mid=(start+last)/2;
         mergetsort(start,mid）;
         mergetsort(mid+1,last);
         mergetSort(start,last);  // 合并函数

   }
}

合并函数：

void mergesort(int first,int mid,int last)
{
   /* printf("first:%d,mid:%d,last:%d
",first,mid,last);

    for(int i=0;i<=mid;i++)
        printf("%d ",a[i]);
    printf("
");
    for(int i=mid+1;i<last;i++)
        printf("%d ",a[i]);
    printf("
");
    printf("-------------
");*/


    int i=first,j=mid+1;
    int k=0;
    while(i<=mid&&j<=last)
    {
        if(a[i]<a[j])
        {
            temp[k++]=a[i];
            i++;
        }
        else{
           temp[k++]=a[j];
           t=t+mid-i+1;
           j++;
        }
    }
    while(i<=mid)
    {
        temp[k++]=a[i];
        i++;
    }
    while(j<=last)
    {
        temp[k++]=a[j];
        j++;
    }
    for(int c=0;c<k;c++)
    {
        a[first+c]=temp[c];
    }

}

需要注意的是t=t+mid-i+1，t即是所求的逆序数。

比如序列91054，在第二次合并190时，0比1小，那么0肯定也会比1后面的9要小，所以0要移动两次，即9和1的逆序数都要加1，那么mid-i+1求的是从比0大的这个数开始到mid一共有多少个数。

所有代码：

#include <iostream>
#include <cstdio>

using namespace std;

int a[500005];
int temp[500005];
__int64 t=0;



void mergesort(int first,int mid,int last)
{
   /* printf("first:%d,mid:%d,last:%d
",first,mid,last);

    for(int i=0;i<=mid;i++)
        printf("%d ",a[i]);
    printf("
");
    for(int i=mid+1;i<last;i++)
        printf("%d ",a[i]);
    printf("
");
    printf("-------------
");*/


    int i=first,j=mid+1;
    int k=0;
    while(i<=mid&&j<=last)
    {
        if(a[i]<a[j])
        {
            temp[k++]=a[i];
            i++;
        }
        else{
           temp[k++]=a[j];
           t=t+mid-i+1;
           j++;
        }
    }
    while(i<=mid)
    {
        temp[k++]=a[i];
        i++;
    }
    while(j<=last)
    {
        temp[k++]=a[j];
        j++;
    }
    for(int c=0;c<k;c++)
    {
        a[first+c]=temp[c];
    }

}


void mergeSort(int first,int last)
{
    if(first<last)
    {
        int mid=(first+last)/2;
        mergeSort(first,mid);
        mergeSort(mid+1,last);
        mergesort(first,mid,last);
    }

}

int main()
{
    int n;
    //freopen("a.txt","rw",stdin);
    do{
        t=0;
        scanf("%d",&n);
        if(n==0) break;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        mergeSort(0,n-1);
        printf("%I64d
",t);
    }while(true);
    return 0;
}

除了归并排序以外，树状数组也可以用来求解。

下次学习。