java - 为什么合并排序用于 Android/Java API 中的对象？

Question

Java Arrays.sort()对于原始类型使用快速排序。另一方面Arrays.sort()对于对象使用合并排序。而且，同样适用于 Collection.sort()它也使用合并排序。集合排序在下面使用数组排序实现。因此，从简单的意义上讲，我可以说基元是使用快速排序进行排序的，而对象是使用合并排序进行排序的。

我的猜测是它与排序算法本身有关。关于快速排序与合并排序的 SO 有很多讨论，例如 this和 this .关于哪个更好，似乎存在相互矛盾的说法，这是可以理解的，因为这取决于数据集。

我的理解是

• 就位:快速排序获胜。合并排序可以就地实现链表
• 外部存储数据:合并排序胜出。
• 排序列表(由任何形式的链表支持):合并排序获胜。 Link

Android API 似乎遵循与 Java 相同的模式。这是我在 Arrays.java 中找到的

    public static void sort(long[] array) {
    DualPivotQuicksort.sort(array);
}

还有这个，

public static void sort(Object[] array) {
    ComparableTimSort.sort(array);
}

我不明白的是，是什么让合并排序成为在 Java 或 Android 中对对象进行排序的良好候选者？为什么不把这个决定留给开发人员呢？

Answer 1

关键问题是排序稳定性 - 如果从排序顺序的角度来看两个元素相等，它们出现在结果中的顺序是否与输入中的顺序相同。

没关系，例如长。输入中 3 的所有实例将被组合在一起，没有人关心哪个是哪个。

另一方面，对象的不同可能不会影响排序顺序。如果您按腿数对动物进行排序，您可能会关心“猫”和“狗”是否保持原始顺序。

Arrays.sort合并排序是稳定的。用于基元的快速排序不需要稳定。