algorithm - 冒泡排序的最佳案例

Question

我想知道冒泡排序的最佳情况是什么？例如，可能存在这样的情况，其中对于最后 2 次通过可能没有交换。我正在用 C 语言编写程序。假设我有一个包含 5 个元素的数组，并且我将元素指定为 1 2 5 4 3，那么最后 2 次传递不会有任何变化？

score 29 · Accepted Answer

29

最好的情况是一次通过。该列表将已经排序。
没有交换=完成。

于 2009-08-31T17:14:35.160 回答

score 26 · Accepted Answer

最佳情况：最好的情况是列表已经排序。a) 将进行比较，但没有交换，执行时间在 O(n2) b) 但是如果我们跟踪每次通过的交换并终止程序检查是否没有交换。那么该程序将只需要一次通过并且最多。单次通过需要 (n-1) 次比较，我们可以说复杂度为 O(n) 量级。

score 12 · Accepted Answer

请参阅冒泡排序：

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

最坏情况性能 O(n²)

最佳案例性能 O(n)

平均案例性能 O(n²)

最坏情况空间复杂度 O(n) 总计，O(1) 辅助

最佳无

score 10 · Accepted Answer

有多种编写冒泡排序算法的方法，随着时间的推移，算法似乎变得更好，更高效。我学到的第一个冒泡排序算法如下。最佳和最坏情况下的算法是 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]

Wikipedia 使用的算法（如下）似乎是使用标志来判断元素是否已交换的改进，这允许冒泡排序算法的最佳情况是 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

score 2 · Accepted Answer

最好的情况是数据已经排序。另一个好例子是当需要排序的项目数量很少时——我曾经使用过它，当我的典型列表是两个项目时，偶尔会排到四个。

score 1 · Accepted Answer

很难说你的意思是

冒泡排序的最佳情况算法复杂度是多少，在这种情况下，C# 没有区别，对于已经排序的输入，答案是O(n 。)
什么时候，如果有的话，你应该考虑使用冒泡排序。

在后一种情况下，您不需要这样做，因为对于较小的情况，Shell 排序和插入排序都将胜过它。我见过的一些性能最好的排序例程是混合快速排序，它对数组的“小”部分使用 Shell 排序。

score 1 · Accepted Answer

1

冒泡排序不可能不交换两次通过。

没有交换的通过意味着列表已经排序。

于 2009-08-31T17:20:00.500 回答

score 0 · Accepted Answer

冒泡排序很少是进行排序的最佳案例。它异常缓慢且效率低下。许多其他排序算法更快。例如，您可以考虑使用 QuickSort 之类的东西。

我所知道的最快的排序算法是由 Steffan Nilsson 开发的，并在下面的文章中进行了描述。

http://www.ddj.com/architect/184404062;jsessionid=VWL2QD1NWIEIJQE1GHOSKHWATMY32JVN?_requestid=396640

如果你只是想知道如何实现冒泡排序，可以在这里找到一篇不错的文章。

http://en.wikipedia.org/wiki/Bubble_sort

score 0 · Accepted Answer

要么是维基百科，要么我错了，但对我来说最好的情况和最坏的情况都是 O(n2) 这来自《算法简介》一书

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]

因此，无论数组是否已排序，即使跳过第 4 行，也没有一次通过，第 2 行和第 3 行按比例执行 n2 次

编辑：我想我明白了维基百科毕竟是对的，但是必须通过添加让我们说布尔变量 is_exchange 在进入第二个循环之前将其设置为 false 来修改算法，如果在退出循环后再次为 false，那么我们就完成了这种情况下的时间将是 O(n) 因为第二个循环被执行了 n 次

algorithm - 冒泡排序的最佳案例

9 回答 9

Related

Reference