为什么会Collections.sort()
创建一个额外的对象数组并对数组执行 Tim 排序,然后最终将排序后的数组复制回List
对象?我知道这个调用针对 进行了优化LinkedList
,但我们不会失去性能ArrayList
吗?
我们本可以避免2n
将其转换为对象数组并将它们添加回列表中的操作数。我知道这些额外的操作不会影响整个排序操作的 Big-O,但我相信它可以针对ArrayList
.
我在这里错过了什么吗?我只是想理解为什么架构是这样布局的。谢谢。
为什么会Collections.sort()
创建一个额外的对象数组并对数组执行 Tim 排序,然后最终将排序后的数组复制回List
对象?我知道这个调用针对 进行了优化LinkedList
,但我们不会失去性能ArrayList
吗?
我们本可以避免2n
将其转换为对象数组并将它们添加回列表中的操作数。我知道这些额外的操作不会影响整个排序操作的 Big-O,但我相信它可以针对ArrayList
.
我在这里错过了什么吗?我只是想理解为什么架构是这样布局的。谢谢。
您正在查看较旧的 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 的链接)。