在预先排序的列表（最好的情况下）上运行shell的排序时间

如果列表是预先排序的（最好的情况），我对shell排序的运行时间感到困惑。它是O（n）还是O（n log n）？在预先排序的列表（最好的情况下）上运行shell的排序时间

for(k=n/2; k>0; k/=2) 
     for(i=k; i<n; i++) 
      for(j=i;j>k; j-=k) 
       if(a[j-k]>a[j]) swap 
       else break;

Shell排序是基于插入排序，并插入排序为O（n）的运行时间为预排序的名单，但是，通过引入间隙（最外层循环），我不知道，如果它使对预先排序的列表进行shell排序O（n log n）的运行时间。

感谢对帮助

在当数据已经下令最好的情况下，最内层的循环将永不掉。它总是迅速打破，因为左值被称为是比右边的值：

for(k=n/2; k>0; k/=2) 
    for(i=k; i<n; i++) 
     for(j=i;j>k; j-=k) 
      if(false) swap 
      else break;

因此，该算法崩溃这样：

for(k=n/2; k>0; k/=2) 
    for(i=k; i<n; i++) 
     no_op()

最好的情况就变成了：

O((n - n/2) + (n - n/4) + (n - n/8) + ... + (n - 1)) 
= O(nlog(n) - n) 
= O(nlog(n))

也就是说，according to Wikipedia，壳牌排序的一些其他变种确实有O（N）最好的情况。

2012-02-16 23:17:26

我认为（至少在正常情况下）大概是O（n log n），尽管确切的数字取决于你使用的进程。

例如，在第一次迭代中，您可以调用插入排序，例如五次，每次排序每五个元素。由于每个元素的排序数量都是线性的，因此总体上会出现线性复杂性。

在下一次迭代中，您将调用插入排序，例如，两次排序每个其他元素。再次，线性整体。

第三，你对每个元素进行插入排序，再次是线性的。总之，你有一个线性算法调用了一个（大致）对数次数，所以它应该总体上是O（n log n）。这在你使用的步长中会呈现某种几何级数，这很常见，但也许并非绝对需要。

2012-02-16 23:20:59

最好的情况是O（n）。原因如下：

让我们从插入排序开始。已经排序的n个条目列表将需要n个减1个比较来完成（不需要交换）。

将插入排序放入带有单个增量1的shellort的上下文中。已经排序的n个条目列表将需要n减去间隙（1）。

假设您有两个空位5，其后是1，n大于5.已排序的列表将需要n-5个比较来处理第一个空位（不需要交换），再加上第二个或2n个n-1比较-6（不需要交换）。

如果您使用n作为输入来生成间隙，则无关紧要。最终每个差距都是一个常数值c（最终的c是1）。

因此，最佳情况下的算法是“n *个间隙 - 所有间隙的总和”。

我不明白“n *个空白......”可能是除O（n）之外的任何东西。

我知道大部分的讨论都把它当成别的东西，我觉得没人会坐下来做数学。正如你所看到的，这不是火箭科学。

2017-05-10 15:16:36

回答