冒泡排序擅长什么？
可能的重复：
冒泡排序有什么用？
我确信每种算法有它的优点和缺点，那么冒泡排序与其他排序算法相比怎么样呢？ （当然我希望答案不是“容易学”）
Possible Duplicate:
What is a bubble sort good for?
I'am sure every algorithm has its advantage and disadvantage, so how about buble sort compared to other sorting algorithm? (ofcourse I hope the answer is other than "easy to learn")
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
就性能而言，冒泡排序不是很好（O(n^2)）。以下是它的一些优点：
冒泡排序非常容易正确编写（如果您正在做一些快速而肮脏的事情，那么使用冒泡排序可能会更容易）。
内存消耗非常低（因为它是就地排序，与数组的合并排序不同）
Performance-wise, Bubble Sort is not very good (O(n^2)). Here are some of it's advantages:
Bubble Sort is very easy to write correctly (if you're doing something quick and dirty then it might be easier just to use bubble sort).
Memory consumption is very low (because it is an in-place sort, unlike Merge Sort for arrays)
它很简单，可以在学校里玩，而不会以完全混乱的方式结束：
“如果你左边的邻居比你高，请交换位置。”
It's simple enough to play it out in school without it ending in a total mess:
"If your left neighbor is taller than you, please switch places."
编程更容易。即使是经验丰富的程序员也会犯错误，例如快速排序、堆排序和合并排序。而且它不会消耗额外的 log(n) 到 O(n) 的堆栈空间。尽管您可以非递归地实现堆排序。
基本上算法是这个
O(n^2)最坏情况性能
基本上这比较慢......
O(n * lg(n))
当您对输入一无所知时，一般排序最快的排序算法（这实际上已被证明是在不了解输入的情况下进行排序的下限）：
堆排序：不需要额外的空间，可以非递归地实现，但会在数组周围反弹，因此它在缓存上的性能不如其他排序。如果递归实现需要 lg(n) 额外的空间用于调用。
O(n) 次排序
如果您对输入有所了解，您通常可以比 O(n*lg(n)) 更好地进行排序。基本上查一下基数排序、桶排序、计数排序等等。方案有很多。一般来说，如果可以使用其中之一进行排序，您应该......
**其他排序：**
还有许多其他类型可用。像希尔排序等等......上面的比较常见。
但无论如何，在现实中，更快的算法通常更难实现。如果有人告诉我在 20 分钟内对这些数字进行排序，而无需使用库，我可能会编写选择排序。越复杂的越容易出错。并且经常需要额外的空间。您必须权衡复杂性、空间和时间。许多编程语言都内置了排序库。
另一件需要注意的事情是排序是否稳定。基本上，如果您有 A、C、D、C、G、C，则每个 C 都会按顺序出现，或者最后一个 C 会出现在其他 C 之一之前。如果您要对多个字段进行排序，这一点很重要。即，如果您按名字排序，然后按姓氏排序（亚历克斯·罗德里格斯、简·罗德里格斯、贝蒂·罗德里格斯）……您会得到第一个排序（亚历克斯·R、贝蒂·R、简·R）。第二类，如果稳定，你会得到 Alex R，Betty R，Jane R。如果不稳定，你可以得到任何订单。一般来说，气泡法和插入法容易实现且稳定。堆排序和快速排序通常不稳定。归并排序很容易实现并且稳定。这也会影响选择......
此外，如果您不知道 O(n) 表示法，基本上它是所需计算次数的上限。为了给您一个想法，要对 20 个项目进行排序，您需要 O(n^2) 大约 400 次操作，而使用 O(n * lg(n)) 您需要查看 20 * 大约 4.3，因此大约 86 次操作。对于 lg(n)，您正在查看 4.3 左右。无论如何，数字越大，这种差异就越大。 10000 个项目对于 n*lg(n) 来说是 133000 次操作，对于 n^2 来说是 100000000 次操作。对于大型列表，使用较慢的排序开始变得不切实际。当然，O(n) 只是 10,000。运营数量并不完全是这些数字，但它们说明了其增长速度。即，仅使用 lg(n)，你从 4.3 增长到 20 到 133000。使用 n，你从 20 增长到 10000，使用 n * lgn，你从 86 增长到 133000，使用 n^2，你从 400 增长到 100000000。所以基本上就像你的列表变大，较慢的列表将达到无法执行的程度，但较快的列表可以。
无论如何，将所有内容放在上下文中，我发现冒泡排序具有以下优点：
无论如何在库中快速排序和稳定合并排序似乎是最受欢迎的。
It's easier to program. Even seasoned programmers get quick sort, heap sort, and merge sort wrong. Also it does not consume an extra log(n) to O(n) in stack space. Although you can implement heap sort non recursively.
Basically the algorithms are this
O(n^2) worst case performance
Basically this is slower....
O(n * lg(n))
Generally the fastest sorting algorithms for general sorting when you don't know anything about the input (this has actually been proven to be a lower bound on sorting without knowing anything about the input):
Heap Sort: Requires no extra space, can be implemented non recursively, but sort of bounces around the array so it is not as good on the cache as the others. If implemented recursively requires lg(n) extra space for calls.
O(n) sorts
If you know something about your inputs you can often sort better than O(n*lg(n)). Basically look up Radix Sort, Bucket Sort, Counting Sort, etc.. There are many schemes. Generally if it is possible to sort using one of these you should....
**Other Sorts: **
There are many other sorts available. Things like shell sort, etc... the ones above are the more common.
But anyway in reality the faster algorithms are often harder to implement. If someone told me to sort these numbers in 20 minutes without a library, I'd probably write selection sort. The more complex ones are easier to get wrong. And often require additional space. You have to evaluate the complexity, space, and time tradeoffs. Many programming languages have built in sorting libraries.
Also one other thing to be careful of is whether a sort is stable or not. Basically if you have A, C, D, C, G, C will each C appear in order, or will the last C appear before one of the other C's. This is important if you are sorting on multiple fields. Ie if you sort by First Name and then last name (Alex Rodriguez, Jane Rodriguez, Betty Rodriguez)...first sort you'd get (Alex R, Betty R, Jane R). Second sort if it is stable you will get Alex R, Betty R, Jane R. If it is not stable, you could get any order. Generally Bubble and Insertion are easy to implement to be stable. Heap Sort and Quick Sort usually aren't stable. Merge sort is easy to implement as stable. This also factors into choices....
Also if you don't know O(n) notation, basically it is an upper bound on how many computations it takes. To give you an idea, to sort 20 items you are looking at around 400 operations with O(n^2) while with O(n * lg(n)) you are looking at 20 * approx 4.3 so around 86 operations. And for lg(n) you are looking at around 4.3. Anyway the larger the number gets the bigger this difference is. 10000 items is 133000 operations for n*lg(n) and 100000000 for n^2. For large lists using the slower sorts starts to become impractical. And of course O(n) is just 10,000. The number of operations is not exactly those numbers, but they speak to how fast it grows. Ie with just lg(n) you grow from 4.3 for 20 to 133000. With n you grow from 20 to 10000 with n * lgn you grow from 86 to 133000 and with n^2 you grow from 400 to 100000000. So basically as your lists get bigger the slower ones will reach a point where they can't do them but the faster ones can.
Anyway having put it all in context I see the following advantages to bubble sort:
Anyway in libraries Quick Sort and Stable Merge sort seem to be the most popular.
冒泡排序是对三个项目的列表进行排序的最快方法。除了极少数例外，所有排序都会退化为三项列表的冒泡排序形式。
Bubble sort is the fastest way to sort a list of three items. With very few exceptions, all sorts degenerate into a form of bubble sort for lists of three.
在已排序的列表上，冒泡排序比快速排序（以及几乎所有其他排序）更快；-)
QuickSort 的最佳情况性能为 O(N log N)，冒泡排序的时间复杂度为 O(N)！
除了这种异国情调之外，我必须同意 Donald Knuth 的观点，计算机编程的艺术，卷。 3：排序和搜索：
BubbleSort is faster than QuickSort (and almost every other sort) on already sorted lists ;-)
QuickSort's best-case performance is O(N log N), BubbleSort's is O(N) !
Other than this exotic, I'd have to agree with Donald Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching:
实际上，除了非常小的列表之外，您永远不会将它用于任何其他用途。对于足够小的列表，较低的开销可以使其优于更高级的排序。我绝不会用它来处理超过十几件物品。
Realistically you would never use it for anything other than very small lists. For a sufficiently small list the low overhead can make it superior to the fancier sorts. I'd never use it for more than a dozen items.