冒泡排序中的交换次数

Question

我有一个冒泡版本:

int i, j;  

for i from n downto 1 
{
    for j from 1 to i-1 
    { 
        if (A[j] > A[j+1])
            swap(A[j], A[j+1]) 
    } 
}

我想使用上面版本的冒泡排序来计算预期的掉期数量.我使用的方法如下所示:

// 0 based index

float ans = 0.0;

for ( int i = 0; i < n-1; i++ )
{
    for ( int j = i+1; j < n; j++ ) {

        ans += getprob( a[i], a[j]); // computes probability that a[i]>a[j].
    }
}

我是正确的方式还是我错过了什么？

Answer 1

获得答案的最佳方法是运行冒泡排序算法本身并在swap()调用后包含一个计数器.您的计算函数将(a)几乎与排序本身一样长(取决于swap()与getprob()的运行时间)和(b)在排序时忽略元素顺序发生变化的点.

顺便说一句,swap()调用的确切数量取决于你需要排序的数据 - 你有n*(n-1)/ 2次比较,其中任何一个都可能导致交换(平均而言,你需要一半的时间)交换比较的元素).