最快的空位序列用于壳排序? [英] Fastest gap sequence for shell sort?

问题描述

根据Marcin Ciura的壳排序算法的最佳(最佳已知)增量序列，shellsort的最佳顺序是1，4，10，23，57，132，301，701 ...，但是如何生成这样的序列呢?在Marcin Ciura的论文中，他说:

According to Marcin Ciura's Optimal (best known) sequence of increments for shell sort algorithm, the best sequence for shellsort is 1, 4, 10, 23, 57, 132, 301, 701..., but how can I generate such a sequence? In Marcin Ciura's paper, he said:

Knuth和Hibbard的序列相对较差，因为它们由简单的线性递归定义.

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

但是我发现大多数算法书都倾向于使用Knuth的序列:k = 3k + 1，因为它很容易生成.您如何生成shellsort序列?

but most algorithm books I found tend to use Knuth’s sequence: k = 3k + 1, because it's easy to generate. What's your way of generating a shellsort sequence?

推荐答案

如果数据集的大小上限是确定的，则可以对步骤序列进行硬编码.如果您的数据集可能会增长而没有上限，那么您应该只担心普遍性.

If your data set has a definite upper bound in size, then you can hardcode the step sequence. You should probably only worry about generality if your data set is likely to grow without an upper bound.

显示的序列似乎呈指数级增长，尽管有古怪之处.质数似乎占多数，但也有非质数.我没有看到明显的生成公式.

The sequence shown seems to grow roughly as an exponential series, albeit with quirks. There seems to be a majority of prime numbers, but with non-primes in the mix as well. I don't see an obvious generation formula.

一个有效的问题是，假设您必须处理任意大的集合，那么您是否需要强调最坏情况的性能，平均情况的性能或几乎排序的性能.如果是后者，则可能会发现使用二进制搜索插入步骤的普通插入排序可能比shellsort更好.如果需要良好的最坏情况下的性能，那么Sedgewick的顺序似乎会受到青睐.您提到的序列针对平均情况的性能进行了优化，在这种情况下，比较的数量大于移动的数量.

A valid question, assuming you must deal with arbitrarily large sets, is whether you need to emphasise worst-case performance, average-case performance, or almost-sorted performance. If the latter, you may find that a plain insertion sort using a binary search for the insertion step might be better than a shellsort. If you need good worst-case performance, then Sedgewick's sequence appears to be favoured. The sequence you mention is optimised for average-case performance, where the number of comparisons outweighs the number of moves.

这篇关于最快的空位序列用于壳排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！