Java:就地对 ArrayList 进行排序

Question

在 Java 的标准库中，有没有一种方法可以对 ArrayList 进行排序？到位，即使用 O(1)额外的存储空间？

Collections.sort(List<T>) 不满足这个要求，因为它

dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array.

如果标准库中什么都没有，有哪些第三方库可以做到这一点？

Answer 1

您可以提取底层数组(例如反射)并对其执行 Arrays.sort(array, 0, list.size())。

Java 7 在对数组进行排序之前不会复制 Arrays.sort() 中的数组。在 Java 6 中，这意味着 Java 6 中的 Collections.sort() 实际上复制了底层数组 TWICE 来执行排序。