algorithm - 冒泡排序算法中的迭代次数是否等于(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

排列它们的不同可能性，也称为排列。然而，这本身与任何排序算法无关。 Bubblesort 的渐近运行时复杂度为

O(n^2)

正如您已经提到的，Bubblesort 比尝试所有可能性要聪明一点。为了最终正确回答这个问题，不，Bubblesort 不 (n-1)! n 迭代元素。