java - Shell 排序最坏情况时间复杂度

Question

我想通过这段 shell 排序代码了解最坏情况分析。你们能帮我找出答案吗？ while 循环将执行 O(log n) 次和 for 循环 O( n) 次；那么复杂度是如何变成 O(n^2) 的呢？一个完整的答案将不胜感激；我已经坚持这一天了。

int i, n = a.length, diff = n/2, interchange, temp;
while (diff > 0) 
{ 
  interchange=0;
  for (i = 0; i < n - diff; i++) 
  {
    if (a[i] > a[i + diff]) 
    { 
      temp = a[i];
      a[i] = a[i + diff];
      a[i + diff] = temp;
      interchange = 1;
    }
  }

  if (interchange == 0) 
  {
    diff = diff/2;
  }
}

Answer 1

您的算法不是 shell 排序。 Shell 排序通过多次执行基本的冒泡排序来工作。每次，您只考虑它们之间有 k 个元素间隙的元素。 k 由以 1 结尾的递减序列给出。您的序列是 n/2、n/4、n/8、...、1，这很好。但是您并没有对该序列的每个成员执行冒泡排序；你只执行一次传球，这是不够的。 O(n^2) 的最坏情况复杂度是由于冒泡排序。

请注意，在您的情况下，由于序列的长度不是恒定的，如果您修复算法，最坏情况下的复杂度将是 O(n^2 * logn)。

有关该算法的更多详细信息，wikipedia是你的 friend 。

稍后编辑:

修改后的代码是:

int i,n=a.length,diff=n/2,interchange,temp;
 while(diff>0) { 
 interchange=0;
 for(i=diff; i<n;i++) {
    temp=a[i];
    for (j = i; j >= gap && a[j-gap] > temp; j -= gap)
      a[j] = a[j-gap];  
    a[j]=temp;
  }
  diff=diff/2;
 }

请注意，我没有检查它，所以我可能是错的。现在，您能看到复杂度为 O(n^2) 的嵌套 for 循环吗？