冒泡排序相关知识总结

轮数表示冒泡排序外层循环的次数，次数表示交换次数。

1. 设排列为 \(w\)，冒泡排序的轮数为 \(\max_{i=1}^{n}(i - w_i)\) . 因为如果 \(i > w_i\) ， 那么这个数每一轮会向目的地前进一位。
2. 设序列为 \(w\)，设 \(f_i\) 表示前 \(i\) 个位置有多少个比 \(w_i\) 大的数，那么逆序对数就是 \(\sum_{i=1}^{n}f_i\) ，每冒泡排序一轮，都会有 \(f_i = \max(f_i-1, 0)\)
3. 冒泡排序次数等于逆序对数。
4. 设排列为 \(w\)，冒泡排序交换次数的下界为 \(\frac{1}{2}\sum_{i=1}^{n}|i - w_i|\) , 一个排列能满足这个下界当且仅当排列中不存在长度>=3的下降子序列 等价于 可以被划分为最多两个不下降子序列.