插入排序比冒泡排序更好？

Question

我正在为考试做修改.

想知道在什么条件下插入排序比O(N ^ 2)的相同平均情况复杂度的冒泡排序更好.

我确实找到了一些相关的文章,但我无法理解它们.

有人会介意以简单的方式解释它吗？

Answer 1

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

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

但是,即使在这种情况下插入排序也会获得更好/相同的性能.

Bubblesort或多或少只对理解和/或教授sortalgorithm的机制有好处,但是现在在编程中找不到合适的用法,因为它的复杂性

O(N²)

意味着它的效率在超过少量元素的列表中显着降低.

Answer 2

我想您正在寻找的答案就在这里：

冒泡排序也可以有效地用于已经排序的列表（除了极少量的元素之外）。例如，如果只有一个元素不有序，冒泡排序只需要 2n 次。如果两个元素不按顺序排列，冒泡排序最多只需要 3n 次......

和

插入排序是一种简单的排序算法，对于小型列表和大多数排序的列表相对有效，并且通常用作更复杂算法的一部分