希尔排序h=h*3+1中的gap=3 请问这个increment是不是越大越好

Answer 1

liuyubobobo 2017-11-28 04:39:33

没有逻辑上的原因。1, 4, 13, 40... 这是我取的一个increment sequence而已，具体是这篇文章的A003462号increment sequence。https://hbfs.wordpress.com/2011/03/01/shellsort/

通过这篇文章，也可以看出来，increment sequence可以随意设计，但是通过比较，不同的increment sequence，性能不同。有很多专门的论文研究比较shell sort中不同的increment sequence对性能的影响。所以不一定gap越大越好。