代码之家 › 专栏 › 技术社区 › Manohar

冒泡排序中执行的平均掉期数

computer-science-theory number-theory computer-science statistics algorithm

2

Manohar · 技术社区 · 8 年前

因此,我认为:

因此,这种分布的模式是(0+n(n-1)/2/2=n(n-1)/4。

2 回复 | 直到 8 年前

1

2

WinningAddicted 8 年前

由于要排序的输入可以是发生概率相等的任意随机数,因此分布是对称的。

2

1

danbanica 8 年前

每次掉期都会减少 inversions

排序后的数组没有反转,因此交换数等于初始数组中的反转数。因此,我们需要计算无序阵列中的平均反转数。

指数对 i , j 具有 一、 < n * (n-1) / 2 这样的配对,因此我们有 n * (n-1) / 4 平均倒置。