complexity-theory - 冒泡排序最坏情况、最佳情况和平均情况复杂度

Question

以下进行冒泡排序的函数的 (a) 最坏情况、(b) 最佳情况和 (c) 平均情况复杂度是多少

for i=1 to n-1 do
    for j=i to n-1 do
        if x[j]>x[j+1] then
            temp=x[j]
            x[j]=x[j+1]
            x[j+1]=temp
        end {if}
    end {for}
end {for}

你会如何证明复杂性的合理性？

Answer 1

最坏的情况是 O(n ² )。

平均情况也是 O(n ² )。

最坏的情况也是 O(n ² )，即使 if 语句中的代码在这种情况下不会被执行。二次复杂度是因为无论列表的内容如何，​​两个 for 循环都将在所有三种情况下完全执行。

Answer 2

下面的 BubbleSort 算法也是如此，因为 while 也是 O(n)。

public static void BubbleSort( int [ ] num )
    {
        int j;
        boolean flag = true;  
        int temp;  

        while ( flag )
        {

            flag= false;   
            for( j=0;  j < num.length -1;  j++ )
            {
                if ( num[ j ] > num[j+1] )   
                {
                    temp = num[ j ];                //swap elements
                    num[ j ] = num[ j+1 ];
                    num[ j+1 ] = temp;
                    flag = true;              //shows a swap occurred
                }
            }

        }

    }

Answer 3

如果您想要一个冒泡排序算法，它会在最佳、最坏和平均情况下的效率发生巨大变化，试试这个：

int count = n - 1;    // The input size
bool sFlag = true;    // A flag variable allowing the inner outerloop to 
                         break early and fall through

while (sFlag ){

    sFlag = false;    // Set false so that the loop can break if no swaps occur
    for (int j = 0; j < count; j++){
        if (A[j+1] < A[j]){

            int temp;    // Swap the two elements
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;

            sFlag = true;    // A swap has occured, iterate again
        }
    }
    count--;    //Next time, don't bother looking at the last element, it is 
                  in order

}

最坏的情况是 Cworst(n) = 1/2n(n+1)，最好的情况是 Cbest(n) = n-1。这是因为 count 变量根据相对于输入大小已经完成的迭代量减少了内部循环的迭代次数。

这是迄今为止我遇到的最有效的冒泡排序。