冒泡排序最坏的情况下，最好的情况下和平均情况下的复杂性

什么是（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

冒泡排序最坏的情况下，最好的情况下和平均情况下的复杂性

回答

相关问题