求解数组中逆序对的对数

84 阅读 0 评论 56 点赞

我是靠谱客的博主怡然唇膏，这篇文章主要介绍求解数组中逆序对的对数，现在分享给大家，希望可以做个参考。

题目：给定一个数组，比如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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
 * 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;
}