algorithm - shell排序的最快间隙序列？

Question

根据 Marcin Ciura 的 Optimal (best known) sequence of increments for shell sort algorithm ,shellsort 的最佳顺序是 1, 4, 10, 23, 57, 132, 301, 701...,但是我怎样才能生成这样的序列呢？在 Marcin Ciura 的论文中，他说:

Both Knuth’s and Hibbard’s sequences are relatively bad, because they are defined by simple linear recurrences.

但我找到的大多数算法书籍都倾向于使用 Knuth 序列:k = 3k + 1，因为它很容易生成。生成 shellsort 序列的方法是什么？

Answer 1

Ciura 的论文根据经验生成序列——也就是说，他尝试了一堆组合，这是效果最好的一个。生成最佳 shellsort 序列已被证明是棘手的，并且该问题迄今为止难以分析。

最著名的增量是 Sedgewick 的，您可以阅读 here (见第 7 页)。