clase funcional efectiva
Pregunta
estoy programando una función para una TI-Nspire , de modo que pueda 't utilizar las órdenes internas desde el interior de una función. ¿Cuál es el algoritmo más eficiente en general para clasificar una lista de números sin necesidad de modificar la propia lista? (Recursividad y la lista de reparto son presa fácil, como es el uso general de las matemáticas.)
Solución
por fusión es sencillo, simple, eficiente y estable:. Divide la lista, más o menos de forma recursiva, y combinar los resultados
Para ser más específicos, mergesort toma O (N log N), que es asintóticamente óptima. Además, en la práctica (con ambos algoritmos modificados para sublistas especie cortos con una especie de propósito especial), mergesort puede ser un competidor cerca de la clasificación rápida modificados utilizados en los / C ++ bibliotecas C estándar.
Editar:. A diferencia de en el lugar géneros como la clasificación rápida y ordenación por inserción, mergesort requiere memoria auxiliar, y es más fácil de poner en práctica mediante la copia en lugar de intercambiar
Otros consejos
Timsort se utiliza en Python y Java SE 7. Toma lo mejor de fusión especie y la ordenación por inserción. La ordenación por inserción es O (n ^ 2), pero con pequeñas listas de números es más rápido que el de combinación de tipo!
Así que usted puede utilizar esto como un algoritmo de clasificación genérica como se indica aquí