为什么Collections.sort()针对LinkedList进行了优化，而没有针对ArrayList进行优化？

Question

为什么Collections.sort()创建一个额外的对象数组并对数组进行Tim排序，最后将排序后的数组复制回List对象？我知道此调用针对 LinkedList 进行了优化，但我们不会损失 ArrayList 的性能吗？

我们本可以避免 2n 次将其转换为对象数组并将它们添加回列表的操作。我知道这些额外的操作不会影响整个排序操作的 Big-O，但我相信它可以针对 ArrayList.

进一步优化

我是不是漏掉了什么？我只是想了解为什么架构是这样布局的。谢谢。

https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/Collections.java#l164

Answer 1

您正在查看较早的 JDK 版本。至少因为 JDK 1.8.0_162 Collections.sort() 调用了 List 的 sort(Comparator<? super E> c)。虽然默认实现从 List 创建一个数组并对该数组进行排序，但 ArrayList 会覆盖该默认实现，并直接对后备数组进行排序。

Collections的sort:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

List的sort:

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

ArrayList的sort:

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

换句话说，这个问题已在 JDK 比您正在查看的版本更新的版本中得到解决。

你可以看看来源 here（感谢 eckes 的 link）。

为什么Collections.sort()针对LinkedList进行了优化，而没有针对ArrayList进行优化？

Why is Collections.sort() optimised for LinkedList, but is not optimised for ArrayList?

java

sorting

algorithm

timsort