正如标题所问，为什么插入、冒泡和选择排序具有相同的大o？在我的算法课中，我们已经介绍了上述四种算法和归并排序，为什么还要使用上述任何一种算法而不是归并排序？
问问题
859 次
3 回答
3
虽然它们是不同的算法，但它们具有相同的渐近复杂度，因为在某种程度上，每个算法都会两次通过长度为 n 的列表。关键是 Big-O 是最坏情况下的性能测量。插入排序在最坏的情况下是 O(n^2)，但在最好的情况下，当列表已经排序时，它变成 O(n)。不同的排序算法具有不同的优势，需要超出 big-o 复杂性的分析。
话虽如此，使用 nlog(n) 排序几乎总是更好，而冒泡排序之类的主要功能可能是向人们介绍排序算法的概念。
于 2012-12-16T04:09:52.107 回答
2
尽管像冒泡排序这样的排序算法对于大量项目非常慢，但当您只有少量项目时它们非常快，部分原因是它们非常简单。当项目已经接近正确位置时，冒泡排序或插入排序也很有用。在这种情况下，一个好的排序算法通常会使用一种技术来使项目按课程规模排序，然后使用另一种算法进行精细排序。
于 2012-12-16T04:13:03.580 回答
1
这是这里被问到的更常见的问题之一。Big-O 表示法是一种衡量算法理论界限的方法，这是在最好的情况下得到恒定时间 O(1) 的地方，即使这种情况很少发生，因此是最好的情况。这三种算法之所以具有相同的大 O 是因为它们都以相同的方式解决排序问题，具有相同的大 O 并不意味着这些算法在它们的工作方式上是远程等效的，即使过程类似。从纯粹的学术角度来看，教授这些内容的原因是您能够从历史中学习，而不是认为您会通过提出冒泡排序来“震惊世界”。它还用于显示看似简单的概念，即排序，
于 2012-12-16T04:15:09.150 回答