Insertion Sort与Bubble sort与Selection sort的功效？

Question

我写下了Insertion Sort比Selection Sort快，Selection Sort比Bubble Sort快，它们3个的运行时间都是O(n^2)，但是我怎么说才能把它们比下去呢？

Answer 1

你可以根据以下标准来比较排序算法。

1. 时间复杂度（大O符号）。你应该注意，最佳情况、最坏情况和平均运行时间可以有不同的时间复杂度。 例如Bubble Sort的best-case只有O(n)，当原始列表大部分都是有序的（没有很多元素不到位）时，它比Selection Sort快。
2. 内存复杂度。 随着n的增长，对一个列表进行排序需要增加多少内存？
3. 稳定性。排序是否能保留具有等价排序值的元素的相对排序？(例如，如果你是按照价格对目录项目的列表进行排序，一些元素可能具有相同的价格。 如果目录最初是按物品名称的字母顺序排序的，那么所选的排序算法是否会在每组价格相同的物品中保留字母顺序。)
4. BestWorstAveravge 所需的比较次数。 当比较操作很昂贵时很重要。例如：比较替代设计的效率，效率是通过一些模拟或其他复杂的计算来计算的）。
5. 最佳最差所需交换操作的平均次数。 当交换操作很昂贵时很重要。例如：对必须在船的甲板上实际移动的运输集装箱进行分类）。
6. 代码大小。 Bubble-sort以代码量小著称。

Answer 2

有几种方法可以看出，insertionselectionbubble sort的运行时间都是n^2。

• 它们使用嵌套循环：n个外循环，平均每个外循环有n2个内循环。
• 它们比较所有的元素对：有n*(n-1)2个元素对

以下是关于运行的一些详细分析 插入选择气泡排序.

Answer 3

bubblesort的优势在于检测已经排序的列表的速度。

BubbleSort最好的情况是： O(n)

然而，即使在这种情况下，插入排序也得到了更好的性能。

Bubblesort，或多或少，只适合于理解或教授排序算法的机制，但由于其复杂性，在现在的编程中找不到合适的用途。

O(n²)

意味着其在元素数量超过少量的列表上的效率会急剧下降。