java - 计算用于整数数组的希尔排序中的数组操作

Question

我正在尝试计算在接受整数数组的 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++ ，但这里的数字要低得多。

Answer 1

试试这个:

.....
T temp = a[p];
numComp++;
boolean in = false;
while (p >= gap && a[p - gap].compareTo(temp) > 0) {
    if(in) numComp++;
    in = true;
    numAsgn++;
    a[p] = a[p - gap];
    p -= gap;
}
.....

关键是不要将外部比较计算两次。

然后是部分:

if (gap % 2 == 0) {
    ++gap;
}

这里似乎是错误的并且没有必要，只需将其删除即可。

完整代码为:

public static <T extends Comparable<? super T>> void shellSort(T[] a) {
    int gap = a.length / 2;
    int numAsgn = 0, numComp = 0;
    while (gap >= 1) {
        for (int i = gap; i < a.length; ++i) {
            int p = i;
            numAsgn++;
            T temp = a[p];
            numComp++;
            boolean in = false;
            while (p >= gap && a[p - gap].compareTo(temp) > 0) {
                if (in)
                    numComp++;
                in = true;
                numAsgn++;
                a[p] = a[p - gap];
                p -= gap;
            }
            numAsgn++;
            a[p] = temp;
        }
        gap /= 2;
    }
    System.out.println(numComp + "," + numAsgn);
}