希尔排序h=h*3+1 其中gap=3 问一下为什么要加一呢？还有gap取的越大是不是越好

来源：2-7 更多关于O(n^2)排序算法的思考

慕婉清5054873

2017-11-27

while( h < n/3 )

h = 3 * h + 1;

写回答

1回答

liuyubobobo

2017-11-28

没有逻辑上的原因。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越大越好。

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1