泡泡擅长什么[[副本]

1. 对于链表很容易实现,因为您总是在从左到右重复遍历时交换相邻节点。
2. 气泡排序是一种稳定排序。

• 冒泡排序非常容易正确地编写(如果你做的事情又快又脏,那么仅仅使用冒泡排序可能更容易)。

这很简单,只要在学校里玩一玩,就不会以一团乱麻收场: “如果你左边的邻居比你高,请换位。”

编程更容易。即使是经验丰富的程序员也会犯快速排序、堆排序和合并排序错误。它也不会在堆栈空间中消耗额外的log(n)到O(n)。尽管可以非递归地实现堆排序。

基本上算法是这样的

O(n^2)最坏情况性能

基本上这是慢。。。。

• 气泡排序:类似的,但不总是与提前退出编程,以允许这一点。一般来说,这个似乎是比较受欢迎的一个讨论和抛出在采访

O(n*lg(n))

一般来说,在你对输入一无所知的情况下,最快的排序算法用于一般排序(这实际上已经被证明是在不了解任何输入的情况下进行排序的下限):

• 快速排序:它通常是高速算法中速度较快的一种,但是在选择轴时出错会使它退化为O(n^2),然后比说气泡/插入/选择更糟糕,因为它还消耗堆栈空间。它更多地利用了缓存局部性,因此通常比其他一些替代方案的性能更好。它需要LG(n)到O(n)的空间来进行调用,这取决于它旋转的好坏。
• 合并排序:O(n*log(n))性能,但需要O(n)个额外的空间。通常没有快速排序快。一般需要lg(n)额外的空间以及通话。。。
  堆排序:不需要额外的空间,可以非递归地实现,但是在数组中会有反弹,所以它在缓存中不如其他的好。如果递归实现,则需要lg(n)额外的调用空间。

O(n)排序
如果你对你的输入有所了解,你通常可以比O(n*lg(n))排序得更好。基本上查基数排序、桶排序、计数排序等。。有许多计划。一般来说,如果可以使用其中一个进行排序,您应该。。。。

**其他种类:** 还有很多其他种类的。像贝壳之类的东西。。。以上这些比较常见。

还有一件事需要注意,那就是排序是否稳定。基本上,如果你有A,C,D,C,G,C,每个C会按顺序出现,或者最后一个C会出现在另一个C之前。如果要对多个字段进行排序,这一点很重要。如果你先按名字再按姓氏排序(亚历克斯·罗德里格斯,简·罗德里格斯,贝蒂·罗德里格斯)……你会得到第一个排序(亚历克斯·R,贝蒂·R,简·R)。第二种如果它是稳定的,你会得到亚历克斯R,贝蒂R,简R。如果它不稳定,你可以得到任何订单。一般来说,气泡和插入都很容易实现稳定。堆排序和快速排序通常不稳定。合并排序很容易实现,因为它是稳定的。这也会影响选择。。。。

另外,如果你不知道O(n)表示法,基本上它是计算量的上限。给你一个想法,排序20个项目,你看大约400个操作与O(n^2),而与O(n*lg(n))你看20*4.3约86个操作。而对于lg(n)来说,你看到的大约是4.3。不管怎样,数字越大,这个差别就越大。10000个项目表示n*lg(n)的133000个操作和n^2的100000000个操作。对于大型列表,使用较慢的排序开始变得不切实际。当然O(n)只有10000。业务的数量并不完全是这些数字,但它们说明了业务增长的速度。即仅用lg(n)你就可以从4.3增长到133000。n从20增长到10000,n*lgn从86增长到133000,n^2从400增长到100000000。所以基本上,当你的单子越来越大,速度越慢的人会达到他们做不到的程度,但是速度越快的人可以做到。

不管怎样,把它放在上下文中,我看到了气泡排序的以下优点:

1. 易于实施并获得正确的结果。
2. 不会为数组或过程调用消耗额外的空间(假设您不递归地实现它)…这对于低内存环境很好
3. 它按顺序读取数组,这样有利于内存缓存
4. 其他人提到,使用这个方法对链表进行排序很容易
5. 很容易使它稳定
6. 一些面试官肯定会在某个时候提到这一点

泡泡港是 更快 比快速排序(以及几乎所有其他排序)更重要 已经 排序列表;-)

QuickSort 的 最佳案例 BubbleSort 是O(N)!

除了这个异国情调,我同意唐纳德·克努斯的观点, 计算机编程艺术,第3卷:分类和搜索 :

实际上,除了非常小的列表之外,您永远不会使用它。对于足够小的列表,较低的开销可以使其优于更高级的排序。我从来不会用它做超过一打的东西。