Principios e implementación de ocho algoritmos de clasificación clásicos
Esta serie de artículos registra principalmente mis notas de estudio durante las vacaciones de verano. También estuve haciendo prácticas durante el verano y aprendí mucho durante ese tiempo. Crearé un blog separado para registrar cada aspecto del conocimiento. El encabezado es principalmente un enlace para iniciar un nuevo blog.
El algoritmo de clasificación de burbujas debería ser el primer algoritmo con el que todos entren en contacto y todos deberían comprender sus principios, pero aún quiero describir sus pasos en mi propio idioma:
Siga las reglas para calcular la complejidad del tiempo, elimine las constantes y el coeficiente más alto, la complejidad es O(N^2)
Clasificación de burbujas y su análisis de complejidad
Complejidad espacial Es la memoria que ocupa la variable temporal al intercambiar elementos
Dada una secuencia entera {6,1,2,3,4}, el resultado de cada finalización del bucle externo es:
Descubrimos que la clasificación fue exitosa después del primer bucle externo, pero el bucle aún continuaría, lo que provocaría una complejidad de tiempo innecesaria.
La clasificación de burbujas es una comparación de elementos adyacentes. Cuando los elementos adyacentes son iguales, no se intercambiarán. Por lo tanto, el algoritmo de clasificación de burbujas es un algoritmo estable.
La clasificación por inserción es una. mejora de la clasificación de burbujas
La idea de la clasificación por inserción es que la matriz esté parcialmente ordenada y luego la parte desordenada se inserte en la parte ordenada, como se muestra en la figura:
(La imagen viene de aquí)
La complejidad del espacio es la memoria que ocupa la variable temporal al intercambiar elementos
Hay dos opciones para optimizar el orden de inserción:
Estos dos algoritmos de clasificación se proporcionarán más adelante en el artículo
Dado que la clasificación por inserción también es una comparación de elementos adyacentes, no se producirá ningún intercambio cuando se encuentren elementos adyacentes iguales, ni habrá una relación relativa entre elementos iguales. La posición cambia
El principio es seleccionar el valor mínimo (valor máximo) de los elementos no clasificados y colocarlo después de los elementos ordenados
La complejidad del espacio es que al intercambiar elementos. memoria ocupada por variables temporales
La clasificación de selección es inestable, por ejemplo, 3 6 3 2 4, el primer elemento 3 y el cuarto elemento 2 se intercambiarán en el primer bucle externo, luego causará el relativo posición de los dos 3 en la secuencia original para cambiar
Hill sort es una versión mejorada del algoritmo de clasificación por inserción, por lo que también se llama algoritmo de clasificación por inserción Hill
Su principio Divide La secuencia se divide en varias subsecuencias (compuestas por elementos separados por un cierto incremento) y realiza la clasificación por inserción directa respectivamente; luego reduce sucesivamente los incrementos y continúa ordenando. Cuando toda la secuencia está básicamente en orden, todos los elementos se insertan. esa ordenación por inserción directa es muy eficiente cuando la secuencia está básicamente ordenada.
La descripción anterior es solo su principio. La implementación real puede ser la siguiente:
La eficiencia de la clasificación Hill depende de la selección de la brecha de valor incremental, que involucra matemáticas. es un problema sin resolver, pero la complejidad en algunas secuencias puede ser O (N 1.3). Por supuesto, la mejor es definitivamente O (N), y la peor es O (N 2)
La complejidad del espacio. es la memoria ocupada por la variable temporal al intercambiar elementos
La clasificación Hill no es solo una comparación de elementos adyacentes. Hay muchas comparaciones de salto y es inevitable que las posiciones relativas de los mismos elementos cambien. entonces la clasificación Hill es inestable
Para comprender la clasificación del montón, primero debes saber qué es un montón.
Características de un árbol binario:
Cuando el valor del nodo padre es siempre mayor que el valor del nodo hijo, es un montón máximo, en caso contrario es un mínimo; montón. La siguiente figura es un montón binario
Generalmente, se utiliza una matriz para representar un montón. El nodo padre del nodo con subíndice i es (i-1)/2; los nodos son (2 i + 1), (2 i + 2)
¿Cómo ajustar la secuencia de matriz dada en un montón de acuerdo con las propiedades del montón?
Aquí tomamos como ejemplo el establecimiento de un montón mínimo.
Obviamente, sus nodos hoja ya son un submontón legal, por lo que no hay necesidad de nodos secundarios al crear. ajustes de montón Para continuar, aquí solo necesita iniciar el ajuste de montón desde el nodo A[4] = 50, es decir, iniciar el ajuste de montón desde la posición (n/2 - 1) hacia arriba:
La complejidad del espacio es la memoria ocupada por la variable temporal al intercambiar elementos.
Dado que la clasificación del montón también intercambia datos en todos los ámbitos, las posiciones relativas entre los mismos elementos cambiarán. El algoritmo es inestable. Por ejemplo, 5 5 5, después de acumular la matriz, intercambie el elemento 5 en la parte superior del montón con el elemento 5 al final del montón, lo que hará que las posiciones relativas del primer 5 y el tercer 5 cambien.
La ordenación por combinación se basa en la operación de combinación. Un algoritmo de clasificación eficiente. Este algoritmo es una aplicación muy típica que utiliza el método divide y vencerás (Divide y vencerás).
La clasificación rápida debería ser un algoritmo que todo el mundo ve y oye con frecuencia, pero es difícil escribirlo. Espero que después de leer el método de cavar hoyos y completar números a continuación, puedas escribir y ordenar rápidamente.
El principio son solo unas pocas oraciones, pero en realidad no es tan simple. Adoptamos un método popular de cavar agujeros y rellenar el método de divide y vencerás.
Para la secuencia. : 72 6 57 88 60 42 83 73 48 85
La matriz se convierte en: 48 6 57 88 60 42 83 73 88 85
Repita los pasos anteriores, primero busque desde atrás hasta el frente, y luego desde el frente Buscar hacia atrás:
La matriz se convierte en: 48 6 57 42 60 72 83 73 88 85
Se puede ver que los números delante de. a[5] son menores que él, a[5] Los siguientes números son todos mayores que él.
Por lo tanto, simplemente repita los pasos anteriores para los dos subrangos a[0...4] y a[6...9]
La complejidad del espacio se debe principalmente al uso del espacio de pila causado por recursión:
La optimización de la clasificación rápida radica principalmente en la selección del número de referencia
La clasificación rápida también compara e intercambia datos a pasos agigantados, lo que puede conducir fácilmente a cambios en el posiciones relativas de los mismos elementos, por lo que la clasificación rápida es inestable
p>Como se mencionó anteriormente, la clasificación de búsqueda binaria es una clasificación de inserción mejorada. La diferencia es que cuando se busca la posición de inserción de un nuevo elemento en un. intervalo ordenado, para reducir el número de comparaciones y mejorar la eficiencia, se utiliza el algoritmo de búsqueda binaria para determinar la posición de inserción.
Para pasos específicos, deje que la matriz sea un [0...n]. :
Posición de inserción de búsqueda binaria, porque no se trata de encontrar valores iguales, sino de insertar la posición apropiada en función de la comparación, por lo que debe La posición de inserción no se conoce hasta que se encuentra el último elemento.
Peor complejidad temporal de la búsqueda binaria: cuando 2^X>=n, la consulta finaliza, por lo que el número de consultas es x, y x es igual a log2n (basado en 2, el logaritmo de n) . Es decir, O(log2n)
Por lo tanto, el número de comparaciones en la clasificación de búsqueda binaria es: x=log2n
Las operaciones de búsqueda binaria y clasificación por inserción que consumen mucho tiempo son: comparación + asignación de desplazamiento hacia atrás. La complejidad del tiempo es la siguiente:
La clasificación de búsqueda binaria se mueve cuando se intercambian datos. Cuando se inserta un valor igual, solo se insertará después de él, sin afectar la posición relativa entre los elementos iguales, por lo que es. estable
Clasificación por algoritmo clásico vernáculo
Clasificación por selección de clasificación por burbujas
Análisis de complejidad de clasificación rápida
Clasificación por inserción optimizada