在Java Arrays.sort()中,基本类型使用快速排序.另一方面,Arrays.sort()对象使用合并排序.同样适用于Collection.sort(),它也使用Merge排序.集合排序使用下面的Arrays排序实现.所以,简单来说,我可以说基元是使用快速排序排序的,但是对象是使用合并排序进行排序的.
我的猜测是它与自己的排序算法有关.关于快速排序与合并排序的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);
}
我不明白的是,是什么让Merge排序成为在Java或Android中排序对象的好选择？为什么不把这个决定留给开发者？
最佳答案
关键问题是排序稳定性 – 如果从排序顺序的角度看两个元素相等,它们是否以与输入中相同的顺序出现在结果中.
原文链接：https://www.f2er.com/android/430314.html对于例如长.输入中的所有3个实例将组合在一起,没有人关心哪个是哪个.
另一方面,对象可能以不影响排序顺序的方式不同.如果您按腿数分类动物,您可能会关心“猫”和“狗”是否保持原始顺序.
Arrays.sort合并是稳定的.用于基元的快速排序不需要稳定.
