冒泡排序最壞的情況下，最好的情況下和平均情況下的複雜性

什麼是（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}

的複雜性

你會如何證明覆雜性？

來源

2013-03-06 Hammer

到目前爲止您提出了什麼？ – 2013-03-06 14:50:36

非常多的聲音，你想我們爲你的作業制定一個答案 – 2013-03-06 14:50:38

氣泡排序複雜性討論是非常普遍的網絡，我沒有看到任何人都會有問題，除非它是作業。嘗試谷歌搜索「泡沫排序的複雜性」？ – 2013-03-06 14:52:29

最糟糕的情況是O（n ）。

平均情況也是O（n ）。

最壞的情況下，也爲O（n ），即使if語句將不會在這種情況下，執行中的代碼。二次複雜性是由於這兩個for循環將在所有三種情況下完全執行，而與列表的內容無關。

來源

2013-03-06 14:53:40 Deepu

對於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 
       } 
      } 

     } 

    }

來源

2013-10-16 20:28:54

如果你想有一個冒泡排序算法顯着最佳的變化，最差，平均情況下效率，試試這個：

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變量會根據已經完成的迭代量相對於輸入大小而使內部循環迭代次數減少。

這是我迄今爲止遇到的最有效的氣泡排序。

來源

2016-04-21 06:59:50 Gnolley

冒泡排序最壞的情況下，最好的情況下和平均情況下的複雜性

回答

相關問題