求解全排列的逆序数 1.123...n 2.135...(2n-1)24…(2n) 3.135…(2n-1)(2n)…2
问题描述：
求解全排列的逆序数 1.123...n 2.135...(2n-1)24…(2n) 3.135…(2n-1)(2n)…2
答
1, 2, 3, ..., n 递增,∴逆序数为0
1,3,5,...,(2n-1),2,4,…,(2n)
前面n个递增,逆序为0,2前面比2大的有n-1个,4前面比4大的有n-2个,……
2n前面比2n大的有0个,
∴序列的逆序数=1+2+……+(n-1)=n(n-1)/2
1,3,5,...,(2n-1),(2n), (2n-2),…,4,2
2n-2前面比2n-2大的有2个,2n-4前面比2n-4大的有4个,……,
2前面比2大的有2（n-1）个,
∴序列的逆序数=2[1+2+……+(n-1)]=n(n-1)