比较次数和物品移动次数

Question

Im使用c++并且正在使用插入排序

在插入排序算法中，我们应该放置一个计数器来监视项目移动的数量和项目比较的数量。我已经在下面添加了我的设置

void InsertionSort::insertion_sort()
{
    int key,i,count = 0;
for(int j=1;j<10;j++)
 {
    key=Arr1[j];
    i=j-1;
    while(Arr1[i]>key && i>=0)
    {
     Arr1[i+1]=Arr1[i];
     i--;
     numberOfItemMovements++;
    }
    Arr1[i+1]=key;
}
}
}

正如你所看到的，我似乎不知道比较计数器应该放在哪里，尽管物品移动计数器很好，并且工作正常。谢谢

Answer 1

实现这一点的一种方法是在循环中使用numberOfComparisons。

while(++numberOfComparisons && Arr1[i]>key && i>=0)
{
    Arr1[i+1]=Arr1[i];
    numberOfItemMovements++;
    i--;
}

1)您是否理解为什么在while循环中可以使用++numberOfComparisons，但numberOfComparisons++却会失败？

2)你有一个问题，Arr1-1可能会被求值。你能找出这是在哪里发生的吗?你能改变你的代码来修复它吗？

Answer 2

移动计数器确实是正确的。

为了实现比较计数器，您需要稍微重新构造代码。特别是，您需要能够区分Arr1[i]>key和i>=0，因为它们中的一个需要比较，而另一个则不需要。

既然这看起来像家庭作业，剩下的就留给你自己解决吧。