为什么Java的排序实现在排序之前将列表转换为数组？

Question

在JDK 1.8中,该java.util.List#sort(Comparator)方法的第一个语句如下:

Object[] a = this.toArray();

将列表复制到数组中,对其进行排序,并将列表中的每个节点重置为数组中的排序值是很昂贵的.

在排序时,似乎不可能将值复制到临时数组ArrayList.我对吗？如果没有,是什么引导了该方法的创造者？

Answer 1

该sort在java.util.List接口只是默认的列表排序的实现.

ArrayList 使用sort方法覆盖此缺省值,该方法直接对其内部数组进行排序.

Answer 2

对于ArrayList或其他随机访问列表,您可能是正确的.

但是,Collections.sort支持任何List实现.例如,对于LinkedList,在排序期间交换元素会非常广泛(因为找到第i个元素需要线性时间).

将List转换为数组,并在对数组进行排序后设置原始List的元素会为算法添加线性时间组件,这不会改变算法的渐近运行时间(O(nlog(n))).

Answer 3

在OpenJDK 1.8中,java.util.ArrayList#sort(Comparator)不复制其内部数组; 正如你所建议的那样,它会按顺序排列.

java.util.List#sort()您批评的实施有以下随附文档:

默认实现获取包含此列表中所有元素的数组,对数组进行排序,并迭代此列表,从数组中的相应位置重置每个元素.(这样可以避免尝试对链接列表进行排序所导致的n²log(n)性能.)

也就是说,复制数组并随机访问移动比在链表中线性移动的开销更有效.通用实现尝试交换元素访问开销的复制开销.对于ArrayList不需要复制以获得对元素的相同随机访问的情况,库通过覆盖该方法省略了副本.

一个有趣的比较:看C++标准库的std::sort()和std::list::sort()功能:

• std::sort() 需要使用随机访问来分隔范围的参数.
• std::list::sort()通过遍历链表节点 仅假设线性访问.

通用std::sort()算法更有效,但是库阻止在std::list一个链接列表上调用它(类似于Java的链接列表java.util.LinkedList).std::list为方便起见,库提供了一种效率较低的方法.与Java库不同,C++库不会将a复制std::list()到数组以使用随机访问std::sort()算法.