java - 为什么合并排序在对反向排序列表进行排序时比普通排序列表更快?

标签 java algorithm sorting merge mergesort

我正在对按升序输出的合并排序算法进行基于比较的分析。我注意到当我给它一个反向排序列表而不是一个升序排序列表时它更快(比较更少)。谁能解释一下为什么?

最佳答案

要合并两个长度为 M 和 N 的列表,您最多需要 M+N-1 次比较。如果第一个列表中的所有条目都小于第二个列表中的条目,则只需进行 M 次比较。如果第二个列表中的所有条目都小于第一个列表中的条目,则只需要进行 N 次比较。

如果您要排序的数字总数不是 2 的幂,您将遇到分成两个不同长度列表的情况。我怀疑您以一种方式实现了合并排序,即这两个中的第一个多了一个元素。这意味着该分区和合并的 M = N+1。如果您的元素顺序相反,则第二个列表中的所有元素都将小于第一个列表中的元素,并且在顺序正确的情况下,您将需要 N 次而不是 M 次比较。

如果你要排序的列表的幂为2,那么正序和倒序应该没有区别。

关于java - 为什么合并排序在对反向排序列表进行排序时比普通排序列表更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12168092/

相关文章:

python - 什么算法解决方案可以匹配包含倍数的两个垃圾箱之间的项目?

java - 如何存储iv、salt和密文?

algorithm - 在线性时间内对 [log n] 不同值进行排序

c - 为什么我的随机数组和排序程序不工作?

c++ - 日期到星期几算法?

java - 在没有概率的情况下渲染 Barnsley Fern 分形

java - 如何在 Java 中对字符串的 ArrayList 进行排序?

javascript - 为 Cordova 插件重新设计非单例 Java 类?

java - 我们有短信协议(protocol)的错误代码吗?

java - 如何在 Java 中使用 String 或 StringBuilder 倒序搜索?