用于整数数组的Shell排序中的计数数组操作
用于整数数组的Shell排序中的计数数组操作
提问于 2018-06-10 00:10:57
我试图统计在我的接受Integer数组的Shell排序方法中发生的数组操作(传入/传出数组的赋值，以及与数组元素的比较)。
这是我的Shell排序使用的代码
public static <T extends Comparable<? super T>> void shellSort(T[] a) {
int gap = a.length / 2;
while (gap >= 1) {
if (gap % 2 == 0) {
++gap;
}
for (int i = gap; i < a.length; ++i) {
int p = i;
numAsgn++;
T temp = a[p];
numComp++;
while (p >= gap && a[p - gap].compareTo(temp) > 0) {
numAsgn++;
a[p] = a[p - gap];
p -= gap;
}
numAsgn++;
a[p] = temp;
}
if (tracing) {
System.out.println("...gap=" + gap + ": " + Arrays.toString(a));
}
gap /= 2;
}
}这就是我所期望的输出。
(注意:我正在对其他排序方法执行相同的操作，但这与我的问题无关)
我为shell排序得到的输出如下：
因此，我得出结论，我没有在某个地方更新numComp的值，但是我找不到它在我的代码中的位置。任何帮助都是非常感谢的。
此外，我尝试将计数更改为这种方式。但无济于事。
//numComp++;
while (p >= gap && a[p - gap].compareTo(temp) > 0) {
numComp++;
numAsgn++;
a[p] = a[p - gap];
p -= gap;
}我不明白这怎么可能，因为循环会多次更新numComp++，但这里的数字要低得多。
回答 1
Stack Overflow用户
发布于 2018-06-10 00:27:48
numComp++; // comparing perhaps more than once but only counted as once here
while (p >= gap && a[p - gap].compareTo(temp) > 0) { // this loop will result in multiple comparisons, is it not?
numAsgn++;
a[p] = a[p - gap];
p -= gap;
}由于需要一个直接的解决方案，那么我们分别记录内部比较，然后将其添加到总比较计数器中，如下所示：
numComp++; // for the loop termination comparison;
int innerComp = 0; // for the loop non-termination comparison;
while (p >= gap && a[p - gap].compareTo(temp) > 0) {
innerComp++;
numAsgn++;
a[p] = a[p - gap];
p -= gap;
}
numComp += innerComp;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50776170
复制相关文章
相似问题
腾讯云开发者
