冒泡排序的最佳案例

Question

我想知道冒泡排序的最佳情况是什么？例如,可能存在这样的情况,其中可能没有交换最后2次传球.我正在使用C语言编写程序.假设我有一个包含5个元素的数组,并且我将元素作为1 2 5 4 3,那么在最后2个传递中没有变化？

Answer 1

最佳案例场景是一次通过.该列表已经排序.
没有交换=完成.

Answer 2

最佳案例:最好的情况是如果列表已经排序.a)将进行比较,但没有交换和执行时间在O(n2)b)但是如果我们在每个通道中保持交换的轨道并且如果没有交换则终止程序检查.然后该程序只需要一次传递和最大值.(n-1)在单次通过中需要比较,我们可以说复杂度是O(n)的量级.

Answer 3

请参阅冒泡排序:

冒泡排序具有最坏情况和平均复杂度О(n²),其中n是被排序的项目数.存在许多具有明显更好的O(n log n)的最坏情况或平均复杂度的排序算法.即使是其他О(n²)排序算法,例如插入排序,也往往比冒泡排序具有更好的性能.因此,当n很大时,冒泡排序不是一种实用的排序算法.

• 最差情况表现 O(n²)
• 最佳案例表现 O(n)
• 平均案例表现 O(n²)
• 最坏情况下空间复杂度 O(n)总,O(1)辅助
• 最佳 号码

Answer 4

有多种编写气泡排序算法的方法，随着时间的流逝，该算法似乎变得越来越好，越来越高效。我学到的第一个气泡排序算法如下。最佳和最差情况下的算法为O（n ^ 2）。

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2     for j = A.length downto i + 1
3         if A[j] < A[j - 1]
4             exchange A[j] with A[j - 1]

维基百科使用的算法（如下）似乎是对标记的改进，它可以使用标记来告知元素是否已被交换，这使得气泡排序算法的最佳情况是O（n）而不是O（n ^ 2）

    procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat 
        swapped = false
        for i = 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap( A[i-1], A[i] )
                swapped = true
            end if
        end for
    until not swapped
end procedure

这是一段视频，可以帮助您稍微解释一下C编程语言中的第一种算法：https : //youtu.be/qOpNrqqTsk4