c++ - 比较次数和项目移动次数

Question

我正在使用 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）你明白为什么++numberOfComparisons可以在while循环中使用但numberOfComparisons++会失败吗？

2) 你有一个问题，可以评估 Arr1[-1]。你能弄清楚这发生在哪里以及如何更改代码来修复它吗？

Answer 2

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

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

既然这看起来像家庭作业，我会把剩下的留给你去解决。