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] 的问题。您能找出发生这种情况的地方以及如何更改代码来修复它吗？