利用 Merge Sort 求逆序对

本文总结一下求逆序对的方法, 主要想记录几点自己的心得. 网上其实也可以找到很多资料, 但是总是感觉他们没有点破一些东西. 话不多说. 开始.

(1) 逆序对的概念:

a[i] < a[j] and i > j, 那么a[i] 和 a[j]就是一个逆序对, 逆序对问题基本上就是给你一组数字, 要这个数列里面的逆序对的数量.

(2) 方法:

(A) 暴力法, 从第一个元素开始, 逐个和后面的元素比较, 直接利用逆序对的概念判断, 然后记录统计结果, 因为对a[i]来讲要判断a[i+1]…a[N-1]个数字, 那么这个方法的时间复杂度就是O(N^2)

(B) 树状数组: 这个是比较tricky的一个数据结构, 树状数组是一种能在O(logN)时间里面找到任意一个range的和的数据结构, 这里不是我的重点, 有兴趣的人可以google之, 这种方法找逆序对的时间复杂度是O(NlogN)

(C) 利用merge sort:

因为merge sort大家都很熟悉, 稍微做点变化实现起来也很简单, 所以比较推荐这个算法.  假设merge_sort(int A[]) 在merge sort 数列A的同时返回A中的逆序对的数量T, 也就是说, 当merge_sort(A) 结束的时候, A已经sorted了, 而且A里面有T个逆序对, T会被返回. 那么我么可以找到这个逆序对数量T的递归结构.

我们知道merge_sort(A) 等价于merge_sort(left part of A) 以及merge_sort(right part of A) 然后加上merge(left, right). 那么A中的逆序对的数量包括三部分, the inverse pair within left part(T1), the inverse pairs within right part(T2), the inverse pair across the left part and right part(T3). 按照我们的假设,  T1, T2会被递归计算, 不用我们再操心, 那么T3怎么计算, T3其实是这样一种逆序对, 他的第一个数a1在left part, 他的第二a2个数在right part, 而且第二个数字比第一个数字小. 排序的好处在于两方面:

第一, 不会增加也不会减少T3类型的逆序对数量(你想, 假设generl的T3类型的数对, a1 在数列的left part, a2在数列的right part, 假设(a1, a2)原先就是逆序对, 那么left part排好序的时候, a1还是在left, part, a2还是在right part, 也就是还是在a1的后面, 这个数对(a1, a2)还是逆序对, 同样道理, 原先不是逆序的正常数对, 就也还是保持正常数对);   第二, 可以在线性时间内算得T3.

首先第一点我罗嗦了很多进行解释, 主要就是我自己在思考的时候我就会有这个担心, 想通了以后我才确信这个算法是正确的, 但是网上很多现成的资料都没点破这一点. 好, 那么现在我们说第二点, 线性时间内计算T3. 这个其实就不难了, 我们知道在merge的时候, 我们需要比较a[i] 和 a[j], a[i] 是左边的第一个元素, a[j]是右边的第一个元素, 如果a[i] < a[j] 那么是正常的数对, 如果a[j] < a[i] 那么a[i] 包括a[i]后面的所有数(到左边数组的最后一个为止) 都和a[j] 都成逆序对, 这个常数时间可以计算(左边数组的长度减去i), 而且这个数量就是和a[j]构成逆序对的所有数量, 没有遗漏也不会额外增加, 所以这就保证了算法的正确性.  那么既然线性时间可以merge搞定, 整个算法的复杂度就是O(NlogN).

Written on August 29, 2013