Código del algoritmo de clasificación rápida
El algoritmo de clasificación es uno de los algoritmos más básicos en "Estructuras de datos y algoritmos".
Los algoritmos de clasificación se pueden dividir en clasificación interna y clasificación externa. La clasificación interna clasifica los registros de datos en la memoria, mientras que la clasificación externa se debe a que la cantidad de datos ordenados es muy grande y no puede acomodar todos los registros ordenados al mismo tiempo. Se requiere acceso a la memoria externa durante el proceso de 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 normalizada, clasificación rápida, clasificación en montón, clasificación por base, etc. Resuma con una imagen:
Haga clic en la imagen a continuación para verla más grande:
Acerca de la complejidad del tiempo
Orden cuadrado ( O( n2)) Ordenar varios tipos de clasificación simple: inserción directa, selección directa y clasificación por burbujas.
Clasificación logarítmica lineal (O(nlog2n)) clasificación rápida, clasificación en montón y combinación
clasificación O(n1+§)), § está entre 0 y 1 constante. Clasificación Hill
Clasificación de rango lineal (O(n)) Clasificación Radix, además de clasificación por cubo y caja.
Acerca de 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.
Algoritmos de clasificación inestables: clasificación por selección, clasificación rápida, clasificación Hill, clasificación en montón.
Explicación de términos: n: tamaño de datos k: número de "depósitos" In-place: ocupa memoria constante, no ocupa memoria adicional In-place: ocupa memoria adicional Estabilidad: 2 claves iguales después de ordenar The el orden es el mismo que antes de ordenar
Contiene el siguiente contenido: 1. Clasificación por burbujas 2, Clasificación por selección 3, Clasificación por inserción 4, Clasificación por colinas 5, Clasificación por suma 6, Clasificación rápida 7, Clasificación por montón 8, Conteo Ordenar 9. Ordenar por cubos 10. Ordenar base
El algoritmo de ordenación incluye lo siguiente:
Algoritmo de ordenación de columnas
Algoritmo de ordenación de columnas
Clasificación de burbujas También es un algoritmo de clasificación simple e intuitivo. Itera sobre la matriz que se va a ordenar, comparando dos elementos cada vez e intercambiándolos si están en el orden incorrecto. El proceso de acceso a la matriz se repite hasta que no se necesitan más intercambios, lo que significa que la matriz está ordenada. Los elementos más pequeños "flotarán" lentamente hacia la parte superior de la matriz mediante el intercambio, de ahí el nombre del algoritmo.
Algoritmo de clasificación por selección
La clasificación por selección es un algoritmo de clasificación simple e intuitivo No importa cuáles sean los datos, su complejidad temporal es O (n?). Entonces, cuando lo use, cuanto menor sea el tamaño de los datos, mejor. Probablemente la única ventaja es que no ocupa espacio de memoria adicional.
Algoritmo de ordenación por inserción
La implementación del código de ordenación por inserción no es tan simple como la ordenación por burbujas o por selección, pero el principio de ordenación por inserción es el más fácil de entender, porque cualquiera que tenga Los juegos de póquer jugados pueden entenderlo en segundos. La clasificación por inserción es uno de los algoritmos de clasificación más simples e intuitivos. Su principio de funcionamiento es construir una secuencia ordenada de datos desordenados, escanear hacia adelante y hacia atrás en la secuencia ordenada, encontrar la posición adecuada e insertarla.
Algoritmo de clasificación Hill
La clasificación Hill, también conocida como algoritmo de clasificación creciente descendente, es una versión más eficiente y mejorada de la clasificación por inserción. Sin embargo, la clasificación Hill es un algoritmo de clasificación inestable.
Ordenación por combinación
Ordenación por combinación es un algoritmo de clasificación eficiente 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 comparaciones Ο(nlogn). En el peor de los casos, se requieren comparaciones Ο(n2), pero esto es poco común. De hecho, la ordenación rápida es generalmente mucho más rápida que otros algoritmos Ο(nlogn) porque su bucle interno se puede implementar de manera eficiente en la mayoría de las arquitecturas.
Algoritmo de clasificación de montón
La clasificación de montón es un algoritmo de clasificación diseñado para utilizar la estructura de datos del montón. Un montón es una estructura que se aproxima a un árbol binario completo y satisface las propiedades de un montón: es decir, el valor clave o índice de un nodo hijo siempre es menor (o mayor) que su nodo padre. La clasificación de montón se puede describir como una clasificación de selección que utiliza el concepto de montón para ordenar.
Algoritmo de ordenación por conteo
El núcleo de la ordenación por conteo es convertir los valores de datos de entrada en valores clave almacenados en un espacio de matriz abierto adicional. Como ordenación por complejidad de tiempo lineal, la ordenación por conteo requiere que los datos de entrada sean números enteros con un rango definido.
Algoritmo de clasificación por cubos
La clasificación por cubos es una versión mejorada de la clasificación por conteo. Utiliza mapeo de funciones y la clave para la eficiencia radica en cómo determinar esta función de mapeo.
Algoritmo de clasificación Radix
La clasificación Radix es un algoritmo de clasificación de enteros no comparativo que corta un número entero en diferentes números por dígitos y luego compara cada número por separado. La clasificación por base no es exclusiva de los números enteros, ya que los números enteros también pueden expresar cadenas (como nombres o fechas) y números de punto flotante en ciertos formatos.