逆序数 时间复杂度O(nlgn)

逆序数的定义，摘自百度百科：

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

我是在看算法导论的时候，看到合并排序的课后习题有一个逆序数，要求是在O(nlgn)的时间复杂度之内查找出来。最直接的算法就是双重循环，类似于冒泡排序法，对整个数组进行外循环，内循环是将外循环的下标所指向的元素与内循环指向元素比较，如果外循环的大于内循环的则++，最后得出逆序数。

但是书上给的提示是在合并排序的基础上该，当时想的分解倒是很容易理解，分为两部分，但是他要在第三步(就是合并排序算法的合并函数)统计出当次合并的逆序数目，脑袋就昏了。主要当时只想到分解，分解后合并。并没有认识到，题目潜在的意思是让你利用合并排序那种合并的时候合并出顺序的思想。弱弱...

大致的思路就比较简单，在合并的时候，如果后半部分的数组的元素小于前面的元素，则将计数器加他跳过前半部分的元素，也就是说加上他比前半部分多少个元素大，然后每次合并后的都是一个已排序的数组。

代码如下：

merge.c合并并统计这次合并的逆序数

#include "merge.h"
#define MAX_NUM 2000000000
int merge(int arr[],int p, int q, int r)
{
	int arr_l[q-p+1];
	int arr_r[r-q+1];
	int i, j, k;
	int cnt = 0;
	j = 0;
	k = 0;
	for(i = 0; i < q-p; i++)
	{
		arr_l[i] = arr[i+p];
	}
	for(i = 0; i < r-q; i++)
	{
		arr_r[i] = arr[i+q];
	}
	/* guide */
	arr_l[q-p] = MAX_NUM;
	arr_r[r-q] = MAX_NUM;
	for(i = p; i < r; ++i)
	{
		if(arr_l[j] <= arr_r[k])
		{
			arr[i] = arr_l[j++];
		}
		else
		{
			arr[i] = arr_r[k++];
				if(arr_l[j] != MAX_NUM)
				{
					cnt += q-p-j;
				}	
		}
	}
	return cnt;
}

merge.h

#ifndef _MERGE_H_
#define _MERGE_H_
int merge(int arr[], int p, int q, int r);
#endif

reveser_number.c

#include <stdio.h>
#include "merge.h"
int reverse_num(int arr[], int start, int end)
{
	static int cnt = 0;
	if (start < end-1)
	{	
		reverse_num(arr, start, (end+start)/2);
		reverse_num(arr, (end+start)/2, end);
		cnt += merge(arr, start, (end+start)/2, end);
	}
	return cnt;
}
int main()
{
	int be_sort[] = {34, 61, 12, 135, 5, 13, 1};
	int i = 0;
	int count = reverse_num(be_sort, 0, 7);
	printf("%d/n", count);
	return 0;
}

有一点需要在merge.c计数的时候注意一下，加的时候加的是q-p-j个元素，就是数组的长度减去已插入到数组中的元素个数，就是剩下的左边的数组的元素个数。