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

Question

哪种排序技术更快:泡泡或选择排序,为什么？两者同样有效吗？

Answer 1

维基百科说(重点补充):

在简单的平均情况Θ(n ²)算法中,选择排序几乎总是优于冒泡排序和gnome排序,但通常优于插入排序.插入排序非常相似,在第k次迭代之后,数组中的前k个元素按排序顺序排列.插入排序的优点是它只扫描所需的元素以放置第k + 1个元素,而选择排序必须扫描所有剩余的元素以找到第k + 1个元素.

简单的计算表明,插入排序通常会执行大约一半的选择排序,尽管它可以执行同样多的或更少的操作,具体取决于排序前数组的顺序.对于某些实时应用程序而言,无论数组的顺序如何,选择排序都将执行相同的操作,这可以被视为优势,而插入排序的运行时间可能会有很大差异.但是,这通常是插入排序的一个优点,因为如果数组已经排序或"接近排序",它的运行效率会更高.

虽然选择排序在写入次数(Θ(n)交换与Ο(n ²)交换)方面优于插入排序,但它几乎总是远远超过(并且永远不会超过)循环排序所做的写入次数,如循环从理论上讲,sort在写入次数上是最优的.如果写入比读取要贵得多,例如使用EEPROM或闪存,每次写入都会缩短内存的使用寿命,这一点非常重要.

最后,通过Θ(n log n)分而治之算法(例如mergesort),选择排序在大型阵列上大大优于大多数.但是,对于小型阵列(即少于10-20个元素),插入排序或选择排序通常都更快.递归算法在实践中的有用优化是切换到"足够小"子列表的插入排序或选择排序.

并且,维基百科关于冒泡排序(重点补充):

冒泡排序具有最坏情况和平均复杂度О(n ²),其中n是被排序的项目数.存在许多具有明显更好的O(n log n)的最坏情况或平均复杂度的排序算法.甚至其他О(n ²)排序算法(例如插入排序)往往具有比冒泡排序更好的性能.因此,当n很大时,冒泡排序不是一种实用的排序算法.

冒泡排序对大多数其他实现(甚至是快速排序,但不是插入排序)的唯一显着优势是,检测列表已排序的能力被有效地构建到算法中.对已经排序的列表(最佳情况)进行冒泡排序的性能是O(n).相比之下,大多数其他算法,即使是具有更好的平均情况复杂度的算法,也会在集合上执行整个排序过程,因此更加复杂.但是,插入排序不仅具有此机制,而且在基本排序(具有少量反转)的列表上也表现更好.

Answer 2

与冒泡排序相比,选择排序执行的交换数量较少; 因此,即使两种排序方法都是O(N ²),选择排序也会更快,更有效!