为何冒泡排序平均情况耗时有时会超过最坏情况？

你的实现代码 #

public String bubbleSortCalc (float[] arr) { 
    float[] b = deepCopy(arr); 
    long start = System.nanoTime(); 
    boolean turnOn = false; 
    do { 
        turnOn = false; 
        for (int i = 0; i < b.length - 1; i++) { 
            if (b[i] > b[i + 1]) { 
                swap(b, i, i + 1); 
                turnOn = true; 
            } 
        } 
    } while (turnOn); 
    long end = System.nanoTime(); 
    return end - start + "ns"; 
}

测试数据（长度100的随机浮点数数组，3次测试） #

核心原因解析 #

1. CPU分支预测的反向增益

冒泡排序内层循环的核心分支if (b[i] > b[i + 1])是关键变量：

• 最坏情况（完全逆序数组）：这个分支每次都会触发交换，CPU的分支预测器会快速锁定100%正确的预测，流水线全程无中断，执行效率拉满。
• 平均情况（随机数组）：分支触发完全随机，分支预测器频繁预测错误，导致CPU流水线反复清空、重启，这部分额外开销的量级远大于交换次数减少带来的收益，最终总耗时更高。

2. 未优化的遍历范围放大了差异

你的实现没有做「记录最后交换位置」的优化：每一轮都固定遍历到数组末尾，哪怕后面的元素已经有序。

• 最坏情况里，虽然每轮都要走满整个数组，但因为分支预测完美，额外遍历的开销几乎可以忽略。
• 随机数组里，理论上交换次数更少，但分支预测失效的开销完全盖过了这个优势，甚至因为额外的无效遍历，让耗时进一步增加。

验证与优化建议 #

• 验证分支预测的影响：把完全逆序的数组随机打乱3-5个元素，再测试耗时，你会发现它的耗时会立刻飙升到接近随机数组的水平。
• 优化冒泡排序实现：记录每一轮最后一次交换的索引lastSwapIndex，下一轮循环只遍历到lastSwapIndex，减少无效遍历，同时降低分支预测失效的整体影响：

public String bubbleSortCalc (float[] arr) { 
    float[] b = deepCopy(arr); 
    long start = System.nanoTime(); 
    int n = b.length;
    int lastSwapIndex;
    do { 
        lastSwapIndex = 0;
        for (int i = 0; i < n - 1; i++) { 
            if (b[i] > b[i + 1]) { 
                swap(b, i, i + 1); 
                lastSwapIndex = i;
            } 
        }
        n = lastSwapIndex + 1;
    } while (lastSwapIndex != 0); 
    long end = System.nanoTime(); 
    return end - start + "ns"; 
}

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