Question

1 3 ...(2n-1)2 4 ...2n求其逆序数?

Answer 1

选择1,2,3,┅,2n为正序,则1 3 ...(2n-1)2 4 ...2n,从2 开始有逆序数,个数为（2n-1-3）/2+1 =n-1个,4的有（2n-1-5）/2+1 =n-2个,直到2n-2有1个,2n没有.

总个数即为求等差数列（n-1）+（n-2）+ ┅ +1的和,为n（n-1）/2.