0

我实现了一个标准的快速排序算法，并在多次运行中对其进行了测试，并将运行时间存储在一个数组中。

int max = 100;
int runs = 1000;
int[] arr = new int[max];
Long[] times = new Long[runs];  

while(n < runs){
        for(int i =0 ; i<max; i++){
        arr[i]=(int)(Math.random()*99);
        //arr[i] = i;  
        }

        Long start = System.nanoTime();
        quicksortsimple(arr,0,max-1);
        Long now = System.nanoTime();

        times[n++] = now-start;
    }

现在发生的情况是，输出的“次”数组以更大的值开始并逐渐减小，在第 100 个索引（快速排序 100 次运行）之后，它变得有点恒定，但该值小于初始 2-3 值的十分之一. n= 1000 返回的平均值在程序的几个 rune 中是相同的。

即使我将数组初始化为已经排序（注释掉的行），也会发生同样的事情，尽管需要更多的平均时间（应该如此）。

但这不应该为同一阵列上的同一算法返回如此不同的运行时间。下降模式表明什么，如果有的话？

4

1 回答 1

0

（下面的解释并不精确到最后的细节，但足以理解发生了什么）

一开始，你的 JRE 以解释模式（慢）运行程序，直到它的热点引擎检测到排序值得加速并创建一个本地编译的翻译，然后使用它并且运行速度比来自解释代码的速度快得多第一次迭代。

于 2017-09-21T12:33:09.627 回答