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

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

每次交换都会使数组中 inversions 的数量正好减少 1。

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

索引对 i、j，其中 i < j 恰好是一半混排数组的倒置。有 n * (n-1) / 2 个这样的对，因此我们平均有 n * (n-1) / 4 个反转。