逆序个数问题算法研究秦韬，全昱立，薛梅，李丽萍(陕西师范大学计算机科学学院，陕西西安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],
Ifia[j],called(a[i],a[j])isareversepair,or"troublemakerson
"Sequenceinreverseorderofthenumbercalledreversenumbersequence
First,bydefinitionviolentm
