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

Question

我试图在Java，插入和合并排序中获得两种排序算法的运行时。程序在433个单词的未排序ArrayList上多次运行排序，并存储要排序的100,200,300,400和433个单词（整个数组）所用的经过时间，然后打印出每个单词的平均时间。这些。

我相信，我的代码还可以。然而，我遇到了一个奇怪的异常，我想知道是否有人可以帮助我理解。

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

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

当运行一次结果我相信如预期的那样，对于较低数量的元素排序，插入排序更快，但对于更高的数量和整个数组，合并排序更快。

但是，当运行10,000次时，平均时间偏离，对于排序的所有元素数量，插入排序的速度要快得多。

就像每次迭代时插入排序加速一样，这怎么可能呢？

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

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

Answer 1

这些算法的时间复杂度是众所周知的：用于插入排序的O（N2）和用于合并排序的O（N.log（N））。

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

• 400字符串的数据集不是很大，实现的质量可能比算法的复杂性更重要。
• 你的插入排序的实现不是很有效，但至少它在适当的位置运行，因此有效的时间复杂度为O（N2）。然而，您应该删除执行每100个元素的测量代码，并且具有非常重要的复杂性。
• 合并排序的实现效率很低：为每个拆分和合并阶段一次为一个元素分配多个动态数组。这是非常耗时的，并且导致许多对象被分配并且几乎立即悬挂以便垃圾收集器以高成本回收。
• 单个调用合并排序可能比插入排序更好，如果时间有意义，但许多调用可能会触发垃圾收集器，但需要大量开销，尽管您的计时没有显示出这种情况的证据，可能是因为10000次迭代是不够。
• 真正的解释实际上很简单：由于您的插入排序实现对数据集进行了排序，因此已经为每个后续调用进行了排序，这是具有线性复杂性的插入排序的最佳情况。

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