插入和合并排序算法 - 异常计时结果
Insertion & Merge sort algorithms - Anomalous timing results
我正在尝试为 Java 中的两种排序算法获得 运行 次，即插入和合并排序。
程序 运行s 对 433 个单词的未排序 ArrayList 进行多次排序，并存储 100、200、300、400 和
要排序的 433 个单词（整个数组），然后打印出每个单词所用的平均时间。
我相信我的代码没问题。但是，我遇到了一个奇怪的异常现象，我想知道是否有人可以帮助我理解。
以下是两种排序都执行一次一次的结果：
以下是两种排序都执行 10,000 次 时的结果：
当 运行 一旦结果如我所料，即对于排序的元素数量较少，插入排序更快，但对于元素数量多和整个数组，合并排序更快。
然而，当 运行 10,000 次时，平均时间有很大偏差，插入排序对于所有已排序元素的数量要快得多。
好像插入排序每次迭代都在加速，这怎么可能？
用于运行所述排序算法多次迭代的排序算法和方法的代码 - 在下面的评论中
感谢您提供的任何帮助。
这些算法的时间复杂度众所周知：O(N2)用于插入排序，O (N.log(N)) 用于归并排序。
以下是您意外观察到的可能原因：
400 个字符串的数据集不是很大，实现的质量可能比算法的复杂性更重要。
您的插入排序实现效率不高，但至少它运行到位，因此有效时间复杂度为 O(N2)。然而，您应该删除每 100 个元素执行一次的测量代码，其复杂性非常高。
您的合并排序实现效率很低：您为每个拆分和合并阶段一次分配多个动态数组一个元素。这是非常耗时的，并且导致大量对象被分配并几乎立即悬空，以供垃圾收集器以巨大的代价回收。
单次调用合并排序可能比插入排序执行得更好，如果时间有意义的话，但许多调用可能会触发垃圾收集器，产生大量开销，尽管你的时间并不重要证明这一点，可能是因为 10000 次迭代还不够。
真正的解释其实很简单：因为你的插入排序实现对数据集进行了就地排序，所以它已经为每个后续调用排序，这是具有线性复杂度的插入排序的最佳情况。
您应该对初始数据集的副本进行排序以获得更有意义的基准。并且还寻找一个更好的合并排序实现，它使用单个临时数组并对元素进行适当的排序，并在预先知道大小时避免动态数组。
我正在尝试为 Java 中的两种排序算法获得 运行 次，即插入和合并排序。 程序 运行s 对 433 个单词的未排序 ArrayList 进行多次排序，并存储 100、200、300、400 和 要排序的 433 个单词（整个数组），然后打印出每个单词所用的平均时间。
我相信我的代码没问题。但是，我遇到了一个奇怪的异常现象，我想知道是否有人可以帮助我理解。
以下是两种排序都执行一次一次的结果：
以下是两种排序都执行 10,000 次 时的结果：
当 运行 一旦结果如我所料，即对于排序的元素数量较少，插入排序更快，但对于元素数量多和整个数组，合并排序更快。
然而，当 运行 10,000 次时，平均时间有很大偏差，插入排序对于所有已排序元素的数量要快得多。
好像插入排序每次迭代都在加速，这怎么可能？
用于运行所述排序算法多次迭代的排序算法和方法的代码 - 在下面的评论中
感谢您提供的任何帮助。
这些算法的时间复杂度众所周知：O(N2)用于插入排序，O (N.log(N)) 用于归并排序。
以下是您意外观察到的可能原因：
400 个字符串的数据集不是很大，实现的质量可能比算法的复杂性更重要。
您的插入排序实现效率不高，但至少它运行到位，因此有效时间复杂度为 O(N2)。然而，您应该删除每 100 个元素执行一次的测量代码，其复杂性非常高。
您的合并排序实现效率很低：您为每个拆分和合并阶段一次分配多个动态数组一个元素。这是非常耗时的，并且导致大量对象被分配并几乎立即悬空，以供垃圾收集器以巨大的代价回收。
单次调用合并排序可能比插入排序执行得更好，如果时间有意义的话，但许多调用可能会触发垃圾收集器，产生大量开销，尽管你的时间并不重要证明这一点，可能是因为 10000 次迭代还不够。
真正的解释其实很简单：因为你的插入排序实现对数据集进行了就地排序，所以它已经为每个后续调用排序，这是具有线性复杂度的插入排序的最佳情况。
您应该对初始数据集的副本进行排序以获得更有意义的基准。并且还寻找一个更好的合并排序实现，它使用单个临时数组并对元素进行适当的排序，并在预先知道大小时避免动态数组。