关于shell 排序中的h = 3 * h + 1;

Question

请问老师，h = 3 * h + 1 这个获取分割值的算法的设计灵感来源于哪儿呢？
谢谢

Answer 1

liuyubobobo 2017-03-05 22:01:42

哈哈，这个问题很好，其实我也不知道= =

Shell Sort的效率，和h的这个序列非常相关。这个序列被称为increment sequence。不同的increment sequence，会让Shell Sort的效率产生影响。h = 3h+1这个式子是一个很经典的实现，因为它非常简单，方便记忆，同时兼顾了效率。我们可以将它理解成哈希表中的哈希函数（如字符串的哈希函数），设计这个函数本身已经一定程度超出了我们工程师学习算法的范畴了。这部分研究涉及了很多数学上的论证，我们主要是记住并应用它。

回到Shell Sort中，关于这个increment sequence，有很多Shell Sort的相关论文，描述的就是设计不同的increment sequence，看其对效率产生的影响。有兴趣可以找来看看。但是很有可能，效率最高的increment sequence到现在还没被发现哦：）