正确计算插入排序比较的次数

Question

int comparisons = 0;
for (int i = 1; i < input.length; i++) {
  int j = i;
  while (j > 0 && comp.compare(input[j - 1], input[j]) > 0) {
    if (comp.compare(input[j - 1], input[j]) > 0)
      comparisons++;
    E temp = input[j - 1];
    input[j - 1] = input[j];
    input[j] = temp;
    j--;
  }
  comparisons++;
}

我正在尝试计算插入排序中的比较次数。但是，我的比较与预期的 JUnit 值不正确。

正在输入： { 9, 5, 6, 7, 2, 8 } 期望：11 但实际是 13

正在输入： {“如何”，“关于”，“dey”，“da”，“熊”};期望：7 但实际是 8

测试输入的预期值是否不正确，或者我是否遗漏了一些极端情况？

Answer 1

即使条件为假且命令为：comparisons++

，也会进行比较

只有当它为真时才会发生 ;)

正确计算插入排序比较的次数

properly count the number of insertion sort comparisons

java

time-complexity

insertion-sort