气球排序的复杂性

Question

我一直在寻找气球排序的复杂性，但我在互联网上没有看到任何有关它的信息。有人能给我气球排序的平均情况、最好情况和最坏情况吗？我们正在对此进行研究，我们确实需要它来完成我们的论文。

Answer 1

对我来说看起来像是 O(n^2) 。你有

for(x=0;x<num;x++)
{
    for(y=0;y<num-x;y++){ 
        if(N[x] > N[x+y]){ 
        temp=N[x];
        N[x] =N[x+y];
        N[x+y]=temp;
    }
}

第一个循环有 n。

对于第二个循环，当 x = 0 时，循环又运行 n 次(这是最坏的情况)。因此你有 n*n = n^2

看起来其他循环都只有 O(n)，所以 O(n^2) 控制着运行时间。