可能的重复：
冒泡排序中的交换次数 https://stackoverflow.com/questions/11331314/number-of-swaps-in-bubble-sort
问题简述如下：
给定一个数组 AN整数，数组中的每个元素都可以增加固定数字b有一定概率 p[i], 0 i < n。我必须找到对数组进行排序的预期交换次数冒泡排序 http://en.wikipedia.org/wiki/Bubble_sort.
我尝试过以下方法：
1) 元素 A[ 的概率i] > A[j] for i < 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].
我已经发帖了类似的问题 https://stackoverflow.com/questions/11331314/number-of-swaps-in-bubble-sort以前但它没有所有的限制。
我没有得到任何好的提示，无论我是否走在正确的轨道上，所以我在这里列出了所有的限制。如果我以错误的方式思考问题，请给我一些提示。
给定元素的预期交换次数只是其左侧大于该元素的预期元素数。
您可以通过指标变量的方法以及预期值具有以下事实来快速计算：线性特性 http://en.wikipedia.org/wiki/Expected_value#Linearity.
所以假设你正在考虑元素a_3。那么预期的交换次数就是
E[a_3 的交换次数] = E[a_0 > a_3] + E[a_1 > a3] + E[a_2 > a_3]
右侧的每个单独期望都可以使用基本概率轻松计算。
那么预期的交换总数就是每个元素的预期交换次数除以二的总和（因为您重复计算）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
