Java Shellsort区间问题

发布于 2024-11-05 03:18:51 字数 1717 浏览 3 评论 0原文

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

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

    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) 运行时间非常重要

谢谢您的帮助。

原文

I need to test the efficiency of shellsort when I am using the standard interval size and also while using a non-standard size. The problem I am encountering is when I try to use my non-standard interval.

This is my Shellsort when h is equal to the standard interval size:

    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; 

    }

  }

And here is my attempt at using a prime number interval

      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];              

        }

      }

I am trying to compare the two based off of real time efficiency , and I can't figure out how to get this prim interval to work.

I'm trying to test:

Shellsort performs better than O(N^2) with appropriately chosen interval sizes
The series of interval sizes chosen is important to achieving better than O(N^2) runtime

Thank you for any help.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

悟红尘 2024-11-12 03:18:51

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

顺便说一句，调用间隔大小列表 h 会严重影响可读性。您至少应该将其命名为 hs。