21

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

Knuth 和 Hibbard 的序列都比较差，因为它们是由简单的线性递归定义的。

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

4

6 回答 6

14

Ciura 的论文凭经验生成了序列——也就是说，他尝试了一堆组合，这是效果最好的一个。事实证明，生成一个最优的 shellsort 序列是很棘手的，而且这个问题迄今为止一直难以分析。

最著名的增量是 Sedgewick 的，您可以在此处阅读（参见第 7 页）。

于 2010-03-29T16:30:40.700 回答
6

如果您的数据集的大小有明确的上限，那么您可以对步骤序列进行硬编码。如果您的数据集可能在没有上限的情况下增长，您可能只应该担心一般性。

显示的序列似乎大致呈指数级增长，尽管有一些怪癖。似乎有大多数素数，但也有非素数。我没有看到明显的生成公式。

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

于 2010-04-03T06:28:34.880 回答
4

我不会羞于接受 Wikipedia 的Shellsort文章中给出的建议，

关于平均比较次数，最著名的缺口序列是 1、4、10、23、57、132、301、701 和类似的，通过实验发现缺口。超过 701 的最佳间隙仍然未知，但通过根据递归公式 h_k = \lfloor 2.25 h_{k-1} \rfloor 扩展上述序列可以获得良好的结果。

Tokuda 的序列 [1, 4, 9, 20, 46, 103, ...]，由简单公式 h_k = \lceil h'_k \rceil 定义，其中 h'k = 2.25h'k − 1 + 1, h '1 = 1，可推荐用于实际应用。

从笔名猜测，似乎 Marcin Ciura 自己编辑了 WP 文章。

于 2011-12-27T23:09:33.243 回答
2

序列是 1、4、10、23、57、132、301、701、1750。对于 1750 之后的每个下一个数字，将前一个数字乘以 2.25 并向下取整。

于 2015-10-24T12:12:12.943 回答
0

我发现这个序列类似于 Marcin Ciura 的序列：

1, 4, 9, 23, 57, 138, 326, 749, 1695, 3785, 8359, 18298, 39744, etc.

例如，Ciura 的序列是：

1, 4, 10, 23, 57, 132, 301, 701, 1750

这是素数的平均值。查找素数均值的 Python 代码在这里：

import numpy as np

def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
vectorized_isprime = np.vectorize(isprime)

a = np.arange(10000000)
primes = a[vectorized_isprime(a)]
#print(primes)
for i in range(2,20):
    print(primes[0:2**i].mean())

输出是：

4.25
9.625
23.8125
57.84375
138.953125
326.1015625
749.04296875
1695.60742188
3785.09082031
8359.52587891
18298.4733887
39744.887085
85764.6216431
184011.130096
392925.738174
835387.635033
1769455.40302
3735498.24225

序列中的差距正在从 2.5 慢慢减少到 2。也许这种关联可以在未来改进 Shellsort。

于 2017-09-08T14:56:13.067 回答
0

我昨天在这里讨论了这个问题，包括给定特定（低）n 时我发现的最佳工作间隙序列。

中间我写

shellsort 的一个令人讨厌的副作用是，当使用一组 n 个条目的随机组合（以节省处理/评估时间）来测试间隙时，您最终可能会得到 n 个条目的最佳间隙或您的集合的最佳间隙组合 - 很可能是后者。

问题在于测试提出的差距，以便得出有效的结论。显然，针对所有 n! 测试差距！一组 n 个唯一值可以表示为的排序是不可行的。例如，以这种方式对 n=16 进行测试意味着必须对 n 值的 20,922,789,888,000 个不同组合进行排序以确定准确的平均、最差和反向排序的情况——只是为了测试一组差距，而那一组可能不是最好的。n=16 可能有 2^(16-2) 组间隙，第一个是 {1}，最后一个是 {15,14,13,12,11,10,9,8,7,6,5,4 ,3,2,1}。

为了说明使用随机组合可能会产生不正确的结果，假设 n=3 可以假设六个不同的顺序 012、021、102、120、201 和 210。您生成一组两个随机序列来测试两个可能的间隙集，{1 } 和 {2,1}。假设这些序列是 021 和 201。对于 {1}，021 可以通过三个比较（02、21 和 01）进行排序，而 201 可以通过（20、21、01）进行排序，总共有六个比较，除以二瞧，平均值为 3，最坏情况为 3。使用 {2,1} 给出 021 的 (01, 02, 21 和 01) 和 201 的 (21, 10 和 12)。七次比较与最坏情况4，平均 3.5。{1] 的实际平均值和最差情况分别为 8/3 和 3。{2,1} 的值为 10/3 和 4。两种情况的平均值都太高，最坏的情况是正确的。

现在将其扩展为找到一组 n=16 的随机序列，这样与其他间隙相比，没有一组测试的间隙会受到青睐，并且结果接近（或等于）真实值，同时始终将处理保持在最低限度. 可以做到吗？可能。毕竟，一切皆有可能——但有可能吗？我认为对于这个问题，随机是错误的方法。根据某些系统选择序列可能不那么糟糕，甚至可能是好的。

于 2018-05-23T14:23:18.397 回答