java - 插入和合并排序算法 - 异常时序结果

Question

我正在尝试获取 Java 中两种排序算法的运行时，即插入和合并排序。该程序对 433 个单词的未排序 ArrayList 多次运行两种排序，并存储要排序的 100、200、300、400 和 433 个单词（整个数组）所花费的时间，然后打印出每个单词所花费的平均时间这些。

我相信我的代码没问题。但是，我遇到了一个奇怪的异常情况，我想知道是否有人可以帮助我理解。

以下是两种排序都执行一次时的结果：

以下是两种排序都执行10,000 次时的结果：

当我相信结果符合预期时运行时，插入排序对于排序的元素数量较少但合并排序对于较高数量和整个数组来说更快。

但是，当运行 10,000 次时，平均时间相差很远，对于所有排序的元素，插入排序要快得多。

就好像每次迭代都会加快插入排序，这怎么可能？

用于运行所述排序算法的多次迭代的排序算法和方法的代码 - 在下面的评论中

感谢您的任何帮助，您可以提供。

标签： javaalgorithmmergesortinsertion-sort

Answer 1

这些算法的时间复杂度众所周知：插入排序为O(N ² ) ，归并排序为O(N.log(N))。

以下是您意外观察的可能原因：

• 400 个字符串的数据集不是很大，实现的质量可能比算法的复杂性更重要。

• 您对插入排序的实现不是很有效，但至少它在原地运行，因此有效时间复杂度为O(N ² )。然而，您应该删除每 100 个元素执行一次的测量代码，并且具有非平凡的复杂性。

• 您的合并排序实现效率很低：您为每个拆分和合并阶段一次分配多个动态数组一个元素。这非常耗时，并且导致大量对象被分配并几乎立即悬空，以便垃圾收集器以巨大的代价进行回收。

• 如果时间完全有意义，则对合并排序的单个调用可能比插入排序执行得更好，但是许多调用可能会触发垃圾收集器，并产生大量开销，尽管您的时间没有显示出这一点的证据，可能是因为 10000 次迭代是不够。

• 真正的解释实际上很简单：由于您的插入排序实现对数据集进行了适当的排序，因此它已经为每个后续调用进行了排序，这是具有线性复杂度的插入排序的最佳情况。

您应该对初始数据集的副本进行排序以获得更有意义的基准。并且还要寻找更好的合并排序实现，它使用单个临时数组并对元素进行就地排序，并在预先知道大小时避免使用动态数组。