气泡排序与选择排序相比如何？ [英] How does bubble sort compare to selection sort?

问题描述

哪种排序技术更快：气泡排序或选择排序，为什么？两者都同样有效吗？

Which sorting technique is faster: bubble or selection sort, and why? Are both equally efficient?

推荐答案

维基百科说（添加了重点）：

在简单平均情况下，Θ（n < sup> 2 ）
算法，选择排序几乎
总是胜过气泡排序和
gnome排序，但通常
优于插入排序。
插入排序与第k次迭代后的
非常相似，数组中的前k个
元素按
排序。插入排序的优点是
，它仅扫描所需数量的元素即可放置k + 1st
元素，而选择排序则必须
扫描所有其余元素才能找到
k + 1st元素。

Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort, but is generally outperformed by insertion sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.

简单的计算表明，
插入排序通常将执行
约一半的比较
作为选择排序，尽管它可以使
执行多少甚至更少的
，具体取决于数组在排序前是
的顺序。可以将
视为某些实时
应用程序的优势，无论数组的
顺序如何，选择排序将使
的性能相同，而插入
排序的运行时间可能相差
。但是，这对于插入排序
来说通常是一个更大的优势，因为如果数组已经排序或
接近排序，它可以更高效地运行
。

Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted."

从
的写入次数（Θ（n）交换与Ο（n ² ）
交换），它几乎总是远远超过
（并且从未超过）循环排序产生的写入
的数量，因为循环排序
在理论上是最优的
次写入。如果
的写入比读取的
昂贵得多，例如使用
EEPROM或闪存，则
的写入会缩短
存储器的寿命，因此这可能很重要。

While selection sort is preferable to insertion sort in terms of number of writes (Θ(n) swaps versus Ο(n²) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.

最后，选择排序在大型数组上的表现要好于Θ（n
log n）分而治之算法
，例如mergesort。但是，对于小型数组
（即少于10-20个元素），插入
排序或选择排序通常都更快
。对于
，递归算法在实践中有用的
有用的优化是将
切换为足够小的子列表的插入排序或选择排序
。

Finally, selection sort is greatly outperformed on larger arrays by Θ(n log n) divide-and-conquer algorithms such as mergesort. However, insertion sort or selection sort are both typically faster for small arrays (i.e. fewer than 10-20 elements). A useful optimization in practice for the recursive algorithms is to switch to insertion sort or selection sort for "small enough" sublists.

并且，气泡排序上的Wikipedia（

And, Wikipedia on bubble sort (emphasis added):

气泡排序的最坏情况和平均
的复杂度都是О（n ² ），其中n是要排序的项目的
数。存在
的许多排序算法，其中
的最坏情况好得多，或者
的平均复杂度为O（n log n）。甚至
的其他О（n ² ）排序算法，例如插入排序的
，也比气泡排序有更好的
性能。
因此，当n为
大时，冒泡排序并不是
的实用排序算法。

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

唯一的优势
冒泡排序比大多数其他
实现（甚至是quicksort）要好，但
不是插入排序，是
检测列表是否为
的能力很有效内置在
算法中。气泡排序
在已经排序的列表
（最佳情况）上的表现为O（n）。相比之下，大多数
的其他算法，甚至那些具有
的平均情况复杂度更高的算法，
都在集合上执行其整个排序过程
，因此更加复杂。
但是，插入排序
不仅也具有这种机制，而且
在经过实质性排序的
的列表上也有更好的表现（其中
的数量很少倒置）。

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. Performance of bubble sort over an already-sorted list (best-case) is O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).

这篇关于气泡排序与选择排序相比如何？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！