算法导论习题---求n个元素任何排列中逆序对的数量

162 阅读 0 评论 107 点赞

我是靠谱客的博主忧郁棒棒糖，这篇文章主要介绍算法导论习题---求n个元素任何排列中逆序对的数量，现在分享给大家，希望可以做个参考。

问题描述：

设A[1…n]是一个包含n个不同数的数组。如果在i < j的情况下，有A[i] > A[j]，则（i,j）就称为A中的一个逆序对（inversion），（逆序对的元素是下标，而不是数组里的值）。给出一个算法，它能用Θ(nlgn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。

问题求解：

方法一：
循环从数组中取出一个元素k，然后从k之后的元素中找到比k小的元素个数，最后统计所有的个数即为排列中逆序对的数目。从数组中取元素的次数为n，每次取出一个元素后，需要遍历（n-i）次（i为当前元素的位置），其时间复杂度为
这里写图片描述
算法实现：

int CountInversions(const vector<int>& a)
{
    int cnt =

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