梳子排序的运行时间是多少？

Question

据我所知，梳状排序也应该在子二次时间运行，就像shell排序一样。这是因为梳排序是泡状排序，而shell排序与插入排序是如何关联的。Shell排序根据应用插入排序的间隙序列对数组进行排序，类似地，梳排序按照应用气泡排序的间隙序列对数组进行排序。那么梳子排序的运行时间是多少？

Answer 1

用什么顺序递增？

如果选择增量为:小于N的形式(2^p * 3^q)的所有数的集合，则运行时间优于二次(与N的对数平方的N成正比)。对于这组增量，Combsort使用相同的增量( "Pratt序列“)执行与Shell排序完全相同的交换。但人们在谈论Combsort时通常并不是这样想的。

理论上..。

随着增量呈几何级数递减(例如，每次通过输入时，增量约为上一次增量的80% )，这就是人们在谈论Combsort时通常所指的。是的，在最坏情况和平均情况下，它都是二次型的.但是..。

在实践中。

只要增量是相对素数，且一个增量与下一个增量之间的比值是合理的(80%是好的)，n就必须大得惊人，才能使平均运行时间大大超过n.log(n)。我一次对数亿条记录进行了排序，只有当我通过构造“杀手输入”来精心设计这些记录时，我才见过二次运行时间。在实践中，相对于素数增量(相邻增量之间的比率为1.25:1)，即使对数百万条记录来说，Combsort平均需要3倍于合并长度的比较，并且通常需要运行2到3倍的时间。