如何在选择和插入排序中计算比较

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--;
   }
   }
 }

其中accounter是一个静态类变量。当我使用一个由1000个元素组成的字符串数组进行测试时，我得到了239507的值。然而，当我用一个顺序正确的字符串数组进行测试时，我得到的值为零，我知道这是不正确的，因为最佳情况下的性能是n项的n个比较。我想知道我的方法是否写错了，或者计数器是否放错了

Answer 1

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

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

Answer 2

每次执行内部循环时递增计数器，并在递增计数器后进行比较

public static void  iSort(String[] array)
{
  int i, j, k,ccounter=0;
  String temp; 
  for(i = 1; i<array.length; i++)
  {
        k=i;
        for(j = k-1; j>=0; j--)
        {
                 ccounter++; //increment counter for every execution of inner loop
                 //better to do integer comparison than string comparison
                 if(Integer.parseInt(array[j]) <= Integer.parseInt(array[k]))
                 {
                     break;
                 }
                 temp = array[j];
                 array[j] = array[k];
                 array[k] = temp;
                 k--;
        }
   }
}