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

Question

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

Answer 1

您可以将排序算法与以下标准进行比较：

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

Answer 2

有几种方法可以看到插入/选择/冒泡排序都在 n^2 时间内运行。

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

下面是对插入/选择/冒泡排序运行的一些详细分析。

Answer 3

冒泡排序的优势在于检测已排序列表的速度：

BubbleSort 最佳案例场景：O(n)

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

冒泡排序或多或少只有助于理解和/或教授排序算法的机制，但现在在编程中找不到合适的用法，因为它的复杂性

O(n²)

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