integers - sort arraylist double java

Java: ordenando una ArrayList en su lugar

Question

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

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

vuelca la lista especificada en una matriz, ordena la matriz y repite la lista restableciendo cada elemento de la posición correspondiente en la matriz.

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

Answer 1

Puede extraer la matriz subyacente (por ejemplo, reflexión) 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 cubos.

Answer 3

Collections.sort() se creó para funcionar con cualquier implementación de List, y es por eso que no funciona (fusionar LinkedList en su lugar es difícil y sacrifica la estabilidad).

Si realmente te preocupa organizar en el lugar, tendrás que implementar tu 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 el mismo mergesort y es llamado internamente por Collections.sort() (al menos en openjdk)