插入排序有何优点可言？

Question

就一般而言，快速排序、归并排序和堆排序似乎在平均情况和最坏情况下表现更好，因此不能做到啥都行。然而，插入排序似乎在增量排序方面表现出色，也就是说，在长时间内将元素逐个添加到列表中，并保持列表排序，特别是如果将插入排序实现为链表 (O(log n) 平均情况下 vs. O(n))。然而，堆看起来也能够执行增量排序，而且执行效果同样不错（从堆中添加或移除单个元素的最坏情况是 O(log n)）。那么相比于其他基于比较的排序算法或堆，插入排序究竟有哪些优势呢？

- CS Student

---

如果你正在从较慢的外部源（如硬盘）加载大量数据，则通常最好使用一种边排序边进行的算法，以利用 CPU 等待驱动器赶上的浪费周期。[参见我下面的答案]（https://dev59.com/AXRB5IYBdhLWcg3wCjrO#30193315）。 - user4229245

Answer 1

来自http://www.sorting-algorithms.com/insertion-sort：

虽然插入排序是具有$O(n^2)$最坏时间复杂度的基本排序算法之一，但当数据接近排序状态（因为它是自适应的），或者问题规模较小（因为它的开销较低）时，插入排序是首选的算法。

出于这些原因，以及因为它也是稳定的，插入排序通常被用作高开销分治排序算法（例如归并排序或快速排序）的递归基线情形（当问题规模较小时）。

- guns

---

啊，我忘记了稳定性……我提到的其他算法都不稳定。 - CS Student

插入排序的内部循环正好适合现代CPU和缓存——它是一个非常紧凑的循环，仅以递增顺序访问内存。 - j_random_hacker

快速排序可以实现为稳定排序，但由于它对随机集合最优，因此我认为高效的qsort函数在排序之前有意使数据随机化。 - guns

插入排序也很好，因为它在在线情况下非常有用，当您一次获取一个元素时。 - sykora

如果有人想知道这里的稳定性是什么意思，请查看https://dev59.com/lHI_5IYBdhLWcg3wHvQ5。 - Usman

Answer 2

算法分析中的一个重要概念是渐进分析。对于两个具有不同渐近运行时间的算法，例如插入排序和快速排序分别为 O(n^2) 和 O(nlogn)，并不能确定哪一个更快。

这种分析的重要区别在于，对于足够大的 N，一个算法将比另一个算法更快。当将算法分析到类似 O(nlogn) 的术语时，可以省略常数。在实际分析算法时，这些常数仅对小 n 的情况很重要。

那么这意味着什么？这意味着对于某些小 n，某些算法更快。EmbeddedGurus.net 的文章提供了一个有趣的视角，介绍了在空间有限（16k）和内存有限的系统中选择不同排序算法的情况。当然，该文章仅参考了对包含20个整数的列表进行排序的情况，因此更大的 n 是无关紧要的。更短的代码、更少的内存消耗（以及避免递归）最终是更重要的决策。

插入排序具有低开销，可以编写得相当简洁，并且具有两个关键优点：它是稳定的，并且在输入接近排序时具有相当快的运行情况。

- Anthony

Answer 3

是的，使用插入排序或其变体有其原因。

其他答案中提到的排序替代方案（快速排序等）假设数据已经在内存中并准备就绪。

但是，如果您试图从较慢的外部源（例如硬盘）读取大量数据，则会浪费大量时间，因为瓶颈显然是数据通道或驱动器本身。它无法跟上CPU的速度。任何读取期间都会发生自然的等待序列。除非您在排序过程中利用这些等待来进行排序，否则这些等待将成为浪费的CPU周期。

例如，如果您将解决此问题的方法设置为以下内容：

1. 在专用循环中读取大量数据到内存中
2. 对该数据进行排序

您很可能需要比使用两个线程执行以下操作更长的时间。

线程A：

1. 读取数据
2. 将数据放入FIFO队列中
3. （重复直到从驱动器中耗尽数据）

线程B：

1. 从FIFO队列中获取数据
2. 将其插入到已排序列表的正确位置中
3. (重复执行，直到队列为空且Thread A表示“完成”)。

...以上步骤可以利用其他时间。注意：线程B不会妨碍线程A的进度。

等到数据被完全读取时，它将已经被排序并准备好使用。

- user4229245

Answer 4

大多数排序程序会使用快速排序，对于非常小的数据集，则会使用插入排序。

- BobbyShaftoe

Answer 5

如果你想要维护一个已排序的列表，那么它与某种树相比并没有任何优势，只是更慢一些。或许它会消耗更少的内存或者实现更简单。向已排序的列表中插入元素需要扫描，这意味着每次插入的时间复杂度为O(n)，因此对n个元素进行排序的时间复杂度为O(n^2)。而将元素插入到平衡树等容器中通常是log(n)，因此排序的时间复杂度为O(n log(n))，当然更好。但是对于小型列表来说，几乎没有什么区别。如果你必须自己编写代码而没有使用任何库、列表很小和/或你不关心性能，则可以使用插入排序。

- MarkR

Answer 6

是的，

在短列表上，插入排序比快速排序更好。

事实上，最佳的快速排序有一个尺寸阈值，在此处停止，然后通过插入排序对超过阈值的整个数组进行排序。

此外...

为了维护记分板，二进制插入排序可能是最好的选择。

请参见此页面。

- JohnPaul

---

“记分牌”概念，其中项目逐个提供，让我想起了这种情况的“双重性”，其中项目需要从排序中逐个返回（如选择排序）。 我编写了一个NlgN排序，它首先返回第一个元素，第二个元素等等。 记账开销非常可怕，但与我对其进行基准测试的库qsort（）相比，比较次数要小。 从所有节点开始，在主池中具有得分为1的得分。 反复从主池中取出两个得分最低的项目并进行比较... - supercat

将“胜者”放回主要得分中，将输者的得分加到自己的得分中，并将输者放入“备用”池中，其得分不变。继续进行，直到主池只剩下一个元素。该元素是最好的，因此输出它，并将所有与获胜元素相比较的元素移动到主池中。然后像以前一样从主池中取出项目，直到只剩下一个（第二好的项目）。在任何给定时间，备用池中的每个项目都会劣于主池中至少一个项目，而主池中没有任何项目... - supercat

...会被认为是比任何一个池中的其他内容都要劣。虽然主池最初将拥有其中的所有 N 个项目，但后续的比较只包括与“赢家”进行过比较的项目，因此输出第一个项目之后的项目将相当快速。 - supercat

Answer 7

对于小型数组，插入排序优于快速排序。 Java 7和Java 8使用双轴快速排序来排序原始数据类型。双轴快速排序优于传统的单轴快速排序。根据双轴快速排序算法：

1. 对于小数组（长度<27），使用插入排序算法。
2. 选择两个枢轴...

显然，对于较小的数组大小，插入排序比快速排序更有效，这就是为什么你 切换到插入排序处理长度小于27的数组 的原因。原因可能是：插入排序中没有递归。

来源: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

- Kangkan Lahkar