algorithm - 希尔排序在预排序列表上的运行时间(最佳情况)

Question

如果列表是预先排序的(最好的情况)，我对 shell 排序的运行时间感到困惑。是 O(n) 还是 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(a[j-k]>a[j]) swap
              else break;

Shell排序是基于插入排序的，插入排序对于预排序列表的运行时间是O(n)，但是，通过引入间隙(最外层循环)，不知道是否会让shell的运行时间缩短对预排序列表进行排序 O(n log n)。

感谢您的帮助

Answer 1

在最好的情况下，当数据已经排序时，最里面的循环永远不会交换。它总是会立即中断，因为已知左侧值小于右侧值:

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) 最佳情况。