泡沫或选择排序 [英] bubble or selection sort

问题描述

该排序技术更快泡沫或选择，为什么？都是同样有效？

which sorting technique is faster bubble or selection and why?Are both equally efficient?

推荐答案

维基百科说（重点补充）：

在简单的平均情况Θ（N ² ）   算法，选择排序几乎   总是优于冒泡排序并   侏儒排序，但一般是   通过插入排序跑赢。   插入排序是在很相似   第k次迭代后，前k   数组中的元素是按排序   订购。插入排序的优势是   它只扫描一样多的元素   它需要，以便将第k + 1号   元素，而选择排序绝   扫描所有剩余的元素找   第k + 1个元素。

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."

虽然选择排序是preferable到   在数量方面插入排序   写（Θ（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）的分而治之算法   如归并。然而，插入   排序或选择排序都   通常对于小数组更快   （即，少于：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.

和，维基百科上冒泡排序（强调）：

And, Wikipedia on bubble sort (emphasis added):

冒泡排序有最坏情况和平均水平   复杂性两者О（正 ² ），其中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.

唯一显著优势   冒泡排序有超过大多数其他   实现，即使是快速排序，但   没有插入排序，是的   能力，以检测该列表为   排序被有效地内置于   算法。冒泡排序的性能   在一个已经排序列表   （最好情况）为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屋！