为何冒泡/选择/煎饼排序在未排序数组测试中运行更快？

我查阅资料得知，冒泡、选择、煎饼排序的最佳情况是数组已排序，此时程序运行更快。但我测试发现，这些算法在未排序数组上的运行速度反而比同数组排序后更快，请问原因是什么？

测试代码 #

测试逻辑代码 #

// ----------------- (1) Bubble Sort -----------------------------
// Unsorted
long startTime11 = System.nanoTime();
Sorting.bubbleSort(wordsToSort);
long endTime11 = System.nanoTime();
long timeLapsed11 = endTime11 - startTime11;
// Already sorted
long startTime12 = System.nanoTime();
Sorting.bubbleSort(wordsToSort);
long endTime12 = System.nanoTime();
long timeLapsed12 = endTime12 - startTime12;
// formats time with commas
String formated11 = formatter.format(timeLapsed11);
String formated12 = formatter.format(timeLapsed12);

bubbleSort方法实现 #

private static void bubbleSort(String[] arr, int n) {
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n - i - 1; ++j)
        {
            if (arr[j + 1].compareTo(arr[j]) < 0)
            {
                String temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

测试结果 #

60万+元素数组 #

• 未排序数组：11,372,240,025,900纳秒
• 已排序数组：22,020,911,806,900纳秒

测试二：

• 未排序数组：11,392,317,750,900纳秒
• 已排序数组：22,024,687,559,200纳秒

15000个单词的数组 #

• 未排序数组：1,407,057,900纳秒
• 已排序数组：1,650,519,600纳秒
• 未排序数组：1,430,736,200纳秒
• 已排序数组：1,645,250,000纳秒

添加预热阶段后：

• 未排序数组：1,453,011,900纳秒
• 已排序数组：1,660,550,800纳秒
• 未排序数组：2,025,017,800纳秒
• 已排序数组：2,466,999,700纳秒

2500个单词的数组 #

• 未排序数组：44,016,900纳秒
• 已排序数组：20,703,300纳秒
• 未排序数组：47,074,400纳秒
• 已排序数组：36,121,700纳秒

600个单词的数组 #

• 未排序数组：7,104,600纳秒
• 已排序数组：1,392,100纳秒
• 未排序数组：7,144,500纳秒
• 已排序数组：1,324,600纳秒

原因分析 #

1. 冒泡排序未实现提前终止优化 #

你的bubbleSort代码没有加入「是否发生交换」的判断逻辑，无论数组是否有序，都会执行完所有的外层循环（共n-1轮）和对应内层循环。标准优化版冒泡排序会在每轮循环开始前设置swapped标志，若本轮未发生任何交换，直接终止排序——这才是已排序数组成为最佳情况的前提。你的代码缺失该优化，导致已排序数组仍需执行全部的比较操作。

2. 字符串比较的开销差异（大数据量下的核心因素） #

你排序的是字符串数组，String.compareTo()的开销取决于相邻字符串的差异程度：

• 在未排序数组中，相邻字符串的字典序通常差异较大（比如"zoo"和"apple"），compareTo()只需比较前几个字符就能得出结果，单次比较耗时短；
• 在已排序数组中，相邻字符串往往字典序接近（比如"apple"和"apples"、"banana"和"band"），compareTo()需要比较更多字符才能确定顺序，单次比较耗时长。

虽然未排序数组中会执行交换操作，但字符串交换只是数组引用的赋值，开销极低。当数组规模较大时，已排序数组中大量高开销的字符串比较，会抵消甚至超过未排序数组中交换操作的额外开销，最终导致已排序数组的整体耗时更长。

3. 小数据量下的表现符合理论预期 #

从600、2500个元素的测试结果来看，已排序数组的耗时明显更短——这是因为小数据量下，字符串比较的开销差异不明显，而未排序数组中额外的交换操作占比更高，所以表现出符合理论的结果。

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