希尔排序的递增序列
来源：2-7 更多关于O(n^2)排序算法的思考
阮威敏
2018-12-19
希尔排序的递增序列是怎样选定下来的，我看《算法（第四版）》中希尔排序的递增序列也是如此，这个递增序列的优点在哪？
写回答
1回答
-
liuyubobobo
2018-12-19
这个增量序列，是生成方式简单（代码简单），同时统计意义上，让希尔排序效率较高的一个增量序列。
具体这个递增序列，是这篇文章的A003462号increment sequence。https://hbfs.wordpress.com/2011/03/01/shellsort/
通过这篇文章，也可以看出来，increment sequence可以随意设计，但是通过比较，不同的increment sequence，性能不同。有很多专门的论文研究比较shell sort中不同的increment sequence对性能的影响。到现在都没有定论那个序列最好，算是算法领域最经典的一个“开放”问题了：）
20
相似问题