冒泡排序与选择排序相比如何？

哪种排序技术更快：冒泡排序或选择排序，为什么？两者效率相同吗？

维基百科 http://en.wikipedia.org/wiki/Selection_sort说（强调）：

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.

简单计算可知 因此，插入排序通常会 执行大约一半的比较 作为选择排序，虽然它可以 执行同样多或更少的操作 取决于数组的顺序 在排序之前。可以看作 对于一些实时的有优势 选择排序的应用 无论什么，都执行相同的操作 插入时数组的顺序 排序的运行时间可能会有所不同 相当。然而，这更 通常是插入排序的优势 因为它运行效率更高 如果数组已经排序或者 “接近排序。”

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 个元素）。 A 实践中有用的优化 递归算法是切换 插入排序或选择排序 对于“足够小”的子列表。

并且，维基百科上冒泡排序 http://en.wikipedia.org/wiki/Bubble_sort（强调）：

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)。相比之下，大多数 其他算法，即使是那些具有 更好的平均情况复杂度， 执行整个排序过程 在集合上，因此更加复杂。 然而，插入排序不仅 也有这个机制，但也 在列表中表现更好 基本上排序（有一个小的 反转次数）。