NOI2018 冒泡排序规律证明
其实网上对于找到规律之后的部分已经讲的很详细了，在这里只较为严谨的证明一遍这个规律（毕竟网上不少人都说"打表可得"）。
首先，我们考虑，对于排列中的一个数i，它对于逆序对的贡献的下界一定是|i-pi|。（这里认为逆序对是有序数对）
假如pi
我们设在pi 那么，i对逆序对的贡献就是k+(n-pi)-(n-i-k)=i-pi+2k。 这个式子中的k是前面比它大的数和它形成的逆序对；(n-pi)是在i前面的数的个数；(n-i-k)的意思是在i之后比i大的数，因为比i大的数一共有n-i个，在i前面有k个，故在i后面有n-i-k个；(n-pi)-(n-i-k)一起表示在i之后的比i小的数。 而对于pi>i时，设在i之后且小于i的数有k个，用同样的方法可以推出i对逆序对的贡献就是k+(n-pi)-(n-i-k)=pi-i+2k。 综上，一个排列中的任意一个数i对逆序对的贡献就是|i-pi|+2k。因为我们要让总的逆序对数=sigma |i-pi|，那么对于任意一个数，k都应该为零。 k为0意味着什么？ 对于一个数i，若pi 然后我们来证明，条件1和“排列中不存在长度大于2的下降子序列”（下文称此为“条件2”）完全等价。 命题1：不满足条件2的排列一定不满足条件1。 如果一个排列中有长度大于2的下降子序列，那么对于这个下降子序列的中间的任意一个数（中间是指不在这个下降子序列的两端）一定不满足条件1。 想一想，它的前面至少有一个比它大的，后面有一个比它小的，那么，不管是i 命题2：满足条件2的排列一定满足条件1。 考虑排列中的任意一个数，他可能是i>pi，也可能反过来，这里只讨论i 对于i 情况2是不存在的的，因为有一个比它大的数在它前面，而一定至少有一个比它小的数在它后面（i前面的位置不够，不能放下所有比i小的数），违背了条件1，自相矛盾。 对于情况1，他是满足条件1的。 故证毕。