3

可能重复：
冒泡排序中的交换次数

问题简述如下：给定一个包含N
个整数 的数组 A，数组中的每个元素都可以增加一个固定数b，概率为p [ i ], 0 <= i < n。我必须找到使用冒泡排序对数组进行排序的预期交换次数。

我尝试了以下方法：

1) 对于i < j的元素 A[ i ] > A[ j ]的概率可以很容易地从给定的概率中计算出来。2) 使用上述方法，我计算出预期的掉期次数为：

double ans = 0.0;
for ( int i = 0; i < N-1; i++ ){
    for ( int j = i+1; j < N; j++ ) {
        ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.

基本上我想到了这个想法，因为预期的交换次数可以通过数组的反转次数来计算。因此，通过利用给定的概率，我正在计算一个数字 A[ i ] 是否会与一个数字 A[ j ] 交换。

我之前发布了一个类似的问题，但它没有所有的限制。

无论我是否走在正确的轨道上，我都没有得到任何好的提示，所以我在这里列出了所有的限制。如果我以不正确的方式思考问题，请给我一些提示。

4

1 回答 1

2

给定元素的预期交换次数只是其左侧大于它的预期元素数量。

您可以通过指标变量的方法和期望值具有线性特性的事实快速计算这一点。

因此，假设您正在考虑 element a_3。那么预期的交换次数就是

E[#a_3 的交换] = E[a_0 > a_3] + E[a_1 > a3] + E[a_2 > a_3]

右侧的每个个体期望都可以使用基本概率轻松计算。

然后，预期的交换总数只是每个元素的预期交换数的总和除以 2（因为您重复计算）。

于 2012-07-05T08:40:55.357 回答