对 Bubblesort 算法进行正确的运行时分析

Question

嘿，我对Bubblesort进行了运行时分析，我想问你是否有任何错误，因为我在某个时候不确定

这里是算法的摘录：

boolean sorted = false;
        while(!sorted)
        {
            int a = 0;
            int b = 1;
            sorted = true;
            while(a < sortArray.length  && b < sortArray.length)
            {
                if(sortArray[a].getWertigkeit() < sortArray[b].getWertigkeit())
                {
                    Karte tmp1 = sortArray[a];
                    Karte tmp2 = sortArray[b];
                    sortArray[a] = tmp2;
                    sortArray[b] = tmp1;
                    sorted = false;
                }

                a++;
                b++;
            }
        }

所以我得到的问题是在第一个while循环中，我解决了如下：

最佳情况：在最佳情况下，sorted 永远不会被设置回 false（通过 if(..){..}）所以它只通过循环一次；因此，如果我没记错的话，运行时间是 2*2n*1 = 4n => O(n) 对于最佳情况；
最坏 Case:In 最坏情况每次循环开始时，变量 sorted 都会设置为 false，据我所知，因此它需要另一个 "n" 比较，以便运行时应该是：n*2n*1 = 2n^2 => O(n^2)

我真的不确定我对 while(!sorted) 的想法是否正确，或者运行时是否有意义（因为大 o 符号看起来不错，但我不确定精确的运行时）

我真的希望我的问题是相关的，我期待收到你的来信。

谢谢

Answer 1

您对 O(n) 的最佳情况运行时间的分析是正确的。干得漂亮！

对于最坏的情况，你需要更精确一点。你是对的，每次重置标志时，你都必须再次遍历数组以使其比以前排序得更好，所以你知道它将是 O(n) 乘以循环次数运行s。您在分析中还没有做的是讨论在所有内容最终排序之前循环可以运行多少次。

关于冒泡排序，您可以观察到在第一次遍历数组后，最大的元素肯定位于最后一个位置 - 您能解释一下原因吗？第二遍之后，第二大元素保证在倒数第二个位置——再一次，你能解释一下为什么吗？基于这种模式，你能争论为什么外层循环的次数运行s最多为O(n)吗？

对 Bubblesort 算法进行正确的运行时分析

Correct runtime analysis on a Bubblesort-algorithm

java

sorting

algorithm

bubble-sort

time-complexity