希尔排序的递增序列

Question

希尔排序的递增序列是怎样选定下来的，我看《算法（第四版）》中希尔排序的递增序列也是如此，这个递增序列的优点在哪？

Answer 1

liuyubobobo 2018-12-19 11:44:32

这个增量序列，是生成方式简单（代码简单），同时统计意义上，让希尔排序效率较高的一个增量序列。

具体这个递增序列，是这篇文章的A003462号increment sequence。https://hbfs.wordpress.com/2011/03/01/shellsort/ 

通过这篇文章，也可以看出来，increment sequence可以随意设计，但是通过比较，不同的increment sequence，性能不同。有很多专门的论文研究比较shell sort中不同的increment sequence对性能的影响。到现在都没有定论那个序列最好，算是算法领域最经典的一个“开放”问题了：）