我的Shell排序程序中的比较和交换计数

Question

我正在尝试计算比较和Shell排序将数字数组int[] array = {1,2,3,4,5,6,7,8,9,10}排序所需的交换。现在比较计数器在[comp），交换计数器在[exch），我得到22个比较，零交换。我认为零交换是正确的，因为它显然是一个有序数组，因此不需要交换。对于由10个元素组成的数组，我不认为22个比较是正确的。有人可以告诉我这些表达方式在哪里，并解释原因吗？我将不胜感激。

public static void shellSort(int[] array) {
    int interval = array.length / 2;
    int comp = 0, exch = 0;
    while (interval != 0) {
        for (int i = 0; i < interval; i++) {
            for (int p = i + interval; p < array.length; p += interval) {
                int key = array[p];
                int j = p - interval;
                while (j >= 0) {
                    comp++;         //Comparison here
                    if (key < array[j]) {
                        array[j + interval] = array[j];
                    } else
                        break;
                    exch++;     //Exchange here
                    j -= interval;
                }
                array[j + interval] = key;
            }
        }
        interval /= 2;
    }
}

Answer 1

来自the theory：

1. 有间隙5（10 >>> 1）：

   {1,6}{2,7}{3,8}{4,9}{5,10}
     ^    ^    ^    ^    ^    --> 5 comparisons
   

2. 有间隙2（5 >>> 1）：

   {1,3,5,7,9}{2,4,6,8,10}
     ^ ^ ^ ^    ^ ^ ^ ^    --> 8 comparisons
   

3. 有间隙1（2 >>> 1）：

   {1,2,3,4,5,6,7,8,9,10}
     ^ ^ ^ ^ ^ ^ ^ ^ ^    --> 9 comparisons
   

总计：22个比较。哪里出问题了？ ：）