为什么Collections.sort使用Mergesort但是Arrays.sort却没有？ [英] Why does Collections.sort use Mergesort but Arrays.sort does not?

问题描述

我正在使用JDK-8（x64）。对于 Arrays.sort （primitives）我在Java文档中发现了以下内容：

I am using JDK-8 (x64). For Arrays.sort (primitives) I found the following in the Java documentation:

排序算法是Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch的Dual-Pivot Quicksort 。

对于 Collections.sort （对象）我发现这个Timsort：

For Collections.sort (objects) I found this "Timsort":

此实现是一个稳定的，自适应的，迭代的 mergesort ...此实现将指定的列表转储到数组中，对数组进行排序，并重复列表重置每个元素从数组中的相应位置。

This implementation is a stable, adaptive, iterative mergesort ... This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array.

如果 Collections.sort 使用数组，为什么不直接调用 Arrays.sort 或使用双轴 QuickSort ？为什么要使用 Mergesort ？

If Collections.sort uses an array, why doesn't it just call Arrays.sort or use dual-pivot QuickSort? Why use Mergesort?

推荐答案

API保证稳定排序Quicksort不提供。但是，当按照自然顺序对原始值进行排序时，您不会注意到差异，因为原始值没有标识。因此，Quicksort用于原始数组，因为它的效率稍高。

The API guarantees a stable sorting which Quicksort doesn’t offer. However, when sorting primitive values by their natural order you won’t notice a difference as primitive values have no identity. Therefore, Quicksort is used for primitive arrays as it is slightly more efficient.

对于您可能注意到的对象，当根据等于实施或提供的比较器更改其订单。因此，Quicksort不是一个选择。因此使用MergeSort的变体，当前的Java版本使用 TimSort 。这适用于 Arrays.sort 和 Collections.sort ，尽管使用Java 8， List 本身可能会覆盖排序算法。

For objects you may notice, when objects which are deemed equal according to their equals implementation or the provided Comparator change their order. Therefore, Quicksort is not an option. So a variant of MergeSort is used, the current Java versions use TimSort. This applies to both, Arrays.sort and Collections.sort, though with Java 8, the List itself may override the sort algorithms.

这篇关于为什么Collections.sort使用Mergesort但是Arrays.sort却没有？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！