c - 气球排序的复杂性

我一直在寻找气球排序的复杂性，但在互联网上什么也没看到。有人可以给我气球排序的平均情况，最佳情况和最坏情况吗？我们正在对此进行研究，我们真的需要它来完成论文。

最佳答案

在我看来像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）控制运行时间。