InsertionSort和ShellSort的间隙大小= 1？

Question

我有两种不同类型的实现，InsertionSort和ShellSort。

它们如下：

InsertionSort：

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

ShellSort：

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

对于ShellSort：

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元素的结果，首先是InsertionSort：

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

ShellSort：

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

您只读取一次要放置在内环之外的值，并且只在内环体中进行一次写入，只在内环之后写入值一次。

这更有效率，因此可以理解shell排序更快。两个第一个shell排序比较慢，这可能是因为

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

在JIT注意到可以用1替换gap并消除包装循环之前，对JIT进行了一段时间的混淆。