问题描述
笨方法:O(n2)
分治O(nlogn)
1)将数组分成两半,分别求出左半边的逆序数和右半边的序数
2)再算有多少逆序是由左半边去一个数和右半边取一个数构成(要求O(n)实现)
解决关键:左半边和右半边都是排好序的.比如,都是从大到小排序的,这样,左右半边只需要从头到尾各扫一遍,就可以找出由量变各取一个数构成的逆序个数
下图是上面2)的图示
首先在排好序后,我们可以得到在本组内,逆序数的个数,然后左右各扫一遍,如上图,如果i<j,那么i后面的书也小于j,肯定不能构成逆序数,j++,当j=5时,i>j,i往后走i++,一直到3,此时不构成,j++,i=3,j=2,构成逆序数,所以得出上述2)中的情况
总结
由归并排序改进得到,加上计算逆序的步骤
MergeSortAndCount:归并排序并计算逆序数
