ShellSort

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

LeeDada

2016-11-02

int h = 1;
while(h < n/3) h = h*3 + 1;

希尔排序的例子中，我知道h是1，4，13的序列，但是为何这里一定要h<n/3呢？

我发现等于也是ok的，性能无差异；

写回答

1回答

liuyubobobo

2016-11-02

已采纳

比如n=12的时候。

按照h<n/3的逻辑，最终求出来的h=4

按照h<=n/3的逻辑，最终求出来的h=13

h是后续排序Shell Sort的初始“步长”，显然对于有n=12个元素的数组来说，初始步长为4更合理。

不过你的逻辑求出来初始h=13并不影响算法的正确性。在下面的排序while循环中，h=13意味第一次循环什么都不需要做（for循环中i=h起始，已经小于n了）。之后h/=3以后，h变成了4，开始了真正的Shell Sort的过程。这一个额外的动作时间复杂度为O(1)，对整体算法的性能是没有影响的。

LeeDada

非常感谢。：-），解释的非常清楚。

2016-11-03

共1条回复

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

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

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1