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代替，包装循环消除之前。