Shell排序间隔问题Java

Question

当我使用标准间隔大小时，以及在使用非标准大小时，我需要测试while排序的效率。我遇到的问题是当我试图使用我的非标准间隔。

当h等于标准间隔大小时，这是我的Shellsort：

    public void shellSort() 
    {
    int inner, outer;
    int temp;
    int h = 1;

    while (h <= length / 3)
    {
      h = h * 3 + 1; 
    }

    while (h > 0) 
    {

      for (outer = h; outer < length; outer++) 
      {
        temp = data[outer];
        inner = outer;

        while (inner > h - 1 && data[inner - h] >= temp) 
        {
          data[inner] = data[inner - h];
          inner -= h;
        }
        data[inner] = temp;
      }

      h = (h - 1) / 3; 

    }

  }

下面是我使用素数间隔的尝试

      private int[]  primes = {0, 1, 3, 7, 13, 31, 97, 211, 503, 1013, 2503, 5171};
      public void shellSort() 
      {
        int inner, outer;
        int temp;
        int count = this.h.length - 1;
        int h = 1;

        h = primes[primes.length - 1] * 2 > length ? primes[primes.length - 1] : primes[primes.length - 2];

        while (h > 0) 
        {         
          for (outer = h; outer < length; outer++) 
          {
            temp = data[outer];
            inner = outer;

            while (inner > h - 1 && data[inner - h] >= temp) 
            {
              data[inner] = data[inner - h];
              inner -= h;
            }
            data[inner] = temp;
          }

          if(count - 1 > 0)           
              h = primes[count - 1];              

        }

      }

我试图比较这两种基于实时效率的方法，并且我不知道如何使这个最原始的间隔工作。

我试着测试：

• Shellsort性能优于O(N^2)和适当选择的区间大小
• 选择的区间大小序列对于实现比O(N^2)运行时

更好的性能非常重要

谢谢你的帮助。

Answer 1

您可能希望在外部循环的每次迭代中减少count的值。在您的代码中，它仍然是this.h.length-1，它是11。因此，在外部循环的每一次迭代之后，您都满足了if条件count-1 > 0，所以您设置了h = this.h[count-1]，我相信它是2503。所以，你重新进入循环。

顺便说一句，调用区间大小列表h会严重影响可读性。你至少应该叫它hs。