算法导论习题解答 2-4

•2-4 给出一个能在Θ(nlgn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。（修改归并排序）
解：可以修改归并排序，在归并时加入计数器，求得逆序对的数目。在归并排序“分”的过程中，逆序对的数目等于两个分开的数组里分别计算出的逆序对的个数加上数组间的逆序对个数，而在继续细分的过程中，原来数组间的逆序对顺序不会改变，所以只要在合并时加上计数器来计算逆序对的个数即可。比如在合并已经排好的数组A和数组B时，如果A[i]>B[j]，则A[i]后面的所有数都可以和B[j]构成逆序对，有Length[A] – i + 1个。
Merge(A,p,q,r)
1、 n1 <- q-p+1
2、 n2 <- r-q
3、 creat arrays L[1..n1+1] and R[1..n2+1]
4、 for i <- 1 to n1
5、      do L[i] <- A[p+i-1]
6、 for j <- 1 to n2
7、      do R[j] <-A[q+j]
8、 L[n1+1] <- ∞
9、 R[n2+1] <- ∞
10、i <- 1
11、j <- 1
12、for k <- p to r
13、      do if L[i] <= R[j]
14、           then A[k] <- L[i]
15、               i <- i+1
16、           else A[k] <- R[j]
17、               j <- j+1
18、 count <- count+n1-i+1