Características de los algoritmos de clasificación utilizados habitualmente y de los modelos de datos lógicos
Los algoritmos de clasificación generalmente consideran dos aspectos, a saber, la complejidad del tiempo y la complejidad del espacio.
La clasificación por inserción y la clasificación por burbujas son clasificaciones simples. Su complejidad de tiempo promedio es O (n ^ 2), el peor de los casos es O (n ^ 2) y el espacio de almacenamiento auxiliar es O (1).
La complejidad temporal promedio de la clasificación rápida es O(nlogn), el peor de los casos es O(n^2) y el espacio de almacenamiento auxiliar es O(logn)
El promedio complejidad temporal de la clasificación por fusión La complejidad temporal es O (nlogn), en el peor de los casos es O (nlogn) y el espacio de almacenamiento auxiliar es O (n)
La complejidad temporal promedio de la clasificación del montón es O (nlogn), en el peor de los casos es O (nlogn) y el espacio de almacenamiento auxiliar es O (1)
La complejidad temporal promedio de la clasificación Base es O (d (n rd)), y en el peor de los casos es O(d(n rd)), el espacio de almacenamiento auxiliar es O(rd), donde d es el número de palabras clave y rd es el número de valores de palabras clave.
En términos de rendimiento promedio, la clasificación rápida tiene el mejor rendimiento y requiere menos tiempo, pero el peor rendimiento de la clasificación rápida no es tan bueno como la clasificación en montón y la clasificación por combinación. El último resultado es que cuando n es grande, la clasificación sumergida lleva menos tiempo que la clasificación en montón, pero requiere más espacio de almacenamiento auxiliar.
Al comparar estos métodos desde una perspectiva de estabilidad, la clasificación básica es una clasificación interna estable, y todas las clasificaciones simples con una complejidad temporal de O(n^2) son estables. Sin embargo, la clasificación rápida, la clasificación por combinación, la clasificación en montón y otros métodos de clasificación con mejor rendimiento temporal son todos inestables.
Para conocer las ideas específicas de cada clasificación, el autor puede buscar en Baidu. Hay entradas correspondientes en la Enciclopedia Baidu.