0

標準の間隔サイズを使用している場合と、非標準のサイズを使用している場合のシェルソートの効率をテストする必要があります。私が遭遇している問題は、非標準の間隔を使用しようとしたときです。

これは、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];              

        }

      }

リアルタイム効率に基づいて 2 つを比較しようとしていますが、このプリム間隔を機能させる方法がわかりません。

私はテストしようとしています:

  • Shellsort は、適切に選択された間隔サイズで O(N^2) よりも優れたパフォーマンスを発揮します
  • 選択された一連の間隔サイズは、O(N^2) ランタイムよりも優れたものを達成するために重要です

助けてくれてありがとう。

4

1 に答える 1

0

おそらくcount、外側のループの各反復での値をデクリメントする必要があります。あなたのコードでは、それはまだthis.h.length-111です。したがって、外側のループを繰り返すたびにif条件count-1 > 0が満たされるので、を設定h = this.h[count-1]します。これは2503だと思います。したがって、ループに再び入ります。

ちなみに、間隔サイズのリストを呼び出すと、h読みやすさが大幅に妨げられます。少なくともそれを呼び出す必要がありますhs。

于 2011-05-06T11:21:27.727 に答える