对于通用排序,答案似乎是否定的,因为快速排序,合并排序和堆排序往往在平均和最差情况下表现更好.但是,插入排序似乎在增量排序方面表现优异,即在保持列表排序的同时,在一段时间内一次向列表添加元素,尤其是在插入排序实现为链接列表时(O(log) n)平均情况与O(n)).但是,堆似乎能够(或几乎)执行增量排序(从堆中添加或删除单个元素具有O(log n)的最坏情况).那么插入排序与其他基于比较的排序算法或堆有什么关系呢？
我有一个字符串列表,已按特定的比较函数排序.
现在我必须使用不同的比较函数重新排序此列表.
这种新的比较函数在比较某些特殊字符(例如变形金刚)时表现略有不同.在大多数情况下,元件必须仅移动一个或两个槽以到达正确的位置.
哪种排序算法最适合根据运行时执行速度对这个几乎完全排序的列表进行重新排序？