> 逆序对，就是诸如 i<j 且 a[i]>a[j] 这样的数对 (i,j)
> 证明下为什么这题的结果就是逆序对的个数
> 
> 首先
> 
> 交换相邻的数，最多只能把逆序对数减一，
> 而排序好的序列中逆序对数为0
> 未排序好的序列中逆序对数不为0
> 换句话说，至少需要交换“逆序对数”次才能把序列排序
> 
> 其次，只要序列不是有序的序列，
> 就必然存在 i 使得 a[i]>a[i+1]
> 这样，只要交换 i 和 i+1
> 就能使逆序对数减一，
> 换句话说，存在交换“逆序对数”次就能把序列排序的算法
> 
> 上界=下界，所以答案就是逆序对数...

• Re:稍微证明下为什么是逆序对数 (4) tanjing 2010-09-12 22:56:19
• Re:稍微证明下为什么是逆序对数 (2) aa2985759 2010-11-22 19:50:17