在刷题的过程中碰到了关于无序序列的逆序对统计的问题。

直接暴力会超时，然后搜索了一下算法，发现可以通过归并排序的思想来做到这个统计的过程。看代码的时候，不知道自己的理解力不够还是不熟悉别人的代码，反正是看不懂。无奈之下自己按照自己的理解实现了一下这个算法，顺便复习了一下归并排序算法，所以有了这么一篇文章。算是个笔记吧。

思想很简单:

1. 数组分成左右两部分
2. 两个子数组排序
3. 两个数组合并，这个合并的过程中，如果左边的key值大于右边的key值，就产生了逆序对。因为左边数组是有序的，所以，这个时候产生的逆序对的个数是剩余未处理的部分的长度，将这个数值统计起来就是我们要的结果。
4. 算法复杂度为$nlog_2 n$。

class MergeSort{    public int sort(int[] array, int p, int r)    {        if (p < r)        {            int q = p + (r - p) / 2;            int len1 = sort(array, p, q);      //子数组排序            int len2 = sort(array, q + 1, r);            int count = merge(array, p, q, r);            return len1 + len2 + count;        }        else        {            return 0;        }    }    public int merge(int[] array, int p, int q, int r)    {        int n1 = q - p + 1;        int n2 = r - q;        int[] array1 = new int[n1 + 1];        int[] array2 = new int[n2 + 1];        array1[n1] = int.MaxValue;        array2[n2] = int.MaxValue;        for (int i = 0; i < n1; i++)        {            array1[i] = array[p + i];        }        for (int i = 0; i < n2; i++)        {            array2[i] = array[q + 1 + i];        }        int index1 = 0, index2 = 0;        int count = 0;        for (int i = p; i <= r; i++)        {            if (array1[index1] <= array2[index2])            {                array[i] = array1[index1++];            }            else            {                array[i] = array2[index2++];                count += n1 - index1;//数组有序，所以剩下几个key就有一个key比array2[index2]大也就是有几个逆序对。            }        }        return count;    }}

算法的有效性：

1. 因为合并前，左右数组有序
2. 左边的key值如果大于右边的key值，就代表有逆序对产生。因为数组有序，这样左边剩余的key值肯定更大，所以剩余几个key就有几个逆序对。
3. 算法的整个过程是递归实现的，比较小的key值是一点一点移动到前面来消除逆序对，这个过程是没有逆向的。