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

Question

在JDK 1.8中，java.util.List#sort(Comparator)方法的第一条语句如下：

Object[] a = this.toArray();

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

似乎在对 ArrayList 进行排序时可以不将值复制到临时数组中。我是对的吗？如果不是，那么创造该方法的人是根据什么指导进行的呢？

- the_kaba

---

有许多列表实现，包括链表，在这些实现中，对列表本身进行排序可能更加昂贵。 - Sualeh Fatehi

似乎在ArrayList的情况下，可以不将值复制到数组中。这正是它的实现方式。 - xehpuk

感谢您的快速回复。 - the_kaba

Answer 1

java.util.List 接口中的 sort 方法仅是对列表排序的默认实现。

ArrayList 通过覆盖该默认方法提供了一个能够直接对其内部数组进行排序的方法。

- greg-449

Answer 2

对于ArrayList或其他随机访问列表，你可能是正确的。然而，Collections.sort支持任何List实现。例如，对于LinkedList，在排序过程中交换元素将非常昂贵（因为查找第i个元素需要线性时间）。将List转换为数组，并在数组排序后设置原始List的元素，会向算法添加一个线性时间组件，但不会改变渐近运行时间为 (O(nlog(n)))。

- Eran

---

看起来像这样简单的代码： if(this instanceof ArrayList) { // 只排序 } else { // 像往常一样做其他事情 }会改善该方法。我是对的吗？ - the_kaba

@the_kaba 这并不是必要的：正如Greg所指出的那样，像ArrayList这样的实现将覆盖此默认方法，以便它们可以在不首先创建数组的情况下执行排序。 - Marco13

Answer 3

在OpenJDK 1.8中，java.util.ArrayList#sort(Comparator)不会复制其内部数组，它会就地排序，正如您建议的那样。

您所批评的java.util.List#sort()实现具有以下附带文档：

默认实现获取包含此列表中所有元素的数组，对数组进行排序，并迭代此列表重置每个元素以从数组中的相应位置获取。 （这避免了尝试就地对链表进行排序导致的O(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 ++库不会将std::list()复制到数组中以使用随机访问的std::sort()算法。

- seh