java - 如何计算选择排序和插入排序中的比较次数？

Question

我正在写两种不同的类型，一种是选择，另一种是插入。以下是我的插入排序方法

public static void  iSort(String[] array)
{
  int i, j, k;
  String temp; 
  for(i = 1; i<array.length; i++)
  {
   k=i;
   for(j = k-1; j>=0 && array[j].compareTo(array[k])>0; j--)
   {
    ccounter++;
     temp = array[j];
     array[j] = array[k];
     array[k] = temp;
     k--;
   }
   }
 }

其中 ccounter 是静态类变量。当我使用 1000 个元素的字符串数组对此进行测试时，我得到的值为 239507。但是，当我使用正确排序的字符串数组进行测试时，我得到的值为零，我知道这是不正确的，因为最好的情况性能是对 n 项进行 n 次比较。不知道是不是我的方法写错了，还是计数器放错了

Answer 1

问题是，如果您因为 compareTo() 返回 false 而退出循环，则您不会计算最终的比较。

如果我写这个，我会将比较代码包装在一个函数中，该函数将调用 compareTo() 并递增计数器。然后我将专门使用这个包装函数来进行所有比较。这样就不会出现错误计数的情况。