根据 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 序列的方法是什么?
最佳答案
Ciura 的论文根据经验生成序列——也就是说,他尝试了一堆组合,这是效果最好的一个。生成最佳 shellsort 序列已被证明是棘手的,并且该问题迄今为止难以分析。
最著名的增量是 Sedgewick 的,您可以阅读 here (见第 7 页)。
关于algorithm - shell排序的最快间隙序列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2539545/