为什么在最坏情况下排序所花费的时间比平均情况要少

Question

我正在生成 100,000 个随机数并传递给排序函数。这些数字是随机的，这意味着对数组进行排序所花费的时间应该大于最好情况并小于最坏情况。（如果我错了，请原谅我，仍在学习时间复杂度）。花了25秒。

然后，我再次将相同的排序数组传递给排序函数，花费了近 0 秒。

然后，我反转数组，因此它应该进行最大次数的迭代（交换），因此平均时间复杂度应该超过 25 秒。然而，只需要8秒。

public class BubbleSort {

    private static void sort(int arr[]) {
        int n = arr.length;
        int temp = 0;
        boolean sorted = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    sorted = false;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {

        int arr[] = new int[100000];
        Random rand = new Random();

        for (int i = 0; i < 100000; i++) {
            arr[i] = rand.nextInt(10000000);
        }

        // Avg Case
        long x = System.currentTimeMillis();
        sort(arr);
        long y = System.currentTimeMillis();
        float sec = (y - x) / 1000F;
        System.out.println("avg Case " + sec);

        // Best Case
        x = System.currentTimeMillis();
        sort(arr);
        y = System.currentTimeMillis();
        sec = (y - x) / 1000F;
        System.out.println("Best Case " + sec);

        // Worst Case
        reverse(arr);
        x = System.currentTimeMillis();
        sort(arr);
        y = System.currentTimeMillis();
        sec = (y - x) / 1000F;
        System.out.println("Worst Case " + sec);

    }
}

这是输出：

avg Case 25.207
Best Case 0.0
Worst Case 8.896