¿Cuál es el algoritmo de clasificación más rápido?
Timsort es un algoritmo de clasificación escrito originalmente para Python en 2001 por Tim Peters. Desde su invención, se ha utilizado como algoritmo de clasificación predeterminado en Python, Java, la plataforma Android y GNU Octave.
Para obtener una descripción detallada de este algoritmo, consulte http://svn.python.org/projects/python/trunk/Objects/listsort.txt
Vea cómo se compara con el otros dos Comparación de algoritmos de clasificación eficientes
En comparación, TimSort tiene el mejor rendimiento. Lo mejor es una combinación de promedio y peor caso. Cuando la cantidad de datos es relativamente pequeña (<= 64), utiliza directamente la clasificación por inserción; de lo contrario, utiliza la clasificación por combinación + búsqueda binaria para mejorar la eficiencia de la clasificación.
A continuación se muestra un ejemplo de clasificación de naipes, compare. el rendimiento de clasificación por burbujas, clasificación por inserción, clasificación rápida, clasificación normalizada y TimSort:
Luego clasifique 1000 barajas de cartas en orden aleatorio, los resultados son los siguientes
Sin embargo, TimSort tiene un problema La descripción de JDK7 menciona que tiene los siguientes problemas de compatibilidad
Por lo tanto, después de JDK7, los comparadores que implementan la interfaz Comparable deben cumplir con las siguientes tres restricciones:
1) Reflexividad: el resultado de la comparación de xey es opuesto al resultado de la comparación de yey x.
2) Transitividad: x>y, y>z, luego x>z.
3) Simetría: x=y, luego el resultado de la comparación de x, z e y. El resultado de la comparación de ,z es el mismo.
Si comparas x,z, entonces comparar y,z tiene el mismo resultado que comparar y,z.
Si su método de comparación viola las restricciones anteriores, entonces puede no utilizar este nuevo algoritmo y volver a la ordenación por combinación tradicional
o modificar su comparador para cumplir con las restricciones anteriores.
Aquí tienes dos ejemplos