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

Question

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

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

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

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

当运行一次时，我相信结果符合预期，即插入排序对于排序的元素数量越少，合并排序对于元素数量越多和整个数组越快。

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

好像每次迭代都在加速插入排序，这怎么可能？

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

感谢您提供的任何帮助。

Answer 1

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

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

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

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

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

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

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

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