插入排序与冒泡排序与选择排序的效率？

Question

我已经写下插入排序比选择排序更快,这比冒泡排序快,并且他们所有3的运行时间都是O(n ^ 2),但是我能说什么来比较它们呢？

Answer 1

您可以根据以下标准比较排序算法:

1. 时间复杂度(Big-O表示法).您应该注意,最佳情况,最坏情况和平均运行时间可能具有不同的时间复杂度.例如,冒泡排序的最佳情况仅为O(n),当原始列表大部分按顺序(不是很多元素不合适)时,使其比选择排序更快.
2. 记忆复杂性.当n增长时,对列表进行排序需要多少内存？
3. 稳定性.排序是否保留具有等效排序值的元素的相对排序？(例如,如果您按价格对目录项目列表进行排序,则某些元素可能具有相同的价格.如果目录最初按项目名称按字母顺序排序,则所选的排序算法将保留每组等价的字母顺序项目).
4. Best/Worst/Averavge所需的比较次数.比较操作昂贵时很重要.(例如:比较通过某些模拟或其他复杂计算计算效率的替代设计的效率).
5. 所需的最佳/最差/平均交换操作数.交换操作很昂贵时很重要.(例如:分拣必须在船甲板上物理移动的集装箱)
6. 代码大小.冒泡排序以其较小的代码占用而闻名.