为什么对Android/Java中的对象使用合并排序？

Question

在Java原语类型中，Arrays.sort()使用快速排序。另一方面，对象的Arrays.sort()使用合并排序。对于同样使用合并排序的Collection.sort()也是如此。集合排序在下面使用数组排序实现。因此，简单地说，我可以说原语是使用快速排序排序的，而对象是使用合并排序排序的。

我猜这和排序算法有关。关于快速排序和合并排序有很多讨论，比如这和这。似乎有矛盾的主张，谁更好，这是可以理解的，因为这取决于数据集。

我的理解是

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

Android似乎遵循与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

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

对于long来说，这并不重要。输入中的所有3实例都将分组在一起，没有人关心哪个是哪一个。

另一方面，对象可能以不影响排序顺序的方式不同。如果你是按腿数分类动物，你可能会关心“猫”和“狗”是否保持原来的顺序。

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

Answer 2

请看这个答案：为什么Collections.sort使用合并排序而不是快速排序？

TL;DR：

与合并相比，QuickSort有两个主要缺陷：

1. 它不稳定(正如parsifal所指出的)。
2. 它不能保证n个log的性能，它可以在病理输入上退化为二次性能。

Answer 3

我认为问题是

是什么使合并排序成为对Java对象进行排序的好选择，以及对原语进行快速排序的原因？

已经被其他人回答了，但是问题是

为什么这个决定没有留给开发人员呢？

还没有得到解决。

事实上，任何开发人员都可以很容易地从Collection或ArrayList派生出一个新的类，隐藏了sort()方法(因为sort()是一个static方法，所以必须是http://docs.oracle.com/javase/tutorial/java/IandI/override.html)并使用他们自己的自定义实现。

这很少(如果有的话)是因为当今大多数年轻的程序员对Java的接触比C++更多。在Java社区中，“抽象”意味着您不知道类的底层实现实际上是如何工作的，而且您也不需要这样做。JVM的机器独立性使我们对速度/效率权衡的直觉变得迟钝。因此，我们中的许多人对数据结构和算法的理解不如一些更老、更有经验的程序员。

这几乎与C++中对抽象的理解截然相反。引用亚历克斯·斯捷潘诺夫的话：

事实上，我并不认为库可以消除程序员对算法和数据结构的了解。它只是消除了程序员实现它们的需要。需要了解数据结构的基本属性才能正确地使用它们，这样应用程序才能满足自己的复杂性需求。