Processing math: 100%

算法导论思考题2-4

算法导论逆序对排序线段树

字数统计: 211阅读时长: 1 min

 2019/07/30  41  Share

思考题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)$ ，那么有$kkey $，即存在一对逆序对，while循环的一次迭代，将$ A[i] $后移一位，最终前$ j $个元素处于有序，此时消除了前$ j$个元素的逆序对。对于7-9的一次循环，相当于消除一对逆序对。因此，插入排序的运行时间和数组的逆序对之间呈线性关系。

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]$

根据上面的思路，只需要对归并排序的代码稍微改动即可。下面是我的实现：

#include<iostream>
#include<cstdio>
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)$ 。

下面时代码实现，常规的线段树模板。

#include<iostream>
#include<algorithm>
using namespace std;
#define lchild (x<<1) 
#define rchild (x<<1|1)
const int N=100;
int A[N<<2|1];
void update(int x)
{
	A[x]=A[lchild]+A[rchild];
}
//建立线段树
void build(int left,int right,int x)
{
	if(left==right){
		A[x]=0;
		return;
	}
	int mid=(left+right)>>1;
	build(left,mid,lchild);
	build(mid+1,right,rchild);
	update(x);
}
//查询区间[L,R]
int query(int left,int right,int L,int R,int x)
{
	if(L<=left&&right<=R)
		return A[x];
	int ret=0;
	int mid=(left+right)>>1;
	if(L<=mid)
		ret+=query(left,mid,L,R,lchild);
	if(R>mid)
		ret+=query(mid+1,right,L,R,rchild);
	return ret;
}
//修改 A[x]=k的结点+1
void modify(int i,int left,int right,int x)
{
	if(left==right){
		++A[x];
		return;
	}
	int mid=(left+right)>>1;
	if(i<=mid)
		modify(i,left,mid,lchild);
	else
		modify(i,mid+1,right,rchild);
	update(x);
}

int main()
{
	int arr[]={10,9,8,7,6,5,4,3,2,1};
	build(1,10,1);
	int cnt=0;
	cout << "Hello" << endl;
	for(auto i:arr)
	{
		cnt+=query(1,10,i+1,10,1);
		modify(i,1,10,1);
	}
	cout << cnt << " ";
}