自动搬运

查看原文

来自洛谷，原作者为

	李若谷 蒟蒻

搬运于2025-08-24 21:28:57，当前版本为作者最后更新于2020-01-30 10:35:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么是逆序对

逆序对的做法已经有很篇题解讲的很好了。但是很少题解有讲为什么相邻交换的次数就是逆序对。这篇题解只是为了证明这个。

首先，显然排好序的序列逆序对数一定是 0。

对于i, 和i+1, 显然如果a[i] <= a[i+1] 那么交换这两个数是多余的。因为不管后面怎么交换，最终a[i]一定在a[i+1]前面，如果交换这两个，就会增加a[i]到a[i+1]的前面的交换次数。

对于i,和j, 设i<j且a[i] > a[j], 那么最终a[j]会交换到a[i]前面, 因为只能两两相邻交换，a[i]和a[j]肯定也会交换，否则a[j]无法到a[i]前面, 因为a[j]不可能跳过a[i]。

交换两个相邻的数逆序对数会 -1。显然若a[i] > a[i+1] 交换是它们会减少1个逆序对，由于a[i]和a[i+1]中间没有数，所以不会影响其他逆序对。导致逆序对数会减少1。

既然，任意两个逆序对都要交换，并且每次交换后逆序对数都会减少1，最终的逆序对数是0，那么肯定要交换的个数就是全部逆序对的个数。