12 January 2013

计算一个序列中的逆序对数目。
仍然采用分治法,利用类似合并排序的方法。
主要难点在于实现合并这一步,思路如下,
给定两个有序序列A和B,要计算A和B之间的逆序对数目,先比较A[1]和B[1],
若大于,则逆序数增加len(A),下一步比较A[1]和B[2]。
若小于,则比较A[2]和B[1]。 直到列表结束。



blog comments powered by Disqus