时间戳

首页 > 解决方案 > 我正在合并排序长度为 10,000 到 75,000 的 int 数组。我得到了奇怪的排序时间。为什么会这样？

java - 我正在合并排序长度为 10,000 到 75,000 的 int 数组。我得到了奇怪的排序时间。为什么会这样？

问题描述

我正在为我的算法类做作业，我必须证明内部合并排序的时间复杂度为O(n log n)。为此，我制作了长度从 10,000 个元素到 75,000 个元素不等的数组。然后我加载随机数低于 10,000 的数组，并将数组长度输出到控制台以及排序所需的时间。

奇怪的结果是，有些需要大约 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;
}

标签： javaarraystime-complexitymergesort

解决方案

评论中的几个考虑因素：

  • 在 WindowsSystem.currentTimeMillis()中，您可以获得一个精度为 64 赫兹（或 15.625 毫秒）的时钟，因此最小差异为 15 毫秒。
  • 鉴于您对数组的随机初始化，它们将被部分排序，并且对部分排序的数组进行排序将（稍微）比未排序的数组快

当您将可复制性问题相加时，很明显要获得显示 O(n log n) 复杂性的合理结果，您应该：

推荐阅读