¿Qué diferentes algoritmos de clasificación están disponibles en Java 6?

Question

Existen varios algoritmos de clasificación como inserstion sort, sort sort, sort de burbuja, etc. que a menudo se discuten en los libros de texto de informática. Dada una matriz de enteros u objetos, ¿hay una API de lenguaje Java 6 incorporada que me permita elegir aplicar un algoritmo de ordenamiento específico para ordenar la matriz en lugar de reinventar estas ruedas nuevamente? Si no está integrado en Java 6, ¿hay bibliotecas de código abierto que produzcan esta funcionalidad y qué son?

Answer 1

Los métodos Arrays.sort() usan una ordenación rápida en todas las matrices de tipo primitivo.

El algoritmo de clasificación es un quicksort sintonizado, adaptado de Jon L. Bentley y M. Douglas McIlroy, "Engineering a Sort Function", Software-Practice and Experience, vol. 23 (11) P. 1249-1265 (noviembre de 1993). Este algoritmo ofrece el rendimiento de n * log (n) en muchos conjuntos de datos que causan que otras soluciones rápidas se degraden a rendimiento cuadrático.

El método Collections.sort() utiliza un tipo de fusión. Este tipo también se usa en Arrays.sort(Object[]) y Arrays.sort(T[], Comparator<? super T>).

El algoritmo de clasificación es un mergesort modificado (en el que se omite la fusión si el elemento más alto en la sublista baja es menor que el elemento más bajo en la sublista alta). Este algoritmo ofrece un rendimiento n log (n) garantizado. Esta implementación vuelca la lista especificada en una matriz, ordena la matriz y repite la lista restableciendo cada elemento desde la posición correspondiente en la matriz. Esto evita el rendimiento n2 log (n) que resultaría de intentar ordenar una lista vinculada en su lugar.

Answer 2

Por lo general, no puede elegir (con la clasificación incorporada, de todos modos). La clase Collections proporciona un método sort que debería ser lo suficientemente eficiente para la mayoría de las necesidades.

Answer 3

Arrays.sort(int[] a) utiliza un quicksort ajustado.

Arrays.sort[Object[] a) utiliza un mergesort modificado.