逆序对，就是诸如 i<j 且 a[i]>a[j] 这样的数对 (i,j)
证明下为什么这题的结果就是逆序对的个数

首先

交换相邻的数，最多只能把逆序对数减一，
而排序好的序列中逆序对数为0
未排序好的序列中逆序对数不为0
换句话说，至少需要交换“逆序对数”次才能把序列排序

其次，只要序列不是有序的序列，
就必然存在 i 使得 a[i]>a[i+1]
这样，只要交换 i 和 i+1
就能使逆序对数减一，
换句话说，存在交换“逆序对数”次就能把序列排序的算法

上界=下界，所以答案就是逆序对数...

• 分析的不错 (0) qq312873977 2009-04-25 16:12:38
• Re:稍微证明下为什么是逆序对数 (305) tanjing 2010-09-12 22:56:05
  • Re:稍微证明下为什么是逆序对数 (4) tanjing 2010-09-12 22:56:19
  • Re:稍微证明下为什么是逆序对数 (2) aa2985759 2010-11-22 19:50:17
• Re:稍微证明下为什么是逆序对数 (30) kymowind 2011-03-30 09:08:32
• 很好的证明，顶一个！ (2) yc5_yc 2013-01-17 21:26:32