algorithm - 是否有充分的理由使用插入排序？

Question

对于通用排序，答案似乎是否定的，因为快速排序、归并排序和堆排序在平均和最坏情况下往往表现更好。然而，插入排序似乎在增量排序方面表现出色，即在较长时间内一次向列表添加一个元素，同时保持列表排序，特别是如果插入排序实现为链表（O(log n) 平均情况与 O(n))。但是，堆似乎能够（或几乎）执行增量排序（从堆中添加或删除单个元素的最坏情况是 O(log n)）。那么与其他基于比较的排序算法或堆相比，插入排序究竟提供了什么？

Answer 1

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

尽管它是最坏情况时间为 O(n ² ) 的基本排序算法之一，但插入排序是当数据接近排序（因为它是自适应的）或当问题规模很小（因为它开销低）。

由于这些原因，并且由于它也很稳定，因此插入排序通常用作递归基本情况（当问题规模较小时），用于更高开销的分治排序算法，例如合并排序或快速排序。

Answer 2

算法分析中的一个重要概念是渐近分析。在具有不同渐近运行时间的两种算法的情况下，例如一种 O(n^2) 和一种 O(nlogn)，分别是插入排序和快速排序的情况，并不能确定一种比另一种快。

这种分析的重要区别在于，对于足够大的 N，一种算法将比另一种算法更快。在将算法分析到 O(nlogn) 之类的术语时，您会删除常量。在实际分析算法的运行时，这些常数仅在 n 较小的情况下才重要。

那么这是什么意思？这意味着对于某些小的 n，某些算法更快。这篇来自 EmbeddedGurus.net 的文章包含了一个有趣的观点，即在有限空间 (16k) 和有限内存系统的情况下选择不同的排序算法。当然，本文仅引用了对 20 个整数的列表进行排序，因此 n 的较大顺序无关紧要。更短的代码和更少的内存消耗（以及避免递归）最终是更重要的决定。

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

Answer 3

是的，有理由使用插入排序或其变体之一。

此处其他答案的排序选项（快速排序等）假设数据已经在内存中并准备就绪。

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

例如，如果您要解决此问题，请执行以下操作：

1. 将专用循环中的大量数据读入内存
2. 对该数据进行排序

与在两个线程中执行以下操作相比，您很可能需要更长的时间。

线程 A：

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

线程 B：

1. 从 FIFO 队列中获取数据
2. 将其插入排序列表中的适当位置
3. （重复直到队列为空并且线程 A 说“完成”）。

...以上将允许您使用否则浪费的时间。注意：线程 B 不会阻碍线程 A 的进展。

当数据被完全读取时，它已经被分类并准备好使用了。

Answer 4

大多数排序过程将使用快速排序，然后对非常小的数据集使用插入排序。

Answer 5

如果您正在谈论维护排序列表，则与某种树相比没有优势，只是速度较慢。

好吧，也许它消耗更少的内存或者是一个更简单的实现。

插入排序列表会涉及扫描，这意味着每次插入都是 O(n)，因此排序 n 项变为 O(n^2)

插入平衡树等容器通常是 log(n)，因此排序是 O(n log(n))，这当然更好。

但对于小型列表，它几乎没有任何区别。如果您必须自己编写而不使用任何库、列表很小和/或您不关心性能，则可以使用插入排序。

Answer 6

是的，

插入排序在短列表上优于快速排序。

事实上，最佳快速排序有一个大小阈值，它会在该阈值处停止，然后整个数组通过插入排序超过阈值限制进行排序。

还...

为了维护记分牌，二元插入排序可能会尽可能好。

请参阅此页面。

Answer 7

对于小数组大小的插入排序优于快速排序。 Java 7 和 Java 8使用双主元快速排序对原始数据类型进行排序。双轴快速分拣执行典型的单轴快速分拣。根据双轴快速排序算法：

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

当然，插入排序对较小的数组大小执行快速排序，这就是为什么要 为长度小于 27 的数组切换到插入排序。原因可能是：插入排序中没有递归。

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