Python三种算法统计任意数列的逆序数

问题描述：计算给定列表的逆序数，也就是每个元素后面比它小的元素数量之和。

（1）对于这个问题，直接使用两层循环即可实现，代码也很简洁。

但是，从算法设计与优化的角度来讲，我们从来不以代码行数多少来判断其优劣。上面的代码虽然简洁，但时间复杂度是平方级的O(n^2)，毫无技巧可言，实在算不上是个好的算法。

（2）参考归并排序算法中使用的分治法，这个问题的求解算法时间复杂度可以达到O(nlogn)。改进算法的核心思路为：1）把列表L平均分为前半部分A和后半部分B；2）统计前半部分A的逆序数和后半部分B的逆序数，以及满足a>b的(a,b)个数，其中a属于A且b属于B，统计逆序数的同时把A和B分别排序并合并为一个列表；3）对前后两部分重复上面的操作。这样以来，在合并A和B时由于已经排序，只需要从前向后扫描A和B，把小的元素移出并添加到结果列表中，如果B最前面的元素小则把逆序数增加A中元素的数量（此时A中所有元素都大于B的第一个元素）。

考虑到Python列表在删除前面元素时会导致后面元素向前移动而引入额外开销，下面的代码并没有真正移出元素，而是通过下标向后移动来模拟移出元素，避免了额外的时间开销。

（3）下面代码把逆序数和插入排序算法结合起来，从后向前扫描元素，每个元素向后移动至合适位置使得原位置后面的元素降序排列，插入位置后面元素数量也就是该元素的逆序数。逆序数越大，下面的算法优势越明显。原始数据恰好降序排列时效率高于前面的两种算法，但原始数据为升序排列时效率非常低，平均效率略高于前面的count()函数但远低于前面的sort_count()函数。

（4）编写代码，测试三种方法的效率

数据完全升序排列的情况：

运行结果：

测试数据完全降序排列的情况：

运行结果：

测试随机数据的情况：

运行结果：