java - 为什么我的随机数组在 0.001 秒内排序？

Question

我正在制作一个程序来比较 4 种不同类型的时间。每个排序使用一个排序数组、一个反向排序数组和一个随机填充的数组。排序和反向排序的时间看起来是正确的，但无论输入大小如何，随机填充的总是返回 <0.01。我的主要看起来像这样：

        System.out.println("---------LEFT PIVOT----------\n");

        for (int i = 0; i < 4; i++) {
            int[][] a = makearrays((int) (_SIZE * Math.pow(2, i)));
            System.out.println("SIZE: " + _SIZE * Math.pow(2, i));
            for (int k = 0; k < 3; k++) {
                long start = System.currentTimeMillis();
                Sort.quicksort(a[k], 0, a[k].length - 1);
                long end = System.currentTimeMillis();
                long time = end - start;
                System.out.println("Time for " + types[k] + ": " + (time / 1000.0) + " seconds.");
                System.out.println();
            }
        }

其中 a[0] 是已排序的，a[1] 是反向排序的，a[2] 是随机排序的。这是输出示例：

Time for SORTED ARRAY: 1.212 seconds.

Time for REVERSE SORTED ARRAY: 5.226 seconds.

Time for RANDOM ARRAY: 0.008 seconds.

在另一次运行中，它输出以下内容：

Time for SORTED ARRAY: 1.19 seconds.

Time for REVERSE SORTED ARRAY: 4.053 seconds.

Time for RANDOM ARRAY: 0.009 seconds.

我打印了每次排序前后的数组，可以确认随机数组在排序前是完全随机的，排序后是完全随机的。有谁知道为什么它会打印这么短的时间？谢谢。

编辑：在那个例子中，我使用了以下内容：

        int _SIZE = 100000;

以下是数组的生成方式：

    public static int[][] makearrays(int size) {
        Random r = new Random();
        int[][] a = new int[3][size];
        for (int i = 0; i < size; i++) {
            a[0][i] = i;
            a[1][i] = size - i - 1;
            a[2][i] = r.nextInt(size);
        }
        return a;
    }

这就是我的快速排序的样子：

public static void quicksort(int[] arr, int l, int r) {
        if (l < r) {
            int s = partition(arr, l, r);
            quicksort(arr, l, s-1);
            quicksort(arr, s+1, r);
        } 
    }

    public static int partition(int[] arr, int l, int r) {
        int p=arr[l],i=l+1;

        for (int j =l+1;j<=r;j++) {
            if (arr[j]<p) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        
        int temp = arr[l];
        arr[l] = arr[i-1];
        arr[i-1] = temp;
        return i-1;
    }

标签： javaarrayssortingquicksort