shell排序最快的间隔序列？

据马尔钦Ciura的Optimal (best known) sequence of increments for shell sort algorithm，为希尔排序的最佳顺序是1，4，10，23，57，132，301，701 ...，但我怎么能产生这样的序列？在马辛Ciura的论文，他说：shell排序最快的间隔序列？

无论是Knuth和希巴德的序列都比较糟糕，因为他们是通过简单的线性递推定义。

但我发现的大多数算法书都倾向于使用Knuth的序列：k = 3k + 1，因为它很容易生成。你如何生成贝壳序列？

来源

2010-03-29 Sawyer

有人挖出了我的序列:-)我在一个数据集上实现了一个排序算法，它的大小非常有限 - 大约是10到50，我发现shellsort是这个范围中最快的一个。我彻底搜索了最好的序列 - 主要发现了Knuths，Sedgewicks等，其中主要基于voodoo和kumba wamba。 Marcin Ciuara似乎是为数不多的基于魔术公式的人，他们实际上做了一些基准测试，并获得了比序列更好的东西，这是我将其发布在OEIS上的主要原因。但我没有给你答案。 – hirschhornsalz 2010-03-29 17:08:05

序列应严格减少，其最后一个元素始终为1.如果gap为1，则表示经典插入排序。所以Ciura的序列正确的是[701,301,132,57,23,10,4,1]。我做了一些测试，壳牌的原始序列对我来说表现更好。 – Jabba 2012-02-28 17:31:26

您提供的链接已损坏。 _“平均壳数最佳增量”_：[abstract]（http://www.springerlink.com/content/2akgu9pvc6jl239g/）和[full paper]（http://sun.aei.polsl.pl/ 〜mciura/publikacje/shellsort.pdf） – user46874 2012-07-22 23:54:43

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

显示的序列似乎粗略地增长为一个指数序列，虽然有怪癖。似乎有大部分素数，但也有非素数。我没有看到明显的世代公式。

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

来源

2010-04-03 06:28:34 Chromatix

在给出O（n * log（n））最好的情况下，Sedgewick的东西是不是O（N ^（4/3））？我的意思是有更快的O（n * log^2（n））最坏的情况下序列，但最糟糕的情况是... – Ivan 2017-06-21 13:38:46

Ciura的论文以经验的方式产生序列 - 也就是说，他尝试了一系列组合，这是最好的。生成一个最佳的shellort序列已被证明是棘手的，并且迄今为止这个问题已经抵抗分析。

最着名的增量是Sedgewick's，您可以阅读大约here（参见第7页）。

来源

2010-03-29 16:30:40

我不会感到羞愧采取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 = 2.25h'k-1， 1 + 1，h'1 = 1，可推荐用于的实际应用。

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

来源

2011-12-27 23:09:33 u0b34a0f6ae

该序列是1,4,10,23,57,132,301,701,1750.对于1750后的每个下一个数字，将前一个数字乘以2.25并向下舍入。

来源

2015-10-24 12:12:12

不，不！很明显，它会失败4,10,23 ... – Enissay 2016-02-09 11:35:12

增加“1750年后”。现在是否正确？ – 2016-04-05 15:43:40

我发现这个序列相似马尔钦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 也许这个协会降低可以提高希尔排序在将来。

来源

2017-09-08 14:56:13

shell排序最快的间隔序列？

回答

相关问题