Java: ordenar una ArrayList en su lugar

Question

En la biblioteca estándar de Java, ¿hay algún método que permita ordenar un ArrayList en su lugar, es decir, utilizando el almacenamiento adicional O(1)?

Collections.sort(List<T>) no cumple este requisito, ya que

vuelca la lista especificada en una matriz, ordena la matriz, e itera sobre la lista de restablecer cada elemento de la posición correspondiente en la matriz.

Si no hay nada en la biblioteca estándar, ¿qué bibliotecas de terceros se pueden usar para hacer esto?

Answer 1

Puede extraer la matriz subyacente (por ejemplo, reflejo) y realizar Arrays.sort (matriz, 0, list.size()) en ella.

Java 7 no copia la matriz en Arrays.sort() antes de ordenar la matriz. En Java 6 sí lo hace, lo que significa que Collections.sort() en Java 6 en realidad copia la matriz subyacente DOS VECES para realizar el ordenamiento.

Answer 2

Simplemente, no. Collections.sort() se creó para ordenar, parece que tiene que implementar el suyo. Para las listas, utilizaría Bubblesort, ya que solo intercambia dos elementos vecinos, lo que se puede hacer muy simple sin cambiar los intervalos.

Answer 3

Collections.sort() se hizo para trabajar con cualquier implementación de lista, y es por eso que no está funcionando en su lugar (fusionar LinkedList en su lugar es difícil y sacrifica la estabilidad).

Si está realmente preocupado por la clasificación en el lugar, tendrá que implementar su propia función de clasificación. Realmente no vale la pena su tiempo a menos que su lista sea muy larga.

Arrays.sort(Object[]) hace lo mismo mergesort y se llama internamente por Collections.sort() (al menos en OpenJDK)