1

如果我有一个数组 A = <0, 15, 5, 1, 0, 20, 25, 30, 35, 40>。当我编写代码来计算比较时，我对在哪里添加计数器感到困惑，因为我担心可能会重复计数。

尽管如此，它说有15个比较。我不确定这是否正确。真正的比较有多少？

int InsertionSort(int A[], int n)
{
   int i, j, index, counter = 0;

   for (i=1; i < n; i++)
   {
      index = A[i];
      for (j=i-1;j >= 0 && A[j] > index;j--)
      {
         A[j + 1] = A[j];
         counter++;
      }
      A[j+1] = index;
      counter++;
   }
   return counter;
}

int main()
{
    int A[]= {5,4,3,2,1};
    int counter = 0;
    int n =5;
    counter = InsertionSort(A, n);
    printf("%d",counter);

    return 0;
}
4

2 回答 2

4

有 15 个比较（和 6 个交换）：

compare: 0 <= 15, 5, 1, 0, 20, 25, 30, 35, 40
compare: 0, 15 > 5, 1, 0, 20, 25, 30, 35, 40
swap:    0, 5 - 15, 1, 0, 20, 25, 30, 35, 40
compare: 0 <= 5, 15, 1, 0, 20, 25, 30, 35, 40
compare: 0, 5, 15 > 1, 0, 20, 25, 30, 35, 40
swap:    0, 5, 1 - 15, 0, 20, 25, 30, 35, 40
compare: 0, 5 > 1, 15, 0, 20, 25, 30, 35, 40
swap:    0, 1 - 5, 15, 0, 20, 25, 30, 35, 40
compare: 0 <= 1, 5, 15, 0, 20, 25, 30, 35, 40
compare: 0, 1, 5, 15 > 0, 20, 25, 30, 35, 40
swap:    0, 1, 5, 0 - 15, 20, 25, 30, 35, 40
compare: 0, 1, 5 > 0, 15, 20, 25, 30, 35, 40
swap:    0, 1, 0 - 5, 15, 20, 25, 30, 35, 40
compare: 0, 1 > 0, 5, 15, 20, 25, 30, 35, 40
swap:    0, 0 - 1, 5, 15, 20, 25, 30, 35, 40
compare: 0 <= 0, 1, 5, 15, 20, 25, 30, 35, 40
compare: 0, 0, 1, 5, 15 <= 20, 25, 30, 35, 40
compare: 0, 0, 1, 5, 15, 20 <= 25, 30, 35, 40
compare: 0, 0, 1, 5, 15, 20, 25 <= 30, 35, 40
compare: 0, 0, 1, 5, 15, 20, 25, 30 <= 35, 40
compare: 0, 0, 1, 5, 15, 20, 25, 30, 35 <= 40
于 2012-10-14T23:34:18.043 回答
1

对我来说，您的柜台似乎在错误的位置。假设 A=<3, 2>，那么您的算法将使用 1 比较，但会报告 counter=2。如果 15 是正确答案，那么这个错误没有发生或以某种方式被取消。

要确定 15 是否真的是正确答案，这就是您可以改进计数器的方法。首先，您的算法依赖于从左到右的条件评估顺序（大多数编程语言都遵守）。这意味着如果 P=false 则 Q 不在 (P && Q) 中求值。如果不能保证从左到右的评估顺序，那么该算法可能会评估 A[-1] > index （这会使您的程序崩溃）。正确计数的最简单方法是将 for 循环的合取分成两行，如下所示：

for (i=1; i < n; i++)
{
   index = A[i];
   for (j=i-1; j >= 0; j--)
   {
      // Every time this line is reached, a comparison will be performed
      counter++;
      if (A[j] > index)
      {
         A[j + 1] = A[j];
      }
   }
   A[j+1] = index;
}

如果解决了，请让我们知道结果，并对此答案进行投票。

于 2012-10-18T12:07:13.587 回答