Java插入排序: Counting Data Comparisons

Question

我正在尝试使用 Java 为该插入排序算法的数据比较次数和数据交换次数放置一个计数器。虽然我相信计数器 swapsNo 放置正确，但 compsNo 没有给我预期的输出(均初始化为零)。我最初将其放置在当前用于在 compElem 与列表项进行比较的情况下进行计数的位置，但显然这只是增加了列表中每个项目的计数器。我想知道计数器是否应该在算法中或完全在其他地方出现两次。

public void insertionSort(T[] list, int length)
{
 for (int firstOutOfOrder = 1; firstOutOfOrder < length;
                               firstOutOfOrder ++)
 {
     Comparable<T> compElem =
               (Comparable<T>) list[firstOutOfOrder];
     compsNo++;

     if (compElem.compareTo(list[firstOutOfOrder - 1]) < 0)
     {
         Comparable<T> temp =
                     (Comparable<T>) list[firstOutOfOrder];
         //or perhaps compsNo++; should go here??
         int location = firstOutOfOrder;

         do
         {
             list[location] = list[location - 1];
             location--;
             swapsNo++;

         }
         while (location > 0 &&
                temp.compareTo(list[location - 1]) < 0);

         list[location] = (T) temp;

     }
   }
 }

更新:我在 while 循环(以前为 doWhile)内添加了 compsNo++ 的增量，并在 if 语句内添加了 swapsNo++ 的增量。这已接近预期输出，但我对自己的编辑还没有信心。

public void insertionSort(T[] list, int length)
{
 for (int firstOutOfOrder = 1; firstOutOfOrder < length;
                               firstOutOfOrder ++)

 {
     Comparable<T> compElem =
               (Comparable<T>) list[firstOutOfOrder];
     compsNo++;
     if (compElem.compareTo(list[firstOutOfOrder - 1]) < 0)
     {
         Comparable<T> temp =
                     (Comparable<T>) list[firstOutOfOrder];

         int location = firstOutOfOrder;



         while (location > 0 && temp.compareTo(list[location - 1]) < 0)
         {
             compsNo++;

             list[location] = list[location - 1];
             location--;
             swapsNo++;
         }




         list[location] = (T) temp;
         swapsNo++;
     }
  }
}

Answer 1

如果您想对比较进行计数，则应在包含 compareTo 调用的每一行之后或之前增加 compsNo。

在您的代码中，有两次 compareTo 调用，并且只有一次 compsNo++。