思考题2-4（逆序对） 假设A[1..n]是一个有$n$个不同数的数组，若iA[j]，则对偶(i,j)称为A的一个逆序对(inversion)。
a.列出数组$<2,3,8,6,1>$的5个逆序对。
逆序对有$(1,5),(2,5),(3,4),(3,5),(4,5)$
b.有集合$\{1,2,\dots,n\}$中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？
当数组为 $\{1,2,\dots,n\}$为逆序时，即$\{n,n-1,\dots,1\}$时逆序对最多。对于 $\forall i,j \in [1,n],(i,j)$均为逆序对。此时共有逆序对$(_n^2)=n(n-1)/2$
c.插入排序的运行时间与输入数组中逆序对的数量之间是什么关系?证明你的回答。
假设数组$A$初始时存在逆序对$(k,j)$，那么有$k
d.给出一个确定在n个元素的任何排列中逆序对数量的算法，最坏情况需要$\Theta(nlgn)$的时间。
对于这个问题，可以采用归并排序统计逆序对量，或者采用线段树。下面给出具体思路
1、归并排序
计算数组的逆序对数量，可以采用归并排序二分的思想。对于一个数组来说逆序对的来源可以分为3种情况。
对于一个数组 $A[left,right],mid=(left+right)/2$
(1) 两个都在左半数组，$left \leq i \leq j \leq mid，A[i] > A[j]$
(2) 两个都在右半数组，$mid+1 \leq i \leq j \leq right,A[i] > A[j]$
(3) 左右各一个，$left \leq i \leq mid < j \leq right,A[i] > A[j]$
根据上面的思路，只需要对归并排序的代码稍微改动即可。下面是我的实现：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
84
85
86
87
using namespace std;
const int INF=0x3f3f3f3f;
class InversionCount
{
public:
/*
总的逆序对等于左子数组的内部逆序对+右子数组的内部逆序对+来自左和右形成的逆序对
*/
static int MergeSort(int A[],int l,int r)
{
int cnt=0;
if(l<r)
{
int m=(l+r)/2;
cnt+=MergeSort(A,l,m);//第1种情况
cnt+=MergeSort(A,m+1,r);//第2种情况
cnt+=Merge1(A,l,m,r);//第3种情况
}
return cnt;
}
//书种归并排序采用哨兵的版本
static int Merge1(int A[],int l,int m,int r){
int inv_cnt=0;
int *L=new int[m-l+2];
int *R=new int[r-m+1];
for(int i=l,k=0;i<=m;)
L[k++]=A[i++];
for(int i=m+1,k=0;i<=r;)
R[k++]=A[i++];
int LenA=m-l+1;//左子数组的长度
L[m-l+1]=R[r-m]=INF;//设置哨兵
for(int k=l,i=0,j=0;k<=r;)
{
if(L[i]<=R[j])//i<j且A[i]<=A[j]，没有逆序对
A[k++]=L[i++];
else{//i<j且A[i]>A[j]
if(L[i]!=INF){//这里有可能左侧数组先达到尾部，此时防止INF引起额外累加。
//大于A[j]的数量=LenA-i(小于A[i]的数量，数组从0开始)
inv_cnt+=LenA-i;
}
A[k++]=R[j++];
}
}
// printf("l = %d r = %d cnt = %d\n",l,r,inv_cnt);
return inv_cnt;
}
//不用哨兵处理会更方便点
static int Merge2(int A[],int l,int m,int r){
int *B=new int[r-l+1];
int i=l,j=m+1,k=0;
int inv_cnt=0;
while(i<=m&&j<=r)
{
if(A[i]<=A[j])
B[k++]=A[i++];
else
{
inv_cnt+=m-i+1;
B[k++]=A[j++];
}
}
while(i<=m)
B[k++]=A[i++];
while(j<=r)
B[k++]=A[j++];
k=0;
for(int i=l;i<=r;)
{
A[i++]=B[k++];
}
return inv_cnt;
}
};
int main()
{
int A[]={1,2,3,4,5,6,7,8};
int B[]={8,7,6,5,4,3,2,1};
int C[]={6,6,6,6,6,5};
int D[]={2,3,8,6,1};
cout << InversionCount::MergeSort(A,0,7)<<endl;
cout << InversionCount::MergeSort(B,0,7)<<endl;
cout << InversionCount::MergeSort(C,0,5)<<endl;
cout << InversionCount::MergeSort(D,0,4)<<endl;
}
2、线段树
可以采用线段树来处理，这里不打算具体展开线段树的内容，后面有时间再整理一个关于线段树的专题。下面介绍算法思路。
1、为数组$A[1,n]$建立线段树，区间统计$[left,rigth]的数目，初始化均为0$，如果数据范围较大数据比较分散，可以先进行一次离散化。
2、依次对$A[1,n] \in [min,man]$的每个元素进行以下操作，假设$A[i]=k$,则对线段树查找区间$[k+1,max]$的大小，加入逆序对数量中，然后令$A[k]+1$。
上面的操作相当于遍历数组A，对于每一个元素，查找当前在它前面大于它的元素个数，然后累加起来，得到逆序对。遍历数组时间为$O(n)$，每进行一次查找操作为$O(lgn)$，总的的时间复杂度为$O(nlgn)$。
下面时代码实现，常规的线段树模板。
1 |
|