Shellsort間隔問題Java

我需要測試使用標準間隔大小時以及使用非標準大小時的shellort效率。我遇到的問題是當我嘗試使用我的非標準間隔時。Shellsort間隔問題Java

這是我的希爾排序當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];    

     } 

     }

我想比較兩個質數間隔嘗試基於實時效率，我無法弄清楚如何獲得這個原始間隔的工作。

我試圖測試：

希爾排序執行爲O更好（N^2）與適當選擇的間隔尺寸
選擇的一系列間隔的尺寸是實現爲O更好重要（N^2）運行時間

謝謝你的幫助。

來源

2011-05-04 Brendan

它有什麼問題？我認爲它沒有正確排序？或者你不知道如何計時？ – Casey 2011-05-04 20:33:21

我知道如何計時，它是將shellsort方法引入無限循環的間隔本身，或者它沒有正確排序。任何人都可以告訴我，黃金間隔計算是否正確？ – Brendan 2011-05-04 21:04:40

您可能希望在外循環的每次迭代中遞減count的值。在你的代碼中，它仍然是this.h.length-1，這是11.因此，在外部循環的每次迭代之後，你有if條件count-1 > 0滿足，所以你設置了h = this.h[count-1]，我相信它是2503.所以，你重新進入循環。

順便說一下，調用間隔大小列表h嚴重阻礙了可讀性。你應該至少叫它hs。

來源

2011-05-06 11:21:27 xofon

相信我，我從來沒有這樣想過。我只是憑經驗命名我的數據，從來沒有機會重新命名它。 – Brendan 2011-05-06 19:47:50

Shellsort間隔問題Java

回答

相關問題