冒泡排序优于其他排序算法吗？

Question

冒泡排序优于其他排序算法吗？

algorithmsortingbubble-sort

12

为什么你会选择使用冒泡排序算法而不是其他的排序算法？

- Neel

如果你喜欢等待一个慢速算法完成？ :) - Michael McGowan

10

当“bogosort”太慢时怎么办？ :-) - templatetypedef

2

建议面试官采用众包方式进行排序。如果一百万人每个人都并行地对一个记录进行排序，整个数组将在短时间内完成排序！ - David

2

不适用于对100万个32位整数进行排序。 - Brent Bradburn

我认为这个问题本质上与冒泡排序有什么用？相同。 - Bill the Lizard

相关：为什么冒泡排序不高效？ - Peter Cordes

14个回答

9

有一种情况下，冒泡排序是最佳选择，但这只在古老的硬件上才能真正发生（基本上是像带有两个头的鼓式存储器这样的东西，你只能按顺序读取数据，并且只能处理直接相邻的两个数据项）。

除此之外，在我看来，它完全没有用处。即使是快速启动某些东西的借口也是无意义的，至少在我看来是这样。选择排序或插入排序更易于编写和/或理解。

- Jerry Coffin

请提供一个有趣的例子，说明冒泡排序算法何时最优。即使大多数人（包括我在内）出生时，这种硬件已经过时了。 - Voo

9

如果你需要创建一个展示冒泡排序动画的网页，你可以使用冒泡排序算法。

- Ted Hopp

8

当满足以下所有条件时：

实现速度比执行速度更重要（概率 <1%）
冒泡排序是你从大学课程记住的唯一排序算法（概率为99%）
你手头上没有排序库（概率 <1%）
你无法访问Google（概率 <1%）

这意味着你需要实现冒泡排序的概率不到0.000099％，也就是说，百万分之一都不到。

- Albin Sunnanbo

适用于排序算法的 Drake 方程式，点赞1个 :-) - templatetypedef

1

但是归并排序更容易实现（它几乎没有比使用递归函数和一个微不足道的基本情况更容易的方法），更短，速度也更快，所以最好将“不允许递归”（概率？一些嵌入式系统可能会出现问题）添加到列表中 ;) - Voo

希望只记得冒泡排序的概率是错误的99％！天哪。插入排序和选择排序都更具直观意义，并且很容易从第一原理重构。 - Peter Cordes

5

如果你的数据存储在一个读取很快但后退定位很慢、倒带很快（或者是一个不需要倒带的循环）的磁带上，那么冒泡排序将表现得相当好。

- aaz

1

或者任何其他人工强制实施的紧密局部性约束的情况。 - dmckee --- ex-moderator kitten

3

我怀疑这是一个陷阱问题。在一般情况下，没有人会选择冒泡排序而不是其他排序算法。唯一合理的情况是当你几乎确定输入数据已经（几乎）排好序时。

- tvanfosson

即使这样，您可能最好使用插入排序！ - templatetypedef

3

如果你需要一种排序算法，它保证稳定并且内存占用很小，那么我建议你选择冒泡排序。如果系统内存非常有限（而且性能不是问题），那么这种算法可以工作，并且任何支持代码的人都可以轻松理解它。如果你预先知道值大多数已经排好序，那么这种算法也有帮助。

即使在这种情况下，插入排序可能更好。

如果这是个诡计问题，下次建议使用Bogosort作为替代方案。毕竟，如果他们正在寻找糟糕的排序，那就试试这种方法吧。

- David

在维基百科上跟进Bogosort之后，我发现了这句精彩的话：“H. Gruber对反常糟糕的随机排序算法的分析。” - Chris Walton

1

@Chris Walton：我仍然喜欢上面评论中提到的我的众包想法。我将不得不在某个时候建议在我的工作中，只是为了看看是否有人真正在听或只是在寻找流行词 :) - David

1

有很多原地排序算法，所以这并不是一个好的理由。但是因为建议Bogosort而+1 :D - Voo

@Voo: 同意。在这种情况下，我仍然会选择插入排序。但是，在所有其他考虑因素大致相等的情况下，至少其他（初级）开发人员可以轻松理解并支持冒泡排序实现，因为他们可能熟悉它。 - David

3

冒泡排序很容易实现。虽然“标准”实现的性能较差，但有一种非常简单的优化方法使其成为与许多其他简单算法相比的强劲竞争者。搜索“梳排序”，看看几行代码的神奇之处。快速排序仍然胜过它，但不太容易实现并且需要支持递归实现的语言。

- BertV

3

我可以想到几个使用冒泡排序的原因：

它是一种基本的初级排序算法。对于学习if、for和while语句的初学者来说非常有用。
我可以想象程序员有些空闲时间来尝试各种排序算法。从最基础的冒泡排序开始试验是再合适不过的了（是的，这确实贬低了它的排名，但是如果有人说“排序算法”，谁不会想到“冒泡排序”呢）。
任何算法都能很容易地记住并使用冒泡排序。
当我刚开始学链表时，冒泡排序帮助我理解所有节点如何相互配合。
现在我感觉自己像在为冒泡排序做广告，所以我会安静下来。

- Jason A.

2

这对于学校中的"婴儿级首次排序"练习非常有用，因为容易解释其工作原理并且易于实现。完成编写后，可能运行一次后就可以删除它，不再考虑。

- Paul Tomblin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

你不会选择冒泡排序。

杜克大学的Owen Astrachan曾经写过一篇研究论文，追溯了冒泡排序(Bubble Sort: An Archaeological Algorithmic Analysis)的历史，并引用了计算机科学界传奇人物Don Knuth的话：

简单来说，除了一个响亮的名字和导致一些有趣理论问题之外，冒泡排序似乎没有什么值得推荐的地方。

该论文得出结论：

在本文中，我们调查了冒泡排序的起源以及尽管许多专家警告不要使用它，但它仍然很受欢迎的原因。通过分析其编码和运行时的复杂性，我们确认了这种警告。

冒泡排序比其他O(n²)排序算法慢；它比插入排序慢四倍，比选择排序慢两倍。虽然它在最佳情况下的行为良好（如果包括检查是否没有交换），但插入排序同样具有良好的最佳情况表现：对已排序的数组只需一次遍历。

冒泡排序在几乎所有真实数据集上都非常慢。任何良好的快速排序、堆排序或归并排序的实现都可能比它快得多。对于使用更简单的排序算法解决小型基本案例的递归排序，使用的是插入排序，而不是冒泡排序。

此外，美国总统说你不应该使用它。

相关文章：为什么冒泡排序不高效？提供了更多细节。