对于通用排序,答案似乎是否定的,因为快速排序、归并排序和堆排序在平均和最坏情况下往往表现更好。然而,插入排序似乎在增量排序方面表现出色,即在较长时间内一次向列表添加一个元素,同时保持列表排序,特别是如果插入排序实现为链表(O(log n) 平均情况与 O(n))。但是,堆似乎能够(或几乎)执行增量排序(从堆中添加或删除单个元素的最坏情况是 O(log n))。那么与其他基于比较的排序算法或堆相比,插入排序究竟提供了什么?
7 回答
来自http://www.sorting-algorithms.com/insertion-sort:
尽管它是最坏情况时间为 O(n 2 ) 的基本排序算法之一,但插入排序是当数据接近排序(因为它是自适应的)或当问题规模很小(因为它开销低)。
由于这些原因,并且由于它也很稳定,因此插入排序通常用作递归基本情况(当问题规模较小时),用于更高开销的分治排序算法,例如合并排序或快速排序。
算法分析中的一个重要概念是渐近分析。在具有不同渐近运行时间的两种算法的情况下,例如一种 O(n^2) 和一种 O(nlogn),分别是插入排序和快速排序的情况,并不能确定一种比另一种快。
这种分析的重要区别在于,对于足够大的 N,一种算法将比另一种算法更快。在将算法分析到 O(nlogn) 之类的术语时,您会删除常量。在实际分析算法的运行时,这些常数仅在 n 较小的情况下才重要。
那么这是什么意思?这意味着对于某些小的 n,某些算法更快。这篇来自 EmbeddedGurus.net 的文章包含了一个有趣的观点,即在有限空间 (16k) 和有限内存系统的情况下选择不同的排序算法。当然,本文仅引用了对 20 个整数的列表进行排序,因此 n 的较大顺序无关紧要。更短的代码和更少的内存消耗(以及避免递归)最终是更重要的决定。
插入排序开销低,可以写得相当简洁,并且它有几个两个关键的好处:它是稳定的,并且当输入接近排序时它有一个相当快的运行情况。
是的,有理由使用插入排序或其变体之一。
此处其他答案的排序选项(快速排序等)假设数据已经在内存中并准备就绪。
但是,如果您尝试从较慢的外部源(例如硬盘驱动器)读取大量数据,则会浪费大量时间,因为瓶颈显然是数据通道或驱动器本身。它只是跟不上CPU。在任何读取过程中都会发生一系列自然的等待。这些等待是浪费的 CPU 周期,除非您使用它们进行排序。
例如,如果您要解决此问题,请执行以下操作:
- 将专用循环中的大量数据读入内存
- 对该数据进行排序
与在两个线程中执行以下操作相比,您很可能需要更长的时间。
线程 A:
- 读取数据
- 将数据放入 FIFO 队列
- (重复直到数据从驱动器中耗尽)
线程 B:
- 从 FIFO 队列中获取数据
- 将其插入排序列表中的适当位置
- (重复直到队列为空并且线程 A 说“完成”)。
...以上将允许您使用否则浪费的时间。注意:线程 B 不会阻碍线程 A 的进展。
当数据被完全读取时,它已经被分类并准备好使用了。
大多数排序过程将使用快速排序,然后对非常小的数据集使用插入排序。
如果您正在谈论维护排序列表,则与某种树相比没有优势,只是速度较慢。
好吧,也许它消耗更少的内存或者是一个更简单的实现。
插入排序列表会涉及扫描,这意味着每次插入都是 O(n),因此排序 n 项变为 O(n^2)
插入平衡树等容器通常是 log(n),因此排序是 O(n log(n)),这当然更好。
但对于小型列表,它几乎没有任何区别。如果您必须自己编写而不使用任何库、列表很小和/或您不关心性能,则可以使用插入排序。
是的,
插入排序在短列表上优于快速排序。
事实上,最佳快速排序有一个大小阈值,它会在该阈值处停止,然后整个数组通过插入排序超过阈值限制进行排序。
还...
为了维护记分牌,二元插入排序可能会尽可能好。
请参阅此页面。
对于小数组大小的插入排序优于快速排序。 Java 7 和 Java 8使用双主元快速排序对原始数据类型进行排序。双轴快速分拣执行典型的单轴快速分拣。根据双轴快速排序算法:
- 对于小数组(长度 < 27),使用插入排序算法。
- 选择两个支点…………
当然,插入排序对较小的数组大小执行快速排序,这就是为什么要 为长度小于 27 的数组切换到插入排序。原因可能是:插入排序中没有递归。
资料来源:http ://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf