我想知道冒泡排序的最佳情况是什么？可能存在这样一种情况，例如在最后两次交换中没有交换。我用C语言编写程序。 假设我有一个由5个元素组成的数组，我将元素设置为1 2 5 4 3，那么最后两次排序就不会改变顺序。
冒泡排序的最佳情况是什么？
13
- Yash
2
1最好的情况是列表已经排序，但我不认为这是你所问的。你能更具体一些吗？ - Dinah
我也不明白这与C#有什么关系。 - Marc Bollinger
9个回答
34
最理想的情况是一次排序即可完成。这意味着列表本身已经有序。
不需要交换任何元素，排序完成。
- jgallant
4
@Jon 如果不指定算法，你怎么能说出最优情况的复杂度呢？我看到了很多冒泡排序的实现。 - user567879
2无论冒泡排序的实现方式如何，至少需要一次完整的遍历来确保列表已排序。最好的情况是列表已经排序，只需要一次遍历即可验证。http://en.wikipedia.org/wiki/Bubble_sort - jgallant
@Jon 如果使用像这样的冒泡排序（第一个算法）http://www.algorithmist.com/index.php/Bubble_sort。最好情况下的复杂度是O(n^2)吗？ - user567879
2@user567879，n^2将是您的最坏情况。想想当冒泡排序运行时会发生什么。如果您的列表已经排序，它将为每个项目运行一次。最佳情况是n（集合中的项目数），因为冒泡排序将需要检查每个项目一次。 - jgallant
28
最佳情况：如果列表已经排序，则为最佳情况。 a）由于它是按原样比较，因此不会进行交换，并且执行时间为O（n2） b）但是，如果我们在每次传递中跟踪交换并终止程序检查是否没有交换。那么程序只需要一次通过，在该单个通过中需要最大（n-1）比较，我们可以说复杂度是O（n）的顺序。
- user239103
12
请参阅冒泡排序：
冒泡排序的最坏时间复杂度和平均时间复杂度都是О(n²)，其中 n 是待排序的项目数。存在许多排序算法，其最坏或平均时间复杂度为O(n log n)。即使是其他的О(n²)排序算法，例如插入排序，也往往比冒泡排序具有更好的性能表现。因此，在 n 较大时，冒泡排序不是一种实用的排序算法。
- 最坏时间复杂度 O(n²)
- 最佳时间复杂度 O(n)
- 平均时间复杂度 O(n²)
- 空间复杂度 O(n)总共，O(1)辅助
- 最优性 否
- Andrew Hare
12
有多种方法可以编写冒泡排序算法，随着时间的推移，该算法似乎变得越来越好，并且更加高效。我学过的第一个冒泡排序算法如下所示。以下算法的最佳和最坏情况是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
- tempmail
1
如果在某个程序中，早期的冒泡排序需要完成所有迭代。这个 swapped = false 可以帮助我们的程序随时停止，从而减少许多步骤。很好的答案。 - Tahir Hussain Mir
2
最好的情况是数据已经排序。另一个好的情况是需要排序的项目数量很少 - 我曾经在我的典型列表中使用它，该列表仅包含两个项目，偶尔会增加到四个。
- Mark Ransom
1
冒泡排序在两次遍历中不进行交换是不可能的。
没有交换的遍历意味着列表已经排序好了。
- Bryan Menard
0
冒泡排序很少是进行排序的最佳选择。它非常缓慢和低效。许多其他排序算法更快。例如，您可以考虑使用类似于QuickSort的东西。
我所知道的最快的排序算法是由Steffan Nilsson开发的，并在以下文章中描述。
http://www.ddj.com/architect/184404062;jsessionid=VWL2QD1NWIEIJQE1GHOSKHWATMY32JVN?_requestid=396640
如果你只是想知道如何实现冒泡排序，你可以在这里找到一篇好的文章。
- Anthony Gatlin
1
1请注意，最快的排序算法通常是特定于应用程序的，尽管几乎所有应用程序都不会在优化超出良好编写的通用（库）算法方面获得明显的好处。 - Sam Harwell
0
可能是我理解错了，但对我来说，最好情况和最坏情况都是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次。
- baz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接