首页 > 代码库 > 算法设计《分治法》归并排序(三)实例分析之逆序对数

算法设计《分治法》归并排序(三)实例分析之逆序对数

问题定义:

  假设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.获取逆序数的同时,也能对整个数组进行排序。

但是,分治法有一个通病,就是虽然时间复杂度降低了,但是需要一个辅助的存储空间。

通过以上分析,实现逆序对数统计的源代码如下所示:

这里的代码是和归并排序算法实现代码基本是一样的,关键之处在与画红线的部分,对于逆序对数进行了统计。

技术分享

技术分享

 技术分享

 

算法设计《分治法》归并排序(三)实例分析之逆序对数