集合排序方法内部使用哪种排序算法？

Question

在collections类中有一个方法sort()用于排序集合元素,但我有一个疑问,内部使用哪种排序算法对元素进行排序.我用Google搜索但没有得到正确答案.请帮帮我 .

Answer 1

答案取决于您所讨论的Java的实现,以及您要排序的数据结构的类型.

例如,集合的javadoc(在Java 6中)指出:

只要遵守规范本身,实现者就可以随意替换其他算法.(例如,sort使用的算法不必是mergesort,但它必须是稳定的.)

话虽如此,不同版本的javadocs对这些Collections::sort方法说了这个:

Java 6:

排序算法是修改后的mergesort(如果低子列表中的最高元素小于高子列表中的最低元素,则省略合并).该算法提供有保证的n log(n)性能.此实现将指定的列表转储到数组中,对数组进行排序,并迭代列表,从数组中的相应位置重置每个元素.这样可以避免尝试对链接列表进行排序所导致的n2 log(n)性能.

对于排序"本机数组"(例如:int),它使用"quicksort",默认为小块/数组大小的插入排序.

Java 7:

实现注意事项:此实现是一个稳定的,自适应的迭代合并输出,当输入数组被部分排序时,它需要远低于n lg(n)的比较,同时在输入数组随机排序时提供传统mergesort的性能.如果输入数组几乎已排序,则实现需要大约n次比较.临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的n/2个对象引用不等.

该实现在其输入数组中具有升序和降序的相同优势,并且可以利用同一输入数组的不同部分中的升序和降序.它非常适合合并两个或多个排序数组:只需连接数组并对结果数组进行排序.

该实现改编自Tim Peters的Python排序(TimSort).它使用了Peter McIlroy的"乐观排序和信息理论复杂性"中的技术,参见"第四届年度ACM-SIAM离散算法研讨会论文集",第467-474页,1993年1月.

此实现将指定的列表转储到数组中,对数组进行排序,并迭代列表,从数组中的相应位置重置每个元素.这样可以避免尝试对链接列表进行排序所导致的n2 log(n)性能.

为了排序"原生阵列"(例如:ints),它使用了"双枢轴快速排序".

Java 8:

该Collectionsjavadoc的推迟到目录::排序它说同样的事情上面引述的Java 7的文本.Java 8的"双枢轴快速排序"显然有一些小的改进.

Java 9:

没变

Java 10:

针对双枢轴快速排序提出了更多增强功能.

另请注意,其他sortAPI 可能会有所不同; 例如,Arrays类中为基元数组量身定制的那些.例如Java 9/Arrays::sort(int[])说:

实施说明:排序算法是Vladimir Yaroslavskiy,Jon Bentley和Joshua Bloch的双枢轴快速算法.该算法在许多数据集上提供O(n log(n))性能,导致其他快速降序降级为二次性能,并且通常比传统(单枢轴)Quicksort实现更快.

而且parallelSort方法又不同了.

最重要的是,如果您想确定使用哪种算法,请查看您正在使用的Java版本的源代码.