1

在我的教科书Algorithms中，我读到：

没有关于随机排序输入的 shellsort 的平均比较次数的数学结果。已经设计了增量序列，驱动最坏情况下比较数的渐近增长到 N 4/3、N 5/4、N 6/5、...。. . , 但其中许多结果主要具有学术兴趣，因为对于 N 的实际值，这些函数很难相互区分（以及与 N 的常数因子）。

而且，在bigocheatsheet.com中，Shell 的时间复杂度排序为：

  • 最坏的情况下 ：O((nlog(n))^2)
  • 平均 ：O((nlog(n))^2)
  • 最好的情况： O(n)

而且，这是我对 shell 排序的实现：

/**
 * Java program to implement shell sort
 */
public class Solution
{
    private static final int arr[] = {2,5,4,3,7,8,9,1,6,6};
    public static void main(String[] args)
    {
        final int N = arr.length;
        int h = 1;
        while(h<(N/3))
            h = 3*h + 1;

        while(h>=1)
        {
            for(int i=h;i<N;i++)
            {
                for(int j=i;j>=h && (arr[j-h]>arr[j]);j-=h)
                {
                    int temp = arr[j-h];
                    arr[j-h] = arr[j];
                    arr[j] = temp;
                }
            }

            h=h/3;
        }

        for(int x:arr)
            System.out.println(x);
    }

}

现在的问题是，我无法理解 Shell 排序的最坏情况复杂性是如何产生的 O((nlog(n))^2)。如果我做错了什么，请纠正我。

4

0 回答 0