[算法] 求数组中倒置个数

http://algs4.cs.princeton.edu/22mergesort/中有一道题是求数组中倒置个数的，原题如下：

Inversions. Develop and implement alinearithmic algorithm Inversions.java forcomputing the number of inversions in a given array (the number ofexchanges that would be performed by insertion sort for thatarray). This quantity is related tothe Kendall tau distance; 

解决思路： Inversions.java在做MergeSort的过程中顺便求出了数组中倒置个数。假设上图中已经获得左右两个子部分中的倒置个数并进行了MergeSort。现在学习一下做整个数组的Merge时如何顺便计算这一层的倒置个数。

• 当aux[0]和aux[5]进行比较时，A小于E，则可知A比左半部分都小（少比较了4次），倒置+5
• 当aux[0]和aux[6]进行比较时，C小于E，则可知C比左半部分都小（少比较了4次），倒置+5
• 当aux[2]和aux[7]进行比较时，E小于G，则可知E比左半部分中G及其之后的数都小（少比较了2次），倒置=+(4-2+1)=+3

整个数组的倒置数为左边部分内部倒置数+右边部分内部倒置数+13。算法时间复杂度为NlogN。