C++插入排序中的比较次数统计问题

你的问题出在while循环的条件判断中的比较操作没有被全部统计：当前代码仅在满足条件进入循环体时才计数一次比较，但实际上每次判断numbers[j] < numbers[j-1]的时候，不管结果是真还是假，这都是一次有效的比较操作，需要被统计。

修正思路 #

把while循环的条件拆分开：先判断j>0，然后每次执行numbers[j]和numbers[j-1]的比较时，先给comparisons加1，再根据比较结果决定是否交换或退出循环。这样无论是否发生交换，每一次元素大小比较都会被计数。

修正后的代码 #

int swaps = 0;
int comparisons = 0;

void InsertionSort(int numbers[], int size) {
    int i;
    int j;
    for (i = 1; i < size; ++i) {
        j = i;
        while (j > 0) {
            comparisons++; // 每次比较前先计数
            if (numbers[j] < numbers[j - 1]) {
                Swap(numbers, j, j - 1);
                swaps += 1;
                j--; 
            } else {
                break; // 元素已处于正确位置，退出循环
            }
        }
        PrintNums(numbers, size); 
    }   
}

说明 #

• 每次进入while(j>0)循环后，都会执行一次numbers[j]和numbers[j-1]的比较，因此先给comparisons加1，确保所有比较操作都被统计。
• 如果当前元素小于前一个元素，执行交换并移动指针；如果大于等于，说明当前元素已经在正确的插入位置，直接退出循环，避免无效的比较。

内容的提问来源于stack exchange，提问作者user23998448