Red de conocimiento informático - Conocimiento del nombre de dominio - Lenguaje C de clasificación rápida

Lenguaje C de clasificación rápida

Los algoritmos de clasificación son uno de los algoritmos más básicos en estructuras y algoritmos de datos.

Los algoritmos de clasificación se pueden dividir en clasificación interna y clasificación externa. La clasificación interna se refiere a la clasificación de registros de datos en la memoria. La clasificación externa significa que debido a que los datos ordenados son muy grandes y no pueden acomodar todos los registros ordenados a la vez, es necesario acceder al almacenamiento externo durante la clasificación. Los algoritmos de clasificación interna comunes incluyen: clasificación por inserción, clasificación Hill, clasificación por selección, clasificación por burbujas, clasificación por fusión, clasificación rápida, clasificación en montón, clasificación por base, etc. Resumámoslo con una imagen:

Haga clic en la imagen a continuación para verla más grande:

Acerca de la clasificación simple con complejidad de tiempo al cuadrado (O (n2)): inserción directa, directa selección y riesgo Clasificación de burbujas.

Clasificación de orden logarítmico lineal (O(nlog2n)), clasificación rápida, clasificación de montón y clasificación de fusión

O (n1+0)), que es una constante entre 0 y 1; . Clasificación Schell

Orden lineal (O(n)) clasificación por base, además de clasificación por cubos y contenedores.

Sobre la estabilidad

Algoritmos de clasificación estables: clasificación por burbujas, clasificación por inserción, clasificación por fusión y clasificación por base.

No existen algoritmos de clasificación estables: clasificación por selección, clasificación rápida, clasificación Hill y clasificación en montón.

Explicación del término:

n: Escala de datos k: Número de "depósitos" en el lugar: Ocupa memoria constante, no ocupa memoria adicional Fuera del lugar: Ocupa memoria adicional Estabilidad: Después de ordenar El orden de dos valores clave iguales es el mismo que antes de ordenar, incluido lo siguiente:

1 Orden de burbuja 2. Orden de selección 3. Orden de inserción 4. Orden de colina 5. Orden de combinación 6. Los algoritmos de clasificación rápida 7, clasificación de montón 8, clasificación de conteo 9, clasificación de cubo 10 y clasificación de Radix incluyen los siguientes detalles:

Algoritmo de clasificación de burbujas

La clasificación de burbujas también es simple e intuitiva. algoritmo de clasificación. Itera sobre la serie a ordenar, compara dos elementos a la vez e intercambiándolos si están en el orden incorrecto. El acceso a la serie se repite hasta que no es necesario ningún intercambio, es decir, la serie queda ordenada. El algoritmo recibe su nombre del hecho de que los elementos más pequeños "flotan" lentamente hasta la parte superior de la secuencia mediante el intercambio.

Algoritmo de clasificación selectiva

La clasificación selectiva es un algoritmo de clasificación simple e intuitivo. No importa qué datos se ingresen, la complejidad del tiempo es O (n?). Por tanto, a la hora de utilizarlo, cuanto menor sea la cantidad de datos, mejor. La única ventaja puede ser que no ocupa espacio de memoria adicional.

Algoritmo de ordenación por inserción

Aunque la implementación del código de ordenación por inserción no es tan simple y tosca como la ordenación por burbuja y la ordenación por selección, su principio debería ser el más fácil de entender, porque aquellos que tienen Jugado al poker. Todo el mundo debería poder entenderlo al instante. La clasificación por inserción es el algoritmo de clasificación más simple e intuitivo. Su principio de funcionamiento es escanear los datos no clasificados de atrás hacia adelante en la secuencia ordenada, encontrar la posición correspondiente e insertarlos.

Algoritmo de clasificación en colina

La clasificación en colina, también conocida como algoritmo de clasificación incremental descendente, es una versión más eficiente y mejorada de la clasificación por inserción. Pero la clasificación Hill es un algoritmo de clasificación inestable.

Algoritmo de clasificación por combinación

La clasificación por combinación es un algoritmo de clasificación eficaz basado en operaciones de combinación. Este algoritmo es una aplicación muy típica de divide y vencerás.

Algoritmo de clasificación rápida

La clasificación rápida es un algoritmo de clasificación desarrollado por Tony Hall. En promedio, ordenar n elementos requiere o comparaciones (NLOGN). En el peor de los casos, se requiere una comparación o(N2), pero esto es poco común. De hecho, la ordenación rápida es generalmente mucho más rápida que otros algoritmos o (NLOGN) porque su bucle interno se puede implementar de manera eficiente en la mayoría de las arquitecturas.

Algoritmo Heapsort

Heapsort se refiere a un algoritmo de clasificación diseñado utilizando la estructura de datos del montón. El montón es una estructura de árbol binario aproximadamente completa que satisface las propiedades del montón: es decir, el valor clave o índice de un nodo secundario siempre es menor (o mayor) que su nodo principal. Se puede decir que la clasificación de montón es una clasificación selectiva que utiliza el concepto de montón.

Algoritmo de ordenación por conteo

El núcleo de la ordenación por conteo es convertir los valores de datos de entrada en claves y almacenarlos en un espacio de matriz adicional. Como clasificación de complejidad de tiempo lineal, la clasificación por conteo requiere que los datos de entrada sean un número entero dentro de un cierto rango.

Algoritmo de clasificación de cubos

La clasificación de cubos es una versión mejorada de la clasificación por conteo. Utiliza la relación de mapeo de funciones, y la clave para la eficiencia radica en la determinación de esta función de mapeo.

Algoritmo de clasificación por Radix

La clasificación por Radix es un algoritmo de clasificación de enteros no comparativo. Su principio es cortar el número entero en diferentes números según la cantidad de dígitos y luego comparar cada dígito por separado. Debido a que los números enteros también pueden representar cadenas (como nombres o fechas) y números de punto flotante en formatos específicos, la ordenación por base no solo funciona con números enteros.