Joyce' Blog
0%

逆序计数

发表于 更新于

分析

  • 穷举（Brute force）: Θ(n2).
  • 分治策略：Θ(nlgn)

  1. 划分：把序列一分为二；

  2. 分别递归求出左右各自部分的逆序数；

  3. 组合: 计数左右部份之间的逆序数, 返回总的逆序数

算法

Merge-and-Count(A,B)

维护一个Current指针指向每个表，初始化指向首元素

维护一个变量Count用于逆序的计数，初始为0

While两个表都不空

令ai与bj是由Current指针指向的元

把这两个表中较小的元素加到输出表中

If bj是较小的元素then

​ 把Count加上在A中右边剩余的元素数

Endif

把较小元素选出的表中的Current指针右移

Endwhile

一旦一个表为空，把另一个表剩余的所有元素加到输出中

返回Count和合并后的表

Sort-and-Count(L)

If这个表中有一个元素，then

没有逆序

Else

把这个表划分成两半，

A包含前个元素

B包含剩下的个元素
(rA,A)=Sort-and-Count(A)

(rB,B)=Sort-and-Count(B)

(r,L)=Merge-and-Count(A,B)

Endif

返回r=rA+rB+r以及排好序的表L

代码

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
#include<bits/stdc++.h>
using namespace std;
int rev_count = 0;
vector<int> merge_count(vector<int>&A, vector<int>&B)
{
	vector<int> R;
	while (!A.empty() && !B.empty())
	{
		int a = A.front();
		int b = B.front();
		if (b < a)
		{
			R.push_back(b);
			rev_count += A.size();
			B.erase(B.begin());
		}
		else
		{
			R.push_back(a);
			A.erase(A.begin());
		}
	}
	R.insert(R.end(), A.begin(), A.end());
	R.insert(R.end(), B.begin(), B.end());
	return R;
}
vector<int> sort_count(vector<int>&L)
{
	int ls = L.size();
	if ( ls!= 1)
	{
		int x = ls / 2;
		vector<int> A, B;
		int i;
		for (i = 0; i < x; ++i)
			A.push_back(L.at(i));
		for(;i<ls;++i)
			B.push_back(L.at(i));
		A = sort_count(A);
		B = sort_count(B);
		L = merge_count(A, B);
	}
	return L;
}
int main()
{
	vector<int> L;
	int n; int t;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> t;
		L.push_back(t);
	}
	sort_count(L);
	cout << rev_count << "\n";
	for (int i = 0; i < n; i++)
		cout << L.at(i) << " ";
	system("pause");
	return 0;
}