在我的壳牌排序程序中计算比较和交换

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

从理论上：

{1,2,3,4,5,6,7,8,9,10}

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 个比较。问题出在哪里？:)

更新

10,9,8,7,6,5,4,3,2,1

1. 带间隙5(10 >>> 1(：

   10,5  9,4  8,3  7,2  6,1
   ê    ê    ê    ê    ê  --> 5c, 5e
   

5,4,3,2,1,10,9,8,7,6

2. 带间隙2(5 >>> 1(：

   5,3,1,9,7
   5,3 
   ê        --> 1c, 1e --> 3,4,5,2,1,10,9,8,7,6
   3,5,1                    ‾   ‾
   ê ê      --> 2c, 2e --> 1,4,3,2,5,10,9,8,7,6
   1,3,5,9                  ‾   ‾   ‾
   ^    --> 1c
   1,3,5,9,7
   ^ ê  --> 2c, 1e --> 1,4,3,2,5,10,7,8,9,6
   ‾   ‾   
   4,2,10,8,6
   4,2
   ê         --> 1c, 1e --> 1,2,3,4,5,10,7,8,9,6
   2,4,10                      ‾   ‾
   ^       --> 1c
   2,4,10,8
   ^  ê    --> 2c, 1e --> 1,2,3,4,5,8,7,10,9,6
   2,4,8,10,6                          ‾   ‾‾
   ^ ê  ê  --> 3c, 2e --> 1,2,3,4,5,6,7,8,9,10
   ‾   ‾   ‾‾ 
   

3. 带间隙1(2 >>> 1(：

   1,2,3,4,5,6,7,8,9,10
   ^ ^ ^ ^ ^ ^ ^ ^ ^   --> 9c
   

我总共进行了27次比较和13次交流。

我很确定你现在能够自己进行最后一次纸笔测试。 :)