2-7中的shell排序，h最大的边界n/3是怎么确定的？

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

Penguinbupt

2017-04-06

你的思路是h从1开始，按照h=3h+1的公式来进行找到最大的h 。这个h=3h+1的公式这个我懂，是现在解决不了的，我不是问这个。

那问题是最大的h的边界是怎么控制的？为啥是n/3？？？

最大的h为n/3的话，那么会有每一组会有3个数字吗？

下面是shell排序的部分代码

while( h < n/3 )

h = 3 * h + 1;

写回答

1回答

liuyubobobo

2017-04-08

我不确定自己是不是准确理解了你的问题。看看我这么解释你是否可以理解：

在这里，我在尝试寻找1，4，13，40... 3*x+1这样的序列中，不超过n且最接近n的那个值。在这种情况下，只要h小于n/3，那么我们就有空间使用3*h+1找到一个这个序列中的更接近n的一个值。

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

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

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 3