氣泡排序算法中的迭代次數是否等於（n-1）！爲n個元素？

Question

我最近讀了一本書，如果我們將n元素排序在一個數組中，所需的迭代次數爲n*(n-1)*...*1 = 7!。但我確定比較的實際數量是（n-1）+（n-2）+ ... + 1 = n（n-1）/ 2。那麼迭代次數和比較次數有什麼不同呢？我猜測沒有，因爲在每次迭代中都會比較數值[if(m[j]>m[j+1])]。所以我錯過了什麼，或者是錯的書？

整個代碼：

for(i=0;i<7;i++) 
{ 
    for(j=0;j<7-i;j++) 
    { 
     if(m[j]>m[j+1]) 
     { 
      t=m[j]; 
      m[j]=m[j+1]; 
      m[j+1]=t; 
     } 
    } 
} 

Answer 1

如果我理解正確的問題，有一些誤解。對於元素的任意數量的n，有

n!=1*2*...*(n-1)*n 

不同的可能性，安排他們，這也是所謂的排列。但是，這與任何排序算法無關。冒泡排序的漸近運行時間複雜度爲

O(n^2) 

因爲你已經提到的那樣，冒泡排序是有點稍微比嘗試所有的可能性更聰明。爲了最終回答問題，否，Bubblesort確實不是採取(n-1)!迭代n元素。