求解数组中逆序对的对数

题目：给定一个数组，比如5, 1, 2, 3, 4，求解该数组中逆序对的数目（这个数组包含4个逆序对，为5,1 5,2 5,3 5,4）

分析：可以采用类似归并排序方式，分而治之，将数组平分为两部分，计算前后两部分中存在的逆序对，在合并过程中，计算两部分之间存在的逆序对数目

代码如下：

/*
 * inverse_pair.cpp
 *
 *  Created on: 2012-6-7
 *      Author: ict
 */


#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;

#define MAX 100
#define MAX_VALUE 9999

int merge_inverse(int a[], int start, int end)
{
	int merge_sum;

	if(start >= end)
	{
		return 0;
	}

	/*
	 * 递归调用，分别求取左部和右部的逆序对
	 */
	int left = merge_inverse(a, start, (start + end)/2);
	int right = merge_inverse(a, (start + end)/2 + 1, end);

	int left_len = (start + end) / 2 - start + 1;
	int right_len = end - ((start + end) / 2 + 1) + 1;

	//使用两个辅助数据进行排序
	int *a1 = (int *)malloc(sizeof(int) * left_len);
	int *b1 = (int *)malloc(sizeof(int) * right_len);

	merge_sum = 0;
	int i, j;

	for(i = 0; i < left_len; i++)
		a1[i] = a[i + start];
	for(i = 0; i < right_len; i++)
		b1[i] = a[i + (start + end)/2 + 1];

	//本算法非常精彩的地方，通过在a1和b1的左右边设置一个哨兵，这种方式可以省去很多麻烦
	a1[left_len] = MAX_VALUE;
	b1[right_len] = MAX_VALUE;

	i = 0;
	j = 0;
	for(int k = start; k <= end; k++)
	{
		if(a1[i] <= b1[j])
		{
			a[k] = a1[i];
			i++;
		}
		else
		{
			a[k] = b1[j];
			merge_sum += left_len - i ;
			j++;
		}
	}

	return merge_sum + left + right;
}

int main()
{
	int a[] = {5,1,2,3,4};

	int result = merge_inverse(a, 0, sizeof(a) / sizeof(int) - 1);

	printf("Result is %dn", result);

	return 0;
}

PS：在归并过程中，巧妙使用了哨兵的方式，使代码更简洁，而且更健壮！

最后

以上就是怡然唇膏为你收集整理的求解数组中逆序对的对数的全部内容，希望文章能够帮你解决求解数组中逆序对的对数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。