1

我有两种不同类型的两种实现，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

我确信我传递给方法的数组是完全相同的，而且它们是非常随机的。

4

1 回答 1

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)) {

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

于 2013-05-11T21:13:04.693 回答