主要内容 #
- 逆序对描述
- 逆序对求解
- 示例程序
1. 逆序对描述 #
设A为一个有 n 个数字的有序集(n>1),其中所有数字各不相同。
如果存在正整数 i, j,使得 1 <= i < j <= n,而且 A[i] > A[j],
则< A[i], A[j] > 这个有序对,称为 A 的一个逆序对,也称为逆序数。
例如:数组<2,3,8,6,1>的逆序对为:<2,1> <3,1> <8,1> <8,6> <6,1>共5个逆序对。
一个排列逆序对的突显,它可以由序位(2,4)或对位元素(5,2)表示。
简单来说,就是一个数的前面有几个比它大的数,那么这个数就有几对逆序对。
2. 逆序对求解 #
目前求逆序对数目比较普遍的方法是利用归并排序做到O(n\log n)的时间复杂度。
举个栗子:3 5 2 1 0 4 9
枚举法:枚举待测位置i,从i+1~n遍历,找出比他小的数的个数,枚举法可得的解有(3,2),(3,1),(3,0),(5,2),(5,1),(5,0),(5,4),(2,1),(2,0),(1,0)。
归并排序法:
对于一个数组arr来说,我们试着将它拆分成两半,比如当下arr是[32, 36, 3, 9, 29, 16, 35, 73, 34, 82]。我们拆分成两半之后分别是[32, 36, 3, 9, 29]和[16, 35, 73, 34, 82]。我们令左边半边的子数组是A,右边半边的子数组是B。显然A和B都是原问题的子问题,我们可以假设通过递归可以求解出A和B子问题的结果。
当我们将arr数组拆分成了AB两个部分之后,整个arr的逆序数就变成了三个部分。分别是A数组之间的逆序数、B数组之间的逆序数,以及AB两个数组之间的逆序数,也就是一个元素在A中,一个元素在B中的逆序数对。A数组中的元素交换位置,只会影响A数组之间的逆序数,并不会影响B以及AB之间构成的逆序数。因为A中的元素即使交换位置,也在B数组所有元素之前。
我们一个步骤就可以完成AB的排序以及插入,就是将AB两个有序的数组进行归并。在归并的过程当中,我们既可以知道插入的B数组中的位置,又可以完成数组的排序,也就顺带解决了A和B排序的问题。所以整个步骤其实就是归并排序的延伸。
3. 示例程序 #
void msort(int s, int t){ //如果只有一个数字则返回,无须排序 if(s == t) return; int mid = (s + t) / 2; //分解左序列 msort(s, mid); //分解右序列 msort(mid + 1, t); int i = s, j = mid + 1, k = s; //接下来合并 while(i <= mid && j <= t){ if(a[i] <= a[j]){ r[k] = a[i]; k++; i++; }else{ r[k] = a[j]; k++; j++; //统计产生的逆序对数量,ans是全局变量 ans += mid - i + 1; } } //复制左边子序列剩余 while(i < =mid){ r[k] = a[i]; k++; i++; } //复制右边子序列剩余 while(j <= t){ r[k] = a[j]; k++; j++; } for(int i = s; i <= t; i++){ a[i] = r[i] } }