小九妹:我问你哦！！！

特邀回答的答案

求排列的逆序数，并确定他们的奇偶性
1 3 5...(2n-1) 2 4 6...(2n)
老师说该排列的前n个数1 3 5...(2n-1)之间不构成逆序，后n
个数 2 4 6...(2n)之间也不构成逆序，只有前后n个数之间才
构成逆序，.........后面的我就没怎么听懂。这句话也不是很
理解，望小妹指点一二！
补充 - 13小时前
这句话中"只有前后n个数之间才构成逆序"不理解，还有接下去该
怎么做？

解：先要搞清楚叫作“排列的逆序”？
如：有一个任意的排列3,2,4,1,5,我们要将这个排列调成自然排
列1,2,3,4,5,(由小到大或由大到小依次排列，谓之自然排列），
需要经过多少次相邻元素的调换？或者说，这个排列是由自然排列
经过多少次相邻元素的调换得到的？这“相邻元素调换”的总次数
谓之排列3,2,4,1,5,的“逆序”。不难看出：要把排列3,2,4,1,5
中的1调到首位必须经过3次调换（4,1换位成1,4;然后2,1换位成
1,2;最后3,1换位成1,3,2,4,5)；把2调到自然排列中的第2位需要
经过1次调换，(即3,2换位）；而3,4,5,已经是自然排列，没有逆
序。故3,2,4,1,5的逆序=3+1=4.
取n=3,那么2n-1=2×3-1=6-1=5,即有排列1,3,5,这是由小到大的自
然排列，故“不构成逆序”。即1,3,5,...,2n-1这n个数已经是自然
排列，“不构成逆序”。同理，2,4,6,...,2n这n个数也是自然排列，
也“不构成逆序”。
还取n=3,那么把前3个奇数1,3,5和后3个偶数2,4,6共6个数排在一起
成1,3,5,2,4,6就不是“自然排列”了，就“构成逆序”啦！此排列的
逆序=2+1=3.
那么排列1,3,5,...,2n-1,2,4,6,...,2n的逆序=？
在此排列中2的左边比2大的数有3,5,7,...,2n-1共n-1个，即2的逆序
为n-1;而4的左边比4大的数有5，7，9，...,2n-1共n-2个；......,
依此类推，该排列的逆序=(n-1)+(n-2)+(n-3)+...+[n-(n-1)]
=n(n-1)-[(n-1)+1](n-1)/2=n(n-1)/2.
如：1，3，5，7，2，4，6，8（这里n=4),其逆序=4（4-1）/2=6).
(逆序=3+2+1=6，即2的左边比2大的数有3，5，7共3个；4的左边比4
大的数有5，7共2个，6的左边比6大的数有7共1个；8的左边比8大的数
为0个；故共有3+2+1+0=6）.
我说清楚了吗？