逆序个数问题算法研究秦韬，全昱立，薛梅，李丽萍(陕西师范大学计算机科学学院，陕西西安710119)摘要:n个元素组成的序列，a[1],a[2],…,a[n]。若i〈j且a[i]〉a[j]，则称（a[i],a[j]）是一个逆序对，或“捣乱分子对”。序列中逆序对的个数称为序列的逆序数。首先，按定义暴力方法求解，计算逆序数要通过n（n-1）/2此次比较,时间复杂度是O（n2）。其次，换一种方法优化，利用树状数组计算逆序数,时间复杂度降为O（nlog2（n））。最后，根据分治归并排序算法计算逆序数，时间复杂度降为O（nlog2（n））。排序树状数组优化的主要思路是将元素从大到小依次放置在数状数组中，对于每一个元素i来说，因它前面的数比它大而计算出逆序数t[i]，利用树状数组的结构特征，即可以O（log2（n））的时间复杂度而统计出t[i]，那么，最终总的逆序数为∑t[i]。而最后一种优化是利用分治的方法，通过折中从而降低复杂度。关键词:逆序数;树状数组；分治归并；算法AlgorithmResearchAboutTheNumberOfReverseProblemQINTao,QUANYu-li,XUEMei,LILi-ping(Dept.of2013,SchoolofComputerScience,ShaanxiNormalUniversity,Xi’an710119,China)Abstract:Sequenceconsistingofnelements,a[1],a[2],...,a[n].Ifia[j],called(a[i],a[j])isareversepair,or"troublemakerson."Sequenceinreverseorderofthenumbercalledreversenumbersequence.First,bydefinitionviolentmethodstosolve,countthenumberofreversethroughn(n-1)/2thecomparison,thetimecomplexityisO(n2).Secondly,foramethodofoptimizingtheuseofcomputingtheinversenumberBinaryIndexedTree,thetimecomplexityisreducedtoO(nlog2(n)).Finally,calculatedaccordingtothepartitionnumberreversemergesortalgorithm,thetimecomplexityisreducedtoO(nlog2(n)).SortBinaryIndexedTreeoptimizationmainideaistobeplacedindecreasingorderofthenumberofelementslikearray,foreachelementi,theresultofitspreviousnumberlargerthanitcalculatedthenumberofreverset[i],theuseofcharacteristicsBinaryIndexedTreestructure,thatcanbeO(log2(n))timecomplexityandthestatisticst[i],thenthefinaltotalnumberofreverseΣt[i].Thefinaloptimizationistheuseofdivideandconquerapproach,throughcompromisetoreducecomplexity.Keywords:Inversenumber;BinaryIndexedTree;Divideandconquermerge;Algorithm1引言逆序个数问题的描述：多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176,178,180,170,171这些捣乱分子对为<176,170>,<176,171>,<178,170>,<178,171>,<180,170>,<180,171>,那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)输入:为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。输出：为一个文件(out)，每行为一个数字，表示捣乱分子的对数。逆序个数问题的原型：逆序数n个元素组成的序列，a[1],a[2],„,a[n]。若i〈j且a[i]〉a[j]，则称（a[i],a[j]）是一个逆序对，即问题描述的“捣乱分子对”。序列中逆序对的个数称为序列的逆序数，即问题需要求解的捣乱分子的对数。例如：176178180170171怎样找逆序数？根据题目意思，对于序列中的每个数字，找出其前面数字中比它大的数字个数，则为它的逆序数对数，序列中所有数字对应的逆序数对数之和，即为这个序列的总逆序数对数。即有：17617818017017100033显然，结果应该是：6。那么，根据题目要求，我们便可以设计不同算法进行问题解决，并比较优化得到最佳算法。2算法设计2.1暴力求解算法描述根据题目的描述与定义，用人类的大脑直接去解，对于序列中的每个数字，找出其前面数字中比它大的数字个数，则为它的逆序数对数，序列中所有数字对应的逆序数对数之和，即为这个序列的总逆序数对数。这种暴力求解法，对于序列由10，100或1000个数字组成时的简单逆序数问题还可...
