插入排序vs冒泡排序vs选择排序的效率? [英] Efficency of Insertion Sort vs Bubble sort vs Selection sort?

问题描述

我已经写下插入排序比选择排序快，比气泡排序快的问题，并且它们在全部3个对象中的运行时间均为O(n ^ 2)，但是我可以说将它们相互比较?

I have written down that Insertion Sort is faster than Selection Sort, which is faster than Bubble Sort, and that their running time for all 3 are O(n^2), but what can I say to compare them with each other?

推荐答案

您可以将排序算法与以下条件进行比较:

You can compare sorting algorithms against the following criteria:

1. 时间复杂度(Big-O表示法).您应该注意，最佳情况，最坏情况和平均运行时间可能具有不同的时间复杂度.例如，冒泡排序的最佳情况只有O(n)，当原始列表大多按顺序排列(元素不多的地方)时，它比选择排序要快.
2. 内存复杂度.随着n的增加，对列表进行排序需要多少内存?
3. 稳定性.排序是否保留具有相等排序值的元素的相对顺序? (例如，如果您按价格对目录项列表进行排序，则某些元素的价格可能相等.如果目录本来是按项名按字母顺序排序的，则所选的排序算法是否将按等价价格在每个组中保留字母顺序项目.)
4. 最佳/最差/平均比较次数.比较操作很昂贵时很重要. (例如:比较通过一些模拟或其他复杂计算来计算效率的替代设计的效率).
5. 最佳/最差/平均所需的交换操作数.当交换操作很昂贵时很重要. (例如:对必须在船甲板上实际移动的运输集装箱进行分类)
6. 代码大小. Bubble-sort以其较小的代码占用量而闻名.

这篇关于插入排序vs冒泡排序vs选择排序的效率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！