我有一个冒泡排序的版本:
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].
}
}
我走的路是正确的还是我错过了什么?
最佳答案
获得答案的最佳方法是运行冒泡排序算法本身,并在 swap() 调用之后包含一个计数器。您的计算函数 (a) 几乎需要与排序本身一样长的时间(取决于 swap() 与 getprob() 的运行时间)和 (b) 忽略了排序时元素顺序发生变化的要点。
顺便说一句,调用 swap() 的确切次数取决于您需要排序的数据——您有 n*(n-1)/2 次比较,其中任何一次都可能导致交换(平均而言,一半的需要交换比较元素的时间)。
关于c++ - 冒泡排序中的交换次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11331314/