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

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

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