1,4,13,40,121...((3 * n) + 1) 在将随机数插入到排序算法。
这是为什么？与线程有关吗？
谢谢。
最佳答案
众所周知，2^k、2^(k-1)、...、1 的 shell 排序增量步长是最差的步长之一。例如，您只比较奇数位置的元素，仅在最后一步比较偶数位置的元素!
其他步骤似乎是 (3^k -1)/2(而不是 3n+1)并且不会遇到诸如偶数/奇数问题之类的问题。这不是证明，但我们可能希望这比 2 的幂更好。
如果您正在寻找数学分析，众所周知，Shell 排序会给数学家带来困难。
我没有在 Sedgewick 的论文 here 中找到对您的序列的任何分析.也许 Knuth 的一本书中有它。
祝你好运。
顺便说一句，你为什么要问线程？
关于algorithm - 为什么序列 1,4,13,40,121... 在插入排序时比 1,2,4,8,16... 更有效？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5481531/