求数列的逆序数对数问题

65 阅读 0 评论 43 点赞

我是靠谱客的博主称心皮卡丘，最近开发中收集的这篇文章主要介绍求数列的逆序数对数问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

问题：对于一个数字数组，如(1,3,5,4,2)，假定我们要求的是从小到大数列的逆序数对，则其中(5,4)就是一组逆序数。

解决方法：求一个数列中所有的逆序数对，可以采用递归与分治的思想，借助归并排序来完成。

一个数列的逆序数对，等于【它的两个子序列各自内部的逆序数对】与【两个数列之间的逆序数对】之和。

单独看这个思路，会觉得很很麻烦，因为还得求数列间的逆序数对。但是借助归并排序，我们可以发现，在两个数列合并的时候，从后面的那个数列中取出一个元素的时候，前面的数列中还剩余的元素个数，既是与该取出的元素逆序的元素个数。当从前面数列中取出元素的时候，不进行计算。

例：合并数列(1,3,5)与(2,4)的时候，先取出前面数列中的1，此时不计算；然后取出后面数列中的2，此时前面数列中剩余两个元素3,5，则与2逆序的数有两个；依次类推，最后可得到总逆序数对是2+1=3。

这样就解决了求【两个数列之间的逆序数对】的问题。而【它的两个子序列各自内部的逆序数对】则可以继续分为更小的数列，利用前面介绍的方法来解决。

以上就是称心皮卡丘为你收集整理的求数列的逆序数对数问题的全部内容，希望文章能够帮你解决求数列的逆序数对数问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。