首页 > 代码库 > 算法设计《分治法》归并排序(三)实例分析之逆序对数
算法设计《分治法》归并排序(三)实例分析之逆序对数
问题定义:
假设A[1...n]是一个有n个不同数的数组。若i<j且A[i]>A[j]则称(A[i], A[j])为数组A的一个逆序对。
例如数组<2, 3, 8, 6, 1>有(2, 1),(3, 1),(8, 6),(8, 1)和(6,1)5个逆序对。
对于这个问题,直观上进行求解的话,使用暴力求解的方式的话,对于每个数num,都遍历数组中num后的所有数的话,则时间复杂度为O(n^2)。
实现代码如下:
另一种方式,便是使用分治法,首先将整个数组分成两部分,然后,分别求解两个子组数种的逆序数,当两个子数组都只有一个数时,可以直接得到两个数是逆序还是非逆序。
例如:一个数组中的元素信息为:<3, 2, 8, 1>,则递归处理的方式如下所示:
0.首先初始化cnt = 0;
1.首先将数组分成两部分<3, 2> <8, 1>
2.对于<3, 2>继续进行分解为<3> <2>
3.当分解到两个子数组都只有一个元素的时候:两个子数组均是已排序的,则<3> <2>,则可以直接判断3>2,因此cnt ++。并且将两个子数组合并为一个有序的数组<2, 3>
4.同时对于1中子数组<8, 1>分解为<8> <1>,则可直接判断8>1,因此cnt ++。并且将两个子数组合并为一个有序的数组<1, 8>
5.当回溯到两个子数组分别为:A:<2, 3> B:<1, 8>,此时进行逆序数的计算,只需要对于两个有序子数组合并的时候,对于合并代码进行修改即可:由于index=0, A[index]>B[0],因此,此时说明A数组中2以后的元素均大于B[0],则,此时cnt += (n1-index),n1代表左边数组A的长度。
使用分治法求逆序数有以下好处:
1.时间复杂度为O(nlg(n))
2.获取逆序数的同时,也能对整个数组进行排序。
但是,分治法有一个通病,就是虽然时间复杂度降低了,但是需要一个辅助的存储空间。
通过以上分析,实现逆序对数统计的源代码如下所示:
这里的代码是和归并排序算法实现代码基本是一样的,关键之处在与画红线的部分,对于逆序对数进行了统计。
算法设计《分治法》归并排序(三)实例分析之逆序对数