什么是泡泡擅长什么？

Question

可能重复:
什么是气泡排序适合？

我确信每种算法都有其优点和缺点,那么与其他排序算法相比,buble sort怎么样呢？(当然我希望答案不是"易于学习")

Answer 1

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

Answer 2

性能方面,冒泡排序不是很好(O(n ^ 2)).以下是它的一些优点:

• 冒泡排序很容易正确编写(如果你正在做一些快速和脏的事情,那么使用冒泡排序可能更容易).

• 内存消耗非常低(因为它是就地排序,不像Merge Sort for arrays)

Answer 3

它很简单,可以在学校里播放,而不会在一个完整的混乱中结束:"如果你的左邻居比你高,请切换位置."

Answer 4

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

基本上算法是这样的

O(n ^ 2)最差情况下的表现

基本上这比较慢......

• 插入O(n ^ 2)但在已排序的列表上执行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))排序更好.基本上查找Radix Sort,Bucket Sort,Counting Sort等.有很多方案.一般来说,如果可以使用其中一种进行排序,你应该....

**其他种类:**还有许多其他种类可供选择.像shell排序等等...上面的那些更常见.

但无论如何,实际上更快的算法通常更难实现.如果有人告诉我在没有图书馆的情况下在20分钟内对这些数字进行排序,我可能会选择排序.更复杂的更容易出错.而且往往需要额外的空间.您必须评估复杂性,空间和时间权衡.许多编程语言都内置了排序库.

还有一点需要注意的是排序是否稳定.基本上如果你有A,C,D,C,G,C将使每个C按顺序出现,或者最后一个C出现在其他C之一之前.如果要对多个字段进行排序,这很重要.即如果你按名字和姓氏排序(Alex Rodriguez,Jane Rodriguez,Betty Rodriguez)......首先你会得到(Alex R,Betty R,Jane R).第二种如果它稳定你会得到Alex R,Betty R,Jane R.如果它不稳定,你可以获得任何订单.通常,气泡和插入易于实现以保持稳定.堆排序和快速排序通常不稳定.合并排序很容易实现稳定.这也是选择的因素....

此外,如果您不知道O(n)表示法,基本上它是计算所需计算量的上限.为了给你一个想法,你可以用O(n*lg(n))对你正在查看大约400个操作的20个项目进行排序,你会看到20*大约4.3,所以大约有86个操作.对于lg(n)你看4.3左右.无论如何,数字越大,这个差异越大.对于n*lg(n),10000个项目是133000个操作,对于n ^ 2,是100000000个.对于使用较慢排序的大型列表开始变得不切实际.当然O(n)只有10,000.操作的数量并不完全是那些数字,但它们说明它的增长速度.即只需lg(n),你就可以从4.3增长到20,增加到133000.随着你从n增长到20,你从n增长到10000,你从86增长到133000,n ^ 2你从400增长到100000000.

无论如何把它全部放在上下文中我看到冒泡排序的以下优点:

1. 易于实施和正确.
2. 不会为数组或过程调用消耗额外的空间(假设您没有递归地实现它)......对于低内存环境非常有用
3. 它按顺序读取数组,因此这对内存缓存很有用
4. 其他人提到很容易使用它来对链表进行排序
5. 很容易使这个稳定
6. 有些采访者无疑会在某些时候提到这一点

无论如何,在库中快速排序和稳定合并排序似乎是最受欢迎的.

Answer 5

冒泡排序是对三个项目列表进行排序的最快方法.除了极少数例外,所有排序都会退化为三种列表的冒泡排序形式.

Answer 6

BubbleSort 比已经排序的列表上的QuickSort (以及几乎所有其他类型)更快 ;-)

QuickSort的最佳表现是O(N log N),BubbleSort是O(N)!

除了这种异国情调外,我不得不同意Donald Knuth,"计算机编程艺术",Vol.3:排序和搜索:

简而言之,泡沫排序似乎没有什么可推荐的,除了一个吸引人的名字和它导致一些有趣的理论问题的事实