如何正确比较排序方法快速排序和归并排序之间的运行时间？

Question

我有一个作业来比较使用合并排序和快速排序对大型整数数组进行排序的执行时间。算法的实现是从书中复制的。它们都按升序对整数进行排序。然后我被要求说明快速排序的平均速度是多少。然而，根据我的测试样本（尽管很小），我发现合并排序速度快了一小部分，这让我相信我的测试不正确。

我有 2 个程序，一个用于合并排序，一个用于快速排序。它们的 main() 代码是相同的（如下所示）。我创建了一个随机大小在 0 和某个选定上限之间的数组。然后我用随机整数填充数组。然后我对数组进行排序并打印它。我使用 currentTimeMillis() 来检查程序的运行时间。我对快速排序和合并排序进行了 10 次运行测试，将总时间相加并除以 10 以获得排序的平均运行时间。我没有发现快速排序平均比合并排序更快。我也尝试过使用固定的数组大小，但结果仍然没有暗示快速排序更快。什么是正确的测试方法？

public static void main(String[] args){

        /* create an array of some size 0 to 100000 with

           random integers and measure the time it takes

           to sort the array in ascending order (where sort() is either quicksort 

           or mergesort.)

        */

        long a = System.currentTimeMillis();

        Random rnd = new Random(System.currentTimeMillis());

        Integer[] array = new Integer[rnd.nextInt(100000)];

        for(int i = 0; i < array.length; i++){

            array[i] = rnd.nextInt();

        }

        sort(array);

        System.out.println(Arrays.toString(array));

        long b = System.currentTimeMillis() - a;

        System.out.println("Program runtime: " + b + "ms");

    }

}

Expected result: Quicksort average running time should be some % faster

in comparison to mergesort, for large random integer arrays.

Actual result: Mergesort was slightly faster in most tests 

(10K elements, 100K elements, 1000K elements).

Answer 1

您的测量包括随机数组的生成，这是一项繁重的操作，并且会扭曲结果。// do initialization herelong a = System.nanoTime();sort(array);long b = System.nanoTime();// do the output here...只会测量执行期间经过的时间sort(array)。哪个时间是您感兴趣的时间。替换System.currentTimeMillis()为System.nanoTime()使得结果更加准确。