代码之家 › 专栏 › 技术社区 › zjffdu

为什么Java的ARARYES.REST方法使用不同类型的两种不同排序算法?

mergesort quicksort algorithm java

zjffdu · 技术社区 · 15 年前

Java 6的 Arrays.sort 方法对基元数组使用快速排序,对对象数组使用合并排序。我相信大多数时候,快速排序比合并排序快,而且内存成本更低。我的实验支持这一点,尽管这两种算法都是O(n log(n))。那么,为什么不同的算法用于不同的类型呢?

6 回复 | 直到 6 年前

170

rogerdpack 7 年前

Community CDub 8 年前

this answer Arrays#Sort() TimSort Arrays#sort() Dual-Pivot QuickSort

msw 9 年前

visual comparison of various algorithms

kukido 11 年前

重要的考虑和合并排序使用的额外空间可能不是问题。如果程序员使用的是原始类型,可能性能是最重要的,因此它们使用快速排序。”

David McManamon 7 年前

爪哇 Arrays.sort 方法使用快速排序、插入排序和合并排序。甚至在OpenJDK代码中实现了单透视和双透视快速排序。最快的排序算法依赖于环境,优胜者是:小数组的插入排序(当前选择的47个),大部分排序数组的合并,以及剩余数组的快速排序,因此Java的数组SoRT()试图根据这些标准选择最佳的算法来应用。

Dinesh Kumar 6 年前

<> > java. UTIL.Engults/EM>对于实现<强>可比< /强>或使用<强>比较器< /强>的对象,使用INTIGHT>QuaskReule>强型> INT和<强>合并> <强> >。使用两种不同方法的想法是,如果一个程序员使用对象,可能空间不是一个非常重要的考虑因素,因此由 mergesort使用的额外空间可能不是问题,如果程序员使用基本类型,则性能可能是最重要的事情,因此使用 quickORT 。

例如: 这是排序稳定性问题时的示例。