InsertionSort與ShellSort的差距大小= 1？

Question

我有兩種不同的排序，InsertionSort和ShellSort。

它們分別是：

插入排序：

for (int pos = 0; pos < arrayToBeSorted.length; pos++) { 
    for (int secondMarker = pos; secondMarker > 0; secondMarker--) { 
     int currentValue = arrayToBeSorted[secondMarker]; 
     int valueBeingCheckedAgainst = arrayToBeSorted[secondMarker - 1]; 
     if (currentValue > valueBeingCheckedAgainst) { 
      break; 
     } 
     arrayToBeSorted[secondMarker] = arrayToBeSorted[secondMarker - 1]; 
     arrayToBeSorted[secondMarker - 1] = currentValue; 
    } 
} 

希爾排序：

for (int gap = a.length/a.length; gap > 0; gap = (gap/2)) { 
    for (int i = gap; i < a.length; i++) { 
     int tmp = a[i]; 
     int j = i; 
     for (; j >= gap && tmp < (a[j - gap]); j -= gap) { 
      a[j] = a[j - gap]; 
     } 
     a[j] = tmp; 
    } 
} 

我也有10陣列持有32000個整數整數。在我在這些類中調用靜態sortArray方法之前，我會獲得時間。下面是結果：

對於InsertionSort.sortArray：

Solving array with: 32000 elements. 
Time in milliseconds:264 
Time in milliseconds:271 
Time in milliseconds:268 
Time in milliseconds:263 
Time in milliseconds:259 
Time in milliseconds:257 
Time in milliseconds:258 
Time in milliseconds:260 
Time in milliseconds:259 
Time in milliseconds:261 

而對於希爾排序：

Solving array with: 32000 elements. 
Time in milliseconds:357 
Time in milliseconds:337 
Time in milliseconds:167 
Time in milliseconds:168 
Time in milliseconds:165 
Time in milliseconds:168 
Time in milliseconds:167 
Time in milliseconds:167 
Time in milliseconds:166 
Time in milliseconds:167 

那麼如何來他們之間有如此大的差別？他們基本上是相同的算法？

另外，ShellSort的前2次運行需要更長時間，但其餘的更快？

這是128000元，插入排序第一次結果：

Solving array with: 128000 elements. 
Time in milliseconds:4292 
Time in milliseconds:4267 
Time in milliseconds:4241 
Time in milliseconds:4252 
Time in milliseconds:4253 
Time in milliseconds:4248 
Time in milliseconds:4261 
Time in milliseconds:4260 
Time in milliseconds:4333 
Time in milliseconds:4261 

希爾排序：

Solving array with: 128000 elements. 
Time in milliseconds:5358 
Time in milliseconds:5335 
Time in milliseconds:2676 
Time in milliseconds:2656 
Time in milliseconds:2662 
Time in milliseconds:2654 
Time in milliseconds:2661 
Time in milliseconds:2656 
Time in milliseconds:2660 
Time in milliseconds:2673 

我可以肯定的是，陣列我傳遞的方法是完全一樣的，並他們很隨意。

Answer 1

在你插入排序，你正在被越來越複雜，

for (int pos = 0; pos < arrayToBeSorted.length; pos++) { 
    for (int secondMarker = pos; secondMarker > 0; secondMarker--) { 
     int currentValue = arrayToBeSorted[secondMarker]; 
     int valueBeingCheckedAgainst = arrayToBeSorted[secondMarker - 1]; 
     if (currentValue > valueBeingCheckedAgainst) { 
      break; 
     } 
     arrayToBeSorted[secondMarker] = arrayToBeSorted[secondMarker - 1]; 
     arrayToBeSorted[secondMarker - 1] = currentValue; 
    } 
} 

您閱讀在內部循環數組的值，而在前面的位置值不小，你寫兩個值給數組。

在希爾排序，

for (int i = gap; i < a.length; i++) { 
    int tmp = a[i]; 
    int j = i; 
    for (; j >= gap && tmp < (a[j - gap]); j -= gap) { 
     a[j] = a[j - gap]; 
    } 
    a[j] = tmp; 
} 

你讀的值被放置一次，內環以外，只有在內部循環體單寫，寫的值只有一次後內部循環。

這樣更有效率，因此殼排序更快是可以理解的。這兩個第一外殼各種速度較慢可能是因爲包裝

for (int gap = a.length/a.length; gap > 0; gap = (gap/2)) { 

混淆了JIT一會兒它注意到gap可以用1代替，包裝循環消除之前。