测试快速排序

-2

的速度，我读算法第四版普林斯顿的书，并观看了在线课程视频。我发现了两件有趣的事情。测试快速排序

它在视频中说，如果我们在快速排序使用截止这样的，我们将通过10〜20％，加快程序：

如果（HI - LO < CUTOFF）插入。排序（一）;

它建议，当我们使用递归公式对数组的分成子阵列，和排序子阵列递归，我们可以使用插入排序算法当子阵列的尺寸比CUTOFF instead.However小，当我测试它与CUTOFF大小3,7和10.它不是这种情况。这在我的测试数据集中慢了大约10倍。数据集是5000个随机数的数组。所以我想我们最好不要对小尺寸数组使用插入排序。

当我尝试测量代码的运行时间并将其与本课程的标准代码（即algs4.jar库）进行比较时。我发现我的时间更长，即使我将我的代码更改为标准代码。最后，我意识到，即使我们QUICKSORT同一阵列的两倍（复制数组作为A1，A2），第二排序的运行时间将永远是一半左右的第二排序的运行时间。即（伪码）： stopWatch sw1 = new stopWatch（）; quicksort（a1）; print sw1.elaspedTime（）;
```
stopWatch sw2 = new stopWatch(); 
quicksort(a2); 
print sw2.elaspedTime(); 
```

然后第二个成本大约一半时间，即使它们是相同的算法和排序在同一阵列。我不知道为什么会发生这种情况。这是一个非常有趣的现象。

来源

2014-10-03 ohmygoddess

做你自己实现快速排序，或者您使用的构建在一个 – Steve 2014-10-03 22:20:56

我自己实施和比较书中的代码。最后，我改变了我的代码，就像这本书一样。结果与上面描述的相同 – ohmygoddess 2014-10-03 22:24:22

我几乎100％确定如果您更改测试器算法的执行顺序，您将得到其他结果。 JVM需要时间来蠕变。 – 2014-10-03 22:28:56

现在。理论上它可能会更快，但取决于您使用的语言，编译器，系统和CPU，它可能会有所不同。我可以用你的第二点作为例子。 CPU有一些叫缓存的东西，它可以容纳频繁使用的数据来提高速度。它非常小，但速度超快，比RAM更快。因此，基本上第一次运行程序时，该数组最初在内存中，并且在缓存未命中时进入缓存。当你第二次运行相同的代码时，一切都已经在缓存中了，不需要在RAM中查找它，也不需要缓存丢失，所以它比第一次运行更快。如果你想准确的结果，那么你可能需要清除RAM清除缓存，关闭所有正在运行的程序和ECT

来源

2014-10-03 22:26:08 Steve

Got you！有道理。谢谢！ – ohmygoddess 2014-10-03 22:28:23

测试快速排序

回答

相关问题