我正在尝试计算 Shell sort 对数组进行排序所需的比较和交换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;
}
}