博客

int cnt=0;							// 逆序对个数
int a[100002], c[100002];
void MergeSort(int l, int r)	// r＝右边界索引＋1
{ 
	int mid, i, j, tmp;
	if (r>l+1)
	{
		mid = (l+r)/2;
		MergeSort(l, mid);
		MergeSort(mid, r);
		tmp = l;
		for (i=l,j=mid; i<mid && j<r; )
		{
			if (a[i]>a[j])
			{
				c[tmp] = a[j];
				tep++,j++;
				cnt += mid-i;			// 使用排序，就可以方便地数跨“分界”的逆序对个数了
			}
			else
				c[tmp++] = a[i++];
		}
		if (j<r) for (; j<r; j++) c[tmp++] = a[j];
		else for (; i<mid; i++) c[tmp++] = a[i];
		for (i=l; i<r; i++) a[i]=c[i];
	}
}

#include<iostream>
using namespace std;
 
/* 归并求逆序对数, arr 存储最终有序结果
 * 在函数外申请一个临时数组作为参数传入
 * 避免递归不断创建临时数组的开销
 */
int Merge(int * arr, int beg, int mid, int end, int * tmp_arr)
{
    memcpy(tmp_arr+beg,arr+beg,sizeof(int)*(end-beg+1));
    int i = beg;
    int j = mid + 1;
    int k = beg;
    int inversion = 0;  // 合并过程中的逆序数
    while(i <= mid && j <= end)
    {
        if(tmp_arr[i] <= tmp_arr[j])
        {
            arr[k++] = tmp_arr[i++];
        }else
        {
            arr[k++] = tmp_arr[j++];
            inversion += (mid - i + 1);
        }
    }
    while(i <= mid)
    {
        arr[k++] = tmp_arr[i++];
    }
    while(j <= end)
    {
        arr[k++] = tmp_arr[j++];
    }
    return inversion;
}
 
int MergeInversion(int * arr, int beg, int end, int * tmp_arr)
{
    int inversions = 0;    // 记录倒序数
    if(beg < end)
    {
        int mid = (beg + end) >> 1;
        inversions += MergeInversion(arr, beg, mid, tmp_arr);
        inversions += MergeInversion(arr, mid+1, end, tmp_arr);
        inversions += Merge(arr, beg, mid, end, tmp_arr);
    }
    return inversions;
}
 
/* 测试序列 ：answer: 10 */
int testPoint[10] = {
    1, 4, 2, 9, 48,
   15, 13, 44, 6, 90
};
 
void main()
{
    int arrcopy[10];      // 临时数组
    memcpy(arrcopy,testPoint,sizeof testPoint);
 
    printf("the num of inversions is: %d\n",
            MergeInversion(testPoint,0,9,arrcopy));
}