algorithm - 冒泡排序中执行的平均交换次数

Question

我现在遇到了这个问题： http ://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3155 问题要求计算冒泡排序算法执行的平均交换次数给定的数据是前 n 个（随机列出的 1 到 n 个）自然数的打乱顺序。

所以，我想：

1. 可能的最大交换次数=n(n-1)/2。（当它们按降序排列时。）
2. 可能的最小交换次数=0。（当它们按升序排列时。）

所以，这个分布的模式是(0+n(n-1)/2)/2 =n(n-1)/4。但是，事实证明这是答案。我不明白为什么模式与平均值一致。

Answer 1

由于要排序的输入可以是任何具有相等出现概率的随机数，因此分布是对称的。

它们的均值、中值和众数重合是对称分布的一个特性，这就是均值和众数相同的原因。

Answer 2

每次交换都会将数组中的反转次数减少 1。

排序后的数组没有反转，因此交换次数等于初始数组中的反转次数。因此，我们需要计算混洗数组中的平均反转次数。

一对索引i, j, 和i<j正好是半数洗牌数组的反转。有n * (n-1) / 2这样的对，因此我们n * (n-1) / 4平均有反转。