插入排序比较计数异常求助：输入用例得15次而非预期13次

嘿，我帮你梳理下这个计数问题的根源，咱们一步步来：

首先，先把你的代码贴出来方便分析：

comparecount=0;
for(int i = 1; i < tab.length; i++) {
    comparecount++; 
    for(int j = i; j > 0; j--) {
        //comparecount++; 
        if(tab[j]<tab[j-1]) {
            comparecount++; 
            swap(tab,j,j-1);
            adjustcount+=3;
        }
    }
}

问题出在哪？ #

你的计数逻辑有两个关键错误：

1. 多余的外层计数：外层循环开头的comparecount++;完全没必要——这行代码不是在统计比较操作，而是每轮i循环就加1，平白多了5次计数（因为输入序列长度为6，i从1到5共5轮）。
2. 遗漏了不交换的比较：你只在tab[j]<tab[j-1]（需要交换）的时候才计数，但插入排序中，只要进行了tab[j]和tab[j-1]的比较，不管是否交换，都应该算一次比较。比如当tab[j] >= tab[j-1]时，这次比较已经发生了，但你没统计进去。

手动验证对比 #

咱们拿输入序列8 5 6 1 7 2手动模拟正确的比较次数：

• i=1（元素5）：和8比较1次 → 累计1
• i=2（元素6）：和8比较1次，和5比较1次 → 累计3
• i=3（元素1）：和8、6、5各比较1次 → 累计6
• i=4（元素7）：和8比较1次，和6比较1次 → 累计8
• i=5（元素2）：和8、7、6、5、1各比较1次 → 累计13

而你的代码计数逻辑：

• 外层加了5次，加上if条件满足时的10次（i=1:1、i=2:1、i=3:3、i=4:1、i=5:4），总共15次，正好和你得到的结果一致。

修复方案 #

调整计数的位置，确保每一次实际的比较都被统计：

comparecount=0;
for(int i = 1; i < tab.length; i++) {
    for(int j = i; j > 0; j--) {
        comparecount++; // 每次比较都计数，不管是否交换
        if(tab[j]<tab[j-1]) {
            swap(tab,j,j-1);
            adjustcount+=3;
        }
        // 补充：如果是优化版插入排序，这里可以加break，找到合适位置就停止循环，避免无用比较
        // else {
        //     break;
        // }
    }
}

修改后，每轮j循环里的比较都会被统计，去掉了多余的外层计数，就能得到预期的13次比较啦。

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