java - InsertionSort 与间隙大小 = 1 的 ShellSort？

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

对于 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

壳排序:

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

你在内层循环中从数组中读取值，当前面位置的值不小于时，你将两个值写入数组。

在 shell 排序中，

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 注意到 gap 可以替换为 1 并消除包装循环之前，它会混淆一段时间。