首页 > 算法 数据结构 > 逆序对 | 逆序数

逆序对 | 逆序数

2012年7月16日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)【《算法导论》2-4】

现给出一个数列,求该数列中的逆序对数(逆序数)。本节给出三种方法:方法一是最直接的暴力方法;方法二是基于归并分治的思想;方法三是基于线段树的。

解法一

暴力方法最直接,也最容易想到,两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:

	int sum = 0;
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			if(arr[i] > arr[j])
			{
				++sum;
			}
		}
	}
	return sum;

解法二

这种方法最初见于《算法导论》,这里先附上《算法导论》2-4关于逆序对的几点讨论:

1)   如果数组的元素取自集合[1,2,…,n],那么,怎样的数组含有最多的逆序对?它包含多少个逆序对?

析:很容易想到,当一个数列为逆序时,即[n,n-1,n-2,…,1],逆序数是最多的,是多少?当n=1,inversion=0;n=2,inversion在原来基础上增加1;n=3,inversion增加2…n=n时,inversion增加n-1,所以总的inversion为等差求和n(n-1)/2;也可以这样理解,数列[n,n-1,n-2,…,1]中任取两个数皆为逆序对,故逆序数为Cn2,即n(n-1)/2。

2)  插入排序的运行时间与输入数组中逆序对的数量之间有怎样的关系?

析:我们知道插入排序的程序如下

for(int i = 1; i < n; ++i)
{
	int key = arr[i];
	for(int j = i; j > 0 && arr[j-1] > key; --j)
	{
		arr[j] = arr[j-1];
	}
	arr[j] = key;
}

可以看出,每次内层循环都尝试将当前元素放在“合适”的位置上,所以对于内层循环的每一次迭代,都是在消除当前元素相对之前元素所对应的一系列逆序对,故总的循环便是消除数列所有的逆序对;

3)  给出一个算法,它能用O(nlgn)的最坏运行时间,确定n个元素的任何排列中逆序对的数目。(提示:修改合并排序)

《算法导论》在这里直接提示修改合并排序,所以自然就是用到分治归并的思想,那么逆序对是出现在什么时候?出现多少呢?

我们知道归并排序是通过分治,然后归并两个有序的序列成一个有序序列。现假设两段有序序列分别是[beg,mid]和[mid+1,end],在归并过程中(i,j分别为两段序列的下标),如果a[i]<a[j],则不会产生逆序对;但当a[i]>a[j]时,就出现逆序对了,出现了多少?既然[beg,mid]是有序的,那么[i-mid]序列就都能与a[j]构成逆序对,故:mid-i+1

复杂度O(nlgn),代码如下:

#include<iostream>
using namespace std;

/* 归并求逆序对数, arr 存储最终有序结果
 * 在函数外申请一个临时数组作为参数传入
 * 避免递归不断创建临时数组的开销
 */
int Merge(int * arr, int beg, int mid, int end, int * tmp_arr)
{
	memcpy(tmp_arr+beg,arr+beg,sizeof(int)*(end-beg+1));
	int i = beg;
	int j = mid + 1;
	int k = beg;
	int inversion = 0;  // 合并过程中的逆序数
	while(i <= mid && j <= end)
	{
		if(tmp_arr[i] <= tmp_arr[j])
		{
			arr[k++] = tmp_arr[i++];
		}else
		{
			arr[k++] = tmp_arr[j++];
			inversion += (mid - i + 1);
		}
	}
	while(i <= mid)
	{
		arr[k++] = tmp_arr[i++];
	}
	while(j <= end)
	{
		arr[k++] = tmp_arr[j++];
	}
	return inversion;
}

int MergeInversion(int * arr, int beg, int end, int * tmp_arr)
{
	int inversions = 0;    // 记录倒序数
	if(beg < end)
	{
		int mid = (beg + end) >> 1;
		inversions += MergeInversion(arr, beg, mid, tmp_arr);
		inversions += MergeInversion(arr, mid+1, end, tmp_arr);
		inversions += Merge(arr, beg, mid, end, tmp_arr);
	}
	return inversions;
}

/* 测试序列 :answer: 10 */
int testPoint[10] = {
	1, 4, 2, 9, 48,
   15, 13, 44, 6, 90
};

void main()
{
	int arrcopy[10];      // 临时数组
	memcpy(arrcopy,testPoint,sizeof testPoint);

	printf("the num of inversions is: %d\n",
			MergeInversion(testPoint,0,9,arrcopy));
}

解法三

一般来讲,在解决数列的区间问题上,线段树有很高的出镜率。逆序数便是一个“区间和”的问题:对于数列中的每个元素,它对应的逆序数便是之前序列中大于该元素的元素个数和。

有了这样的分析,便可以用线段树来解决了:对于数列中每一个元素x,它必将对应这线段树中的一条长logn的路径,该路径中的每条线段都包含x,故每遍历到一个元素则将包含该元素的路径中的每条线段次数都加1,而查询该元素所对应的逆序数便是查询线段树中[x,up]的区间和,其中up为该序列的上界。

举个例子:序列:5,4,3,2,1的逆序数,设up为10

i=0,arr[i]=5,查询区间[5,10]的元素个数,此时线段树空,故inversion=0;将5插入包含它的线段路径。

i=1,arr[i]=4,查询区间[4,10]的元素个数,为1,故inversion+=1;将4插入包含它的线段路径。

i=2,arr[i]=3,查询区间[3,10]的元素个数,为2,故inversion+=0;将3插入包含它的线段路径。

以此类推。。。代码如下:

#include<iostream>
using namespace std;

/* 线段树求逆序数 */
#define BORDER 100  // 设测试数列最大不超过100

struct Node         // 线段树
{
	int left;
	int right;
	int counter;
}segTree[4*BORDER];

/* 构建线段树 根节点开始构建区间[lef,rig]的线段树*/
void construct(int index, int lef, int rig)
{
	segTree[index].left = lef;
	segTree[index].right = rig;
	if(lef == rig)   // 叶节点
	{
		segTree[index].counter = 0;
		return;
	}
	int mid = (lef+rig) >> 1;
	construct((index<<1)+1, lef, mid);
	construct((index<<1)+2, mid+1, rig);
	segTree[index].counter = 0;
}

/* 包含x的区间的值都+1 即对包含x的logn个节点的路径进行更新*/
void insert(int index, int x)
{
	++segTree[index].counter;
	if(segTree[index].left == segTree[index].right)
	{
		return;
	}
	int mid = (segTree[index].left + segTree[index].right) >> 1;
	if(x <= mid)
	{
		insert((index<<1)+1, x);
	}else
	{
		insert((index<<1)+2, x);
	}
}

/* 查询点x的逆序数,即查询[x,BORDER]的区间和 */
int query(int index, int left, int right)
{
	if(segTree[index].left == left && segTree[index].right == right)
	{
		return segTree[index].counter;
	}
	int mid = (segTree[index].left+segTree[index].right) >> 1;
	if(right <= mid)
	{
		return query((index<<1)+1,left,right);
	}else if(left > mid)
	{
		return query((index<<1)+2,left,right);
	}
	return query((index<<1)+1,left,mid) + query((index<<1)+2,mid+1,right);
}

/* 测试序列 :answer: 10 */
int testPoint[10] = {
	1, 4, 2, 9, 48,
   15, 13, 44, 6, 90
};

void main()
{
	construct(0,0,100);           // 构建[0,100]线段树
	int reverseSum = 0;           // 记录逆序对数
	for(int i = 0; i < 10; ++i)   // 查询当前逆序数
	{
		reverseSum += query(0,testPoint[i],BORDER);
		printf("num of reverse order is: %d\n", reverseSum);
		insert(0,testPoint[i]);
	}
}

由于线段树的插入和查询操作皆可以在lgn的时间内完成,故遍历一个数列求逆序数的时间复杂度为O(nlgn),空间复杂度为O(nlgn)。

本文相关代码可以到这里下载。

(全文完)

参考资料:《算法导论》2-4

  • 嘲笑自己

    2 3 8 6 1

  • Anderson

    hi 我又来了
    我在看用merge解决逆数对
    int Merge(int * arr, int beg, int mid, int end, int * tmp_arr)
    {
    memcpy(tmp_arr+beg,arr+beg,sizeof(int)*(end-beg+1));
    int i = beg;
    int j = mid + 1;
    int k = beg;
    int inversion = 0; // 合并过程中的逆序数
    while(i <= mid && j <= end)
    {
    if(tmp_arr[i] <= tmp_arr[j])
    {
    arr[k++] = tmp_arr[i++];
    }else
    {
    arr[k++] = tmp_arr[j++];
    inversion += (mid - i + 1);
    }
    }
    你的这段代码有问题, "如果a[i]<a[j],则不会产生逆序对" 这是错的啊, 应该是a[i] 和 所有a[mid] ~ a[j]的产生逆数对吧.
    而且最后 while(i <= mid)
    {
    arr[k++] = tmp_arr[i++];
    }
    while(j <= end)
    {
    arr[k++] = tmp_arr[j++];
    }
    如果是把左边的数字加merge到末尾,说明这个数字比又边的任何一个数字都大, count应该是 to - mid
    我写了个测试了结果应该是对的. 咱们可以讨论下.
    private static void merge(int[] arr, int from, int mid, int to) {
    // TODO Auto-generated method stub
    int start1, start2;
    int[] tmp = new int[arr.length];
    for( int t = from; t <= mid; t++ ) {
    tmp[t] = arr[t];
    }
    start1 = from;
    start2 = mid + 1;
    while( from <= mid && start2 <= to ) {
    if( tmp[from] < arr[start2] ) {
    arr[start1++] = tmp[from++];
    count += start2 - mid -1;
    }
    else {
    arr[start1++] = arr[start2++];
    }
    }
    for( int t = from; t <= mid; t++ ) { //左边加到末尾,比右边的都大
    arr[start1++] = tmp[t];
    count += to - mid;
    }
    }

    • Yx.Ac

      @Anderson 抱歉这么久才回复!
      这个算法的思想就是基于归并,归并的过程说到底是从两个元素两个元素开始进行的,本文的代码是在归并的每一步计算“该步”所能“看见”的逆序数,然后每一步的进行累加,而又因为分治的原因,所以前一步的归并并不影响后面归并的逆序数,您可以举例分步来看一下;下面说一下您提出的问题:
      1.“你的这段代码有问题, "如果a[i]<a[j],则不会产生逆序对" 这是错的啊, 应该是a[i] 和 所有a[mid] ~ a[j]的产生逆数对吧”。其实,a[i]<a[j]不产生逆序对,指的是对于a[j]来讲,目前为止(左边部分的指针跑到i的时候)还没有产生逆序对;您说的“a[i] 和 所有a[mid] ~ a[j]的产生逆数”是错误的,因为a[i]<a[j]但不一定就大于a[mid]~a[j]之间,我们的思路可能不同,我考虑的是合并的每一步比较时,当前所产生的逆序对。
      2. “如果是把左边的数字加merge到末尾,说明这个数字比又边的任何一个数字都大, count应该是 to - mid”您说的这一点,代码在合并的每一步其实都已经计算过了,您可以用测试用例跑一下。
      如果有反例能说明我代码的错误,还望告知,谢谢!咱们可以进一步讨论,嘿嘿!