8

为什么会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

4

1 回答 1

11

您正在查看较旧的 JDK 版本。至少自从 JDK 1.8.0_162Collections.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 版本中得到解决。

您可以在此处查看源代码（感谢 eckes 的链接）。

于 2019-01-13T10:44:49.973 回答