Question

求数列逆序数

Answer 1

1.
逆序数‘也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个
不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。’
2.
从小到大（从左到右），先看第一个数，如果前面比他大的数没有，则我们可以把这个数的逆序数即为0；再看第二个数，如果其左边的数比它大的数有n1个，则这个数的逆序数为n1；再看第三个数，如果其左边的数比它大的数有n2个，则这个数的逆序数为n2；再看第四个数，如果其左边的数比它大的数有n3个，则这个数的逆序数为n3；一直看到这个数列的结尾，最后再把每个数的逆序数相加即可。
3.
1，2，3，4，5。。。。。。此数列从第一个数到第n个数的逆序数分别别为：0，0，0，0，0，。。。。。。故此数列的逆序数为0+0+0+0+0+。。。。。。=0.

Answer 2

解：如果数列各项都不想等，那么倒置顺序以后，设原数列一共有n项，那么新数列的逆序数是c
n
2
–
k
=
n(n
–
1)/2
–
k
。