举报
浪迹-_-mm
逆序数,就是观测a(1, n)a(2, n-1)a(3, n-2) ……, a(n, 1)中逆序下标的个数 首先逆序,就是一组下标数列b1,b2,……bn, 如果存在某个数bj比前面的数bi小,则称含有下标bj的元素是逆序的,且若前面每存在一个比bj大的元素,都要算一次逆序数。(可能表述不太严格,时间久了,见谅) (你也可以理解为前后任取两个元素(a(bi), a(bj)),比较下标,若bi>bj,则称该数对是逆序的,逆序数就是该数列a(b1), a(b2), ……a(bn)中这样逆序数对的个数,所以bj每次小于前面一个元素的下标,都有计算一个a(bj)的逆序数) 下面看a(1, n)a(2, n-1)a(3, n-2) ……, a(n, 1)的逆序数 行的下标为1,2,……,n,都是顺序,即1≤2≤……≤n,不用考虑了 列的下标n, n-1, n-2, ……, 1, 挨个看,n,前面没有元素,不是逆序的 n-1,比n小,是逆序的,且只比n一个元素小,逆序数是1 n-2,比n、n-1小,逆序的,逆序的个数是2,逆序数是2 n-3,比n, n-1, n-2小,逆序数是3 …… 1,比n, n-1, ……, 2小,逆序数是n-1 则整体的逆序数是1+2+……+n-1 = n(n-1)/2 这里是看某个元素前面有几个下标比它大,我第一次给出的计算逆序数方法是从前面大的元素观察,看后面有几个元素下标比它小,结果是一样的。