冒泡排序算法中的迭代次数是否等于(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 比尝试所有可能性要聪明一点。为了最终正确回答问题 no，Bubblesort 确实 not 对 n 元素进行 (n-1)! 次迭代。

冒泡排序算法中的迭代次数是否等于(n-1)！对于 n 个元素？

Is the number of iterations in a bubble sorting algorithm equal to (n-1)! for n elements?

algorithm

bubble-sort