为何选择/增强冒泡/插入排序的比较次数始终一致？技术问询

哥们儿，我太懂你这种困惑了——本来想对比三种排序的效率，结果每次跑出来比较次数都一模一样，肯定是哪里逻辑踩坑了！结合你描述的场景和代码片段，我帮你梳理几个最可能的原因：

最常见的坑：复用了同一个数组对象 #

你生成随机数组后，是不是直接把同一个数组传给了三个排序方法？比如：

int[] randomArr = generateRandomArray(testRuns[0]);
int selectionCount = selectionSort(randomArr);
int bubbleCount = enhancedBubbleSort(randomArr);
int insertionCount = insertionSort(randomArr);

这就大错特错了！排序算法都是原地修改数组的——第一个排序（比如选择排序）跑完后，数组已经变成完全有序的了。后面的冒泡和插入排序拿到的是已经排好的数组，这时候它们的比较次数会和对随机数组操作的情况完全不同。

但为什么三个次数会完全相同？大概率你的「增强冒泡排序」根本没做优化（比如没加标志位提前终止），还是普通冒泡排序——普通冒泡排序不管数组有序与否，比较次数都是固定的 n*(n-1)/2，和选择排序的比较次数一模一样。而如果你的插入排序统计逻辑也错了（比如把移动次数当成比较次数，或者没正确统计），就会出现三个次数完全相同的情况。

第二个可能：比较次数的计数器没做隔离/重置 #

如果你用了一个类级别的静态变量来统计比较次数（比如public static int comparisonCount;），那三个排序方法会共用这个计数器，而且每次排序后你没把它清零。比如第一个排序把计数器加到45，第二个排序继续累加，最后三个方法返回的都是同一个累计值，自然就相同了。

正确的做法是：每个排序方法内部用局部变量来统计比较次数，最后返回这个值，完全隔离各个算法的计数。比如选择排序的正确写法：

public static int selectionSort(int[] arr) {
    int comparisons = 0; // 局部计数器，每个排序调用都会重新初始化
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++; // 每次比较都计数
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 交换操作
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
    return comparisons;
}

第三个可能：排序算法的比较次数统计逻辑错误 #

比如：

• 你把交换次数当成了比较次数（选择排序交换次数少，但比较次数多，这就会导致统计值不对）；
• 增强冒泡排序的比较次数只在交换时计数，而忽略了那些没有交换但进行了比较的情况；
• 插入排序的统计逻辑写错了，比如没有在while循环的每次比较时计数。

解决方案 #

1. 为每个排序算法创建独立的数组副本：
   生成随机数组后，用Arrays.copyOf()复制出三个独立的数组，分别传给三个排序方法，保证每个算法都对初始随机数组操作：

   int[] originalArr = generateRandomArray(testRuns[0]);
   int[] selectionArr = Arrays.copyOf(originalArr, originalArr.length);
   int selectionCount = selectionSort(selectionArr);
   
   int[] bubbleArr = Arrays.copyOf(originalArr, originalArr.length);
   int bubbleCount = enhancedBubbleSort(bubbleArr);
   
   int[] insertionArr = Arrays.copyOf(originalArr, originalArr.length);
   int insertionCount = insertionSort(insertionArr);
   

2. 用局部变量统计比较次数：
   每个排序方法内部声明自己的计数器，不要用全局静态变量，避免互相干扰。
3. 检查并修正比较次数的统计逻辑：
   确保每一次数组元素的比较操作都被计数，比如冒泡排序里的if (arr[j] > arr[j+1])，每次进入这个判断前都要给计数器加1。

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