归并排序与逆序对

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

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

思想很简单:

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值是一点一点移动到前面来消除逆序对，这个过程是没有逆向的。