算法导论 — 思考题4-4 逆序对

（逆序对）假设$A[1..n]$A[1..n]是一个有$n$n个不同数的数组。若$i &lt; j$i<j且$A[i] &gt; A[j]$A[i]>A[j]，则对偶$(i, j)$(i,j)称为A的一个逆序对(inversion)。
　　a. 列出数组$&lt;2, 3, 8, 6, 1&gt;$<2,3,8,6,1>的5个逆序对。
　　b. 由集合${1, 2, …, n}$1,2,…,n中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？
　　c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。
　　d. 给出一个确定在$n$n个元素的任何排列中逆序对数量的算法，最坏情况需要$Θ(n{\rm lg}n)$Θ(nlgn)时间。（提示：修改归并排序）
　　解
　　a.
　　5个逆序对：$(8, 6) (6, 1) (8, 1) (3, 1) (2, 1)$(8,6)(6,1)(8,1)(3,1)(2,1)
　　
　　b.
　　逆序对最多的情况出现在元素按降序排列的时候，即${n, n-1, … , 2, 1}$n,n−1,…,2,1。这种情况下，任意两个元素都构成逆序对，一共有$C_n^2=(n(n-1))/2$Cn2​=(n(n−1))/2组逆序对。

c.
　　插入排序的运行时间$T(n)$T(n)与数组中的逆序对数量$R(n)$R(n)成线性关系，即$T(n) = Θ(R(n))$T(n)=Θ(R(n))。下面用数学归纳法证明。
　　初始情况$n = 2$n=2，线性关系显然成立。
　　下面进入归纳过程。假设对于$n-1$n−1个元素的情况，插入排序的运行时间$T(n-1)$T(n−1)与逆序对的数量$R(n-1)$R(n−1)成线性关系$T(n-1) = Θ(R(n-1))$T(n−1)=Θ(R(n−1))。对于$n$n个元素的情况，其逆序对数目$R(n)$R(n)分为两部分：
　　① 前$n-1$n−1个元素的逆序对数目$R(n-1)$R(n−1)；
　　② 前$n-1$n−1个元素与第$n$n个元素构成的逆序对数目$R_p(n)$Rp​(n)。
　　故$R(n) = R(n-1) + R_p(n)$R(n)=R(n−1)+Rp​(n)。
　　$n$n个元素的插入排序可分为两步进行：
　　① 首先将前$n-1$n−1个元素排序，其时间$T(n-1) = Θ(R(n-1))$T(n−1)=Θ(R(n−1))；
　　② 然后将第$n$n个元素插入到已排序好的前$n-1$n−1个元素中。前$n-1$n−1个元素与第$n$n个元素存在$R_p(n)$Rp​(n)个逆序对，这说明前$n-1$n−1个元素中一共存在$R_p(n)$Rp​(n)个元素比第$n$n个元素要大。插入排序在这一阶段要将第$n$n个元素插入到合适的位置，这一步的运行时间$T_p(n) = Θ(R_p(n))$Tp​(n)=Θ(Rp​(n))。
　　故排序$n$n个元素的运行时间$T(n) = T(n-1) + T_p(n) = Θ(R(n-1)) + Θ(R_p(n)) = Θ(R(n-1) + R_p(n)) = Θ(R(n))$T(n)=T(n−1)+Tp​(n)=Θ(R(n−1))+Θ(Rp​(n))=Θ(R(n−1)+Rp​(n))=Θ(R(n))。
　　综上所述，插入排序的运行时间$T(n)$T(n)与数组中的逆序对数量$R(n)$R(n)成线性关系$T(n) = Θ(R(n))$T(n)=Θ(R(n))。

d.
　　采用分治法。对于数组$A[1 .. n]$A[1..n]，将其对半分为两个子数组：$A_L = A[1 .. ⌊n/2⌋]$AL​=A[1..⌊n/2⌋]和$A_R = A[⌊n/2⌋+1 .. n]$AR​=A[⌊n/2⌋+1..n]。$A[1 .. n]$A[1..n]的逆序对数目$R(A)$R(A)分为$3$3部分：
　　① 左半边子数组$A_L$AL​的逆序对数目$R(A_L)$R(AL​)
　　② 右半边子数组$A_R$AR​的逆序对数目$R(A_R)$R(AR​)
　　③ 左半边子数组的元素与右半边子数组的元素构与的逆序对数目$R(A_L, A_R)$R(AL​,AR​)。
　　故$R(A) = R(A_L) + R(A_R) + R(A_L, A_R)$R(A)=R(AL​)+R(AR​)+R(AL​,AR​)。
　　下面考虑③。一种简单的方法是，对$A_L$AL​中的每个元素$A_L[i]$AL​[i]，遍历$A_R$AR​中的每个元素$A_R[j]$AR​[j]，寻找与$A_L[i]$AL​[i]构成逆序对的元素。这种方法的时间为$Θ((n/2)^2) = Θ(n^2)$Θ((n/2)2)=Θ(n2)，时间成本太高。然而，如果$A_L$AL​和$A_R$AR​分别已经排好序，可以把时间缩减到$Θ(n)$Θ(n)。并且，分别排序$A_L$AL​和$A_R$AR​并不影响$A_L$AL​和$A_R$AR​之间的逆序对数目$R(A_L, A_R)$R(AL​,AR​)。这一过程具体如下：
　　
　　上述方法可以和归并排序揉合在一起，先执行${\rm CROSS-INVERSION-COUNT}(A, p, q, r)$CROSS−INVERSION−COUNT(A,p,q,r)，然后执行归并排序的${\rm MERGE}$MERGE过程。在递归的每一层，执行${\rm CROSS-INVERSION-COUNT}(A, p, q, r)$CROSS−INVERSION−COUNT(A,p,q,r)和${\rm MERGE}$MERGE过程各花费$Θ(n)$Θ(n)时间。递归一共有$Θ({\rm lg}n)$Θ(lgn)层，因此该算法的执行时间为$Θ(n{\rm lg}n)$Θ(nlgn)。下面给出完整的伪代码。
　　
　　代码链接：https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter02/Problem_2-4/InversionCount