我正在对长度为10000到75000的整数数组进行合并排序。我的时间越来越奇怪了。为什么会这样？

Question

我正在为我的算法类做一个赋值，我必须证明内部合并排序的时间复杂度为O（n logn）。为此，我制作了长度从10000个元素到75000个元素的数组。然后，我将随机数加载到10000以下的数组中，并将数组长度与排序所需的时间一起输出到控制台。

奇怪的结果是，有些数组需要约15毫秒的给定或获取，而另一些数组则需要0毫秒，即使数组的长度要长数万个整数。你知道为什么吗？我可以上传输出的屏幕截图，但需要有人批准，因为我没有足够的“声誉”。我已经检查了阵列。调用mergeSort（）方法后，它们看起来确实被排序了。

public static void main(String[] args){
    int[] dataLength = { 10_000, 15_000, 20_000, 25_000, 30_000,
                         35_000, 40_000, 45_000, 50_000, 55_000,
                         60_000, 65_000, 70_000, 75_000 };
    // internal merge sort
    for (int i = 0; i < dataLength.length; i++) {
        int[] input = new int[dataLength[i]];
        for (int j = 0; j < input.length; j++) {
            input[j] = random.nextInt(10000);
        }

        long startTime = System.currentTimeMillis();
        mergeSort(input, 0, input.length);
        long endTime = System.currentTimeMillis();

        System.out.println("Length of array is: " + input.length + ". The sorted array: " +
                           Arrays.toString(input));
        System.out.println("Internal sort with " + dataLength[i] + " items took: " +
                           (endTime - startTime) + " milliseconds");
    }
}

public static void mergeSort(int[] input, int start, int end) {
    if (end - start < 2) {
        return;
    }

    int mid = (start + end) / 2;
    mergeSort(input, start, mid);
    mergeSort(input, mid, end);
    merge(input, start, mid, end);
    return;
}

public static void merge(int[] input, int start, int mid, int end) {
    if (input[mid - 1] <= input[mid]) {
        return;
    }
 //        index of "left" array
    int i = start;
 //        index of "right" array
    int j = mid;
    int tempIndex = 0;
    int[] temp = new int[end - start];

    while (i < mid && j < end) {
        temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
    }
 //        optimizes the merge. If there are elements in the left array we just copy them back
 //        into the input array instead of merging them with the temp array first
    System.arraycopy(input, i, input, start + tempIndex, mid - i);
    System.arraycopy(temp, 0, input, start, tempIndex);
    return;
}

Answer 1

评论中的几个考虑因素：

• 在Windows中，ystem.currentTimeMillis（）为您提供64 hz（或15.625 ms）精度的时钟，因此最小差异为15 ms。
• 给定您对数组的随机初始化，它们将被部分排序，并且对部分排序的数组进行排序将比未排序的数组（略）快

当你把可复制性问题加在一起时，很明显，要得到显示O（n logn）复杂性的合理结果，你应该：

• 使用System.nano时间获得更精确的时钟测量。
• 使用较大的数组来扩大时间差
• 使用像JMH这样的代码分析器/基准测试器