对于通用排序，答案似乎是否定的，因为快速排序、合并排序和堆排序在平均情况和最坏情况下往往表现更好。然而，插入排序似乎在增量排序方面表现出色，即在很长一段时间内一次向列表添加一个元素，同时保持列表排序，特别是如果插入排序是作为链表实现的（O(log n) 平均情况与 O(n))。然而，堆似乎能够（或几乎）执行增量排序（从堆中添加或删除单个元素的最坏情况为 O(log n)）。那么，与其他基于比较的排序算法或堆相比，插入排序到底有什么优势呢？
From http://www.sorting-algorithms.com/insertion-sort:
Although it is one of the elementary sorting algorithms with
O(n2) worst-case time, insertion sort
is the algorithm of choice either when
the data is nearly sorted (because it
is adaptive) or when the problem size
is small (because it has low
overhead).
由于这些原因，并且由于它也是稳定的，插入排序是
通常用作递归基本情况
（当问题规模较小时）
更高的开销分而治之
排序算法，例如归并排序
或快速排序。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
