1

使用 Java（如果重要的话）

我一个接一个地运行 MergeSort 和 QuickSort 并比较两者的运行时间，在我的计算机上对 10,000,000 个值进行排序时我发现运行 MergeSort 时的运行时间然后是 QuickSort

合并排序 = 1.6 秒（大约）

快速排序 = 0.3 秒（大约）

当首先运行 Quicksort 然后 MergeSort 为相同的输入大小 10,000,000 我得到

合并排序 = 0.6s

快速排序 = 1.2 秒

我假设这可能与内存分配有关，但我不确定您将如何解释

-编辑- 在运行这两个例程之前，我正在创建一个包含 10,000,000 个随机值的文件 randomintegers.dat 的两个单独的数组 a[] 和 b[]。MergeSort 对数组 a[ ] 进行排序，QuickSort 对数组 b[ ] 进行排序。（即两个数组是分开的

4

2 回答 2

1

另一种选择是您将一个的输出用作下一个的输入。 QuickSort对输入“排序”（以积极的方式）比MergeSort.

于 2013-08-25T08:56:43.503 回答
0

您的基准测试代码很可能不符合标准，因为您编写的 Java 代码与 JVM 实际执行的代码之间存在距离，因此在 JVM 上进行基准测试非常棘手。如果您想要真正可靠的结果，您应该使用 Google Caliper 或 Oracle jmh 来利用多年的专业基准测试。缺乏这一点，请至少遵循以下准则：

  1. 创建两个数组：一个主数组，它保存随机数据，另一个将传递给排序方法。每次将master复制到工作数组中；
  2. 重复运行每种排序并显示每次通过的时间；
  3. 观察报告的时间。您应该看到第一次和第二次运行之间的排序时间下降，甚至可能进一步运行。你必须跑多次，直到你看到时间稳定了；

  4. MergeSort，与 不同QuickSort，使用动态内存分配。因此，它会导致垃圾收集器窃取总时间的一部分。通过显式垃圾收集来控制这一点，这又一次难以实现。我对一种我认为可行的简单方法的建议：

    for (int i = 0; i < 3; i++) { System.gc(); Thread.sleep(500); }

除此之外，还有 GC 调整参数、堆大小等，以便在MergeSort运行时最小化 GC。另一方面，MergeSort 期间的 GC 是不争的事实，它会影响你的实际表现。

最后，一般做法建议 QuickSort 应该是首选，只要您不介意它不稳定的事实。当按多个标准（首先按 X，然后按 Y）对对象进行排序时，此属性使其无用。

于 2013-08-25T09:29:54.310 回答