我想知道你是否会使用插入或选择几乎排序的文件.他们两个平均做多少掉期？我听过两个N/2并O(n)用于选择!我知道插入时你必须扫描数组的已排序部分以找到放置新元素的位置但是在选择中,你必须扫描数组的整个未排序部分以找到要添加到未排序子数组开头的下一个元素.
有许多流行的排序算法旨在利用几乎排序的数据.可能最受欢迎的是timsort,以Tim Peters 为名,他是Python核心开发人员,他首先提出并实现了算法作为Python中使用的默认排序算法.排序算法现在也用作许多Java版本中的默认排序算法.
Timsort是一种混合稳定排序算法,源自合并排序和插入排序,旨在很好地处理多种真实数据.[...]算法查找已经排序的数据的子序列,并使用该知识更有效地对剩余部分进行排序.这是通过将已识别的子序列(称为运行)与现有运行合并直到满足某些条件来完成的.[...] 维基百科
当数据几乎按照它近似排序的意义排序时,插入排序非常有效:
当输入中的每个元素距离其排序位置维基百科不超过k个位置时,时间复杂度为O(nk)
插入排序不能利用数据几乎排序的许多其他常见情况,例如颠倒顺序或数据由两组排序数据组成(例如,从连接两个排序数组的结果).
选择排序并没有真正受益于几乎排序的数据.因此,如果您确实知道您的数据中有一些接近排序,那么这是一个糟糕的算法选择.