c++ - 冒泡排序中的交换次数

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 次比较，其中任何一次都可能导致交换(平均而言，一半的需要交换比较元素的时间)。