并归排序法求逆序数

[转]http://blog.csdn.net/lewutian/article/details/4549656

 

并归排序法求逆序数 收藏
逆序对（inversion pair）是指在序列{a0,a1,a2...an}中，若ai<aj(i>j)，则(ai,aj)上一对逆序对。而逆序数 （inversion number）顾名思义就是序列中逆序对的个数。例如： 1 2 3是顺序，则逆序数是0；1 3 2中(2,3)满足逆序对的条件，所以逆序数只有1； 3 2 1中(1,2)(1,3)(2,3)满足逆序对，所以逆序是3。由定义不能想象，序列n的逆序数范围在[0,n*(n-1)/2]，其中顺序时逆序数为 0，完全逆序时逆序数是n*(n-1)/2。
就我所知，目前求这种逆序对最快的算法是利用归并排序，其时间复杂度为O(nlgn), 空间复杂度为O(n)
闲话少说，看代码

 

#include <stdio.h>
#include <stdlib.h>

/**///////////////////////////////////////////////////////////////////////////
//求逆序数
//最快的算法是归并排序时计算逆序个数，时间复杂度是nlog2n, 空间复杂度是2n
//a为字符数组，len为字符数组的长度
int number = 0; //number表示逆序对的个数
void mergePass(char *, char *, int, int);
void merge(char*, char*, int, int, int);
void copy(char *dest, char *src, int l, int r)
{
    while(l <= r)
	{
        dest[l] = src[l];
        l++;
    }
}
void mergeSort(char *a, int size)
{
    char *b = (char*)malloc(sizeof(char) * size);
    mergePass(a, b, 0, size - 1);
    free(b);
}


void mergePass(char *a, char *b, int l, int r)
{
    int m;
    if(l < r)
	{
        m = (l + r) / 2;
        mergePass(a,b,l,m);
        mergePass(a,b,m+1,r);
        merge(a,b,l,m,r);
        copy(a,b,l,r);
		
    }
}

void merge(char *a, char *b, int l, int m, int r)
{
    int i = l, j = m + 1;
    while( i <= m && j <= r)
	{
        if(a[i] <= a[j])
            b[l++] = a[i++];
        else
		{
            b[l++] = a[j++];
			//a[i] > a[j], 表示出现了逆序对，此时由于
			//a[i..m]是已经有序了，那么a[i+1], a[i+2], ... a[m]都是大于a[j]的，
			//都可以和a[j]组成逆序对，因此number += m - i + 1
            number += m-i+1;
        }
    }
    while(i <= m)
        b[l++] = a[i++];
    while(j <= r)
        b[l++] = a[j++];
}


int main()
{
    char a[10] = {'A','A','C','A','T','G','A','A','G','G'};
    char b[5] = {'A', 'B', 'A', 'A','A'};
    mergeSort(a, 10);
    for(int i = 0; i < 10; i++)
        printf("%c ",a[i]);
    printf("%d ", number);
    system("pause");
    return 0;
}