我正在为考试做复习。
想知道在 O(N^2) 的平均情况复杂度相同的情况下，插入排序在什么条件下会比冒泡排序表现更好。
我确实找到了一些相关的文章，但我无法理解。
有人介意用简单的方式解释吗？
问问题
24886 次
5 回答
5
冒泡排序的优势在于检测已排序列表的速度：
BubbleSort 最佳案例场景：O(n)
然而，即使在这种情况下，插入排序也得到了更好/相同的性能。
冒泡排序或多或少只有助于理解和/或教授排序算法的机制，但现在在编程中找不到合适的用法，因为它的复杂性
O(n²)
意味着它的效率在超过少量元素的列表上急剧下降。
于 2012-05-03T09:40:57.747 回答
4
我想到了以下几点：
冒泡排序总是需要再传递一次数组来确定它是否已排序。另一方面，插入排序不需要这个——一旦插入最后一个元素，算法就保证数组是排序的。
冒泡排序
n在每次通过时都会进行比较。插入排序比比较少n：一旦算法找到插入当前元素的位置，它就会停止比较并取下一个元素。最后，引用维基百科文章：
冒泡排序与现代 CPU 硬件的交互也很差。它需要至少两倍于插入排序的写入、两倍的缓存未命中以及渐近更多的分支错误预测。Astrachan 在 Java 中对字符串进行排序的实验表明，冒泡排序比插入排序慢大约 5 倍，比选择排序慢 40%
你可以在那里找到原始研究论文的链接。
于 2012-05-03T10:16:52.220 回答
0
在最坏的情况下，两者都倾向于在 O(n^2) 时执行
在最好的情况下，即当数组已经排序时，冒泡排序可以在 O(n) 处执行。
于 2013-04-04T18:02:03.817 回答
0
你能提供你不明白的相关文章的链接吗？我不确定他们可能会解决哪些方面的问题。除此之外，还有一个理论上的区别可能是冒泡排序更适合表示为数组的集合（而不是表示为链表的集合），而插入排序更适合链表。
原因是冒泡排序总是一次交换两个项目，这在数组和链表上都是微不足道的（对数组更有效），而插入排序插入到给定列表中的一个位置，这对于链表来说微不足道，但涉及将数组中的所有后续元素向右移动。
话虽这么说，但还是要加一粒盐。首先，实际上，排序数组几乎总是比排序链表快。仅仅因为扫描一次列表已经有很大的不同。除此之外，将数组的 n 个元素向右移动比执行 n（甚至 n/2）个交换要快得多。这就是为什么其他答案正确地声称插入排序总体上是优越的，以及为什么我真的想知道您阅读的文章，因为我想不出一种简单的方式来说明这在案例 A 中更好，而在案例 A 中更好B.
于 2012-05-03T10:17:55.313 回答
0
我想您正在寻找的答案在这里：
冒泡排序也可以有效地用于除了极少数元素之外已经排序的列表。例如，如果只有一个元素没有排序，冒泡排序只需要 2n 次。如果两个元素不按顺序排列，冒泡排序最多只需要 3n 次...
和
插入排序是一种简单的排序算法，对于小列表和大多数排序列表相对有效，并且通常用作更复杂算法的一部分
于 2012-05-03T09:30:47.767 回答