我现在遇到了这个问题: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3155 该问题要求计算当给定数据是前 n 个(1 到 n 随机列出)自然数的打乱顺序时,冒泡排序算法执行的平均交换次数。
所以,我认为:
- 最大可能交换次数=n(n-1)/2。 (当它们按降序排列时。)
- 最小交换次数=0。 (当它们按升序排列时。)
因此,该分布的众数为 (0+n(n-1)/2)/2 =n(n-1)/4。 但是,这就是答案。 我不明白为什么众数与均值一致。
最佳答案
由于要排序的输入可以是任意出现概率相同的随机数,因此分布是对称的。
对称分布的一个特性是它们的均值、中位数和众数一致,这就是均值和众数相同的原因。
关于algorithm - 冒泡排序中执行的平均交换次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45322531/