原序列1357…(2n-3)(2n-1)(2n)(2n-2)(2n-4)…642中，(2n-1)的逆序有(2n-2),...,4,2共n-1个；(2n-3)的逆序有(2n-4),...,4,2共n-2个；(2n-5)的逆序有(2n-6),...,4,2共n-3个；……5的逆序有4,2共2个；3的逆序有2共1个；(2n)的逆序有(2n-2),...,4,2共n-1个；(2n-2)的逆序有(2n-4),...,4,2共n-2个；……6的逆序有4,2共2个；4的逆序有2共1个；所以，原2n元序列的逆序数是 [(n-1)+(n-2)+…+2+1]*2=n(n-1).
|
