Resumen del algoritmo de clasificación O(n2)
Definición: La clasificación por selección es un algoritmo de clasificación simple e intuitivo. Funciona seleccionando el más pequeño (o más grande) de los elementos de datos que se ordenarán cada vez y almacenándolo al comienzo de la secuencia hasta que todos los elementos de datos que se ordenarán estén ordenados.
Ilustración:
Implementación del código fuente:
Análisis: a través de la ilustración y el código fuente de la clasificación selectiva, podemos ver que la clasificación selectiva requiere dos bucles, el Lo más importante es ejecutar completamente el bucle interno cada vez que se ejecuta. ¿Hay alguna manera de evitar que el bucle interno se ejecute cada vez? Definitivamente, se llama clasificación de burbujas.
Definición: La clasificación de burbujas es un algoritmo de clasificación simple en informática. Recorre repetidamente la columna de elementos que se van a ordenar, comparando cada vez dos elementos adyacentes e intercambiándolos si están en el orden incorrecto (por ejemplo, de mayor a menor, de la primera letra de la A a la Z). La clasificación de elementos se repite hasta que no es necesario intercambiar elementos adyacentes, lo que significa que los elementos se han ordenado.
Ilustración:
Implementación del código fuente:
Análisis: Se puede ver en la ilustración y el código fuente que, en términos del número de ejecuciones, la clasificación por burbujas es mejor que la selección. El número de ciclos de clasificación debería ser menor. ¿Significa esto que la ordenación por burbujas será mejor que la ordenación por selección en términos de complejidad temporal si los elementos de la matriz que se van a ordenar encajan mejor? ¿Es este realmente el caso?
De hecho, este no es el caso. Después de muchas pruebas y verificaciones, la complejidad temporal de la clasificación de burbujas es básicamente inferior a la de la clasificación por selección. En el código fuente, podemos ver claramente que, aunque la clasificación por burbujas se ejecuta menos veces que la clasificación por selección, el número de intercambios aumenta significativamente. Y si tiene un conocimiento básico del principio de ejecución de instrucciones de los programas de computadora, siempre que lo haga. Debe saber que la acción de intercambio requiere más instrucciones que la acción de asignación. Entonces, al final del día, la clasificación por burbujas tiene una mayor complejidad temporal que la clasificación por selección en la mayoría de los casos.
Dado que la operación de intercambio consume tantos recursos, ¿hay alguna manera de reducir o incluso eliminar la operación de intercambio mientras se reduce el número de ejecuciones del bucle interno? Este es el tipo de inserción.
Definición: La operación básica de ordenación por inserción es insertar un dato en los datos ordenados para obtener un dato nuevo más uno ordenado, es decir, cada paso clasifica un registro según el código clave El tamaño de el valor se inserta en la posición correspondiente del archivo ordenado anterior hasta que se completen todas las inserciones.
Ilustración:
Implementación del código fuente:
Análisis: Como se puede ver en la ilustración y el código fuente, la ordenación por inserción (optimización) no tiene intercambio. operación, y para el bucle interno, si el elemento a ordenar es un valor relativamente grande, el bucle interno se ejecutará muy pocas veces. Por lo tanto, si los datos originales están básicamente ordenados, utilizar la ordenación por inserción será muy eficaz. ¿Se puede optimizar aún más el algoritmo de clasificación en el nivel O (n2)? Si es así, ¿en qué áreas se puede optimizar? Aquí, presentaremos la clasificación Hill, que es un algoritmo de clasificación propuesto para permitir que los algoritmos de clasificación rompan el límite de complejidad temporal O (n2).
Definición: La clasificación Shell es una clasificación por inserción, también conocida como clasificación incremental descendente. Es una versión más eficiente y mejorada del algoritmo de clasificación por inserción directa.
La idea básica de este algoritmo es agrupar registros de acuerdo con un determinado incremento de subíndice, y cada grupo se ordena mediante el algoritmo de clasificación por inserción directa a medida que el incremento disminuye gradualmente, cada grupo contiene más y más palabras clave Cuando el incremento se reduce; a 1, se agrupa todo el archivo y finaliza el algoritmo de clasificación.
Para la clasificación Hill, lo más crítico es cómo elegir el incremento. Cómo determinar este incremento es en realidad una cuestión matemática que hasta el momento no tiene respuesta. Sin embargo, tras una gran cantidad de experimentos, se obtuvo un valor empírico. La fórmula de selección de incrementos que damos como ejemplo es: h = 3 *?h 1, consulte la ilustración a continuación.
Ilustración:
Implementación del código fuente:
Análisis: a partir del ordenamiento por inserción, sabemos que las filas insertadas en la matriz a ordenar están básicamente ordenadas en orden. La eficiencia del algoritmo de clasificación por inserción será muy alta, por lo que podemos pensar que la idea final de la clasificación Hill es: primero insertar la secuencia completa de registros que se van a ordenar directamente en varias subsecuencias para ordenar, y luego "básicamente insertar " los registros en toda la secuencia "Ordenar en orden. Los registros de la secuencia están "sustancialmente ordenados", ordenados según la clasificación de inserción directa.
La razón por la que la clasificación Hill es tan eficiente es que su idea básica es realmente muy útil: cuando h es grande, la cantidad de elementos que deben moverse para cada clasificación de elementos de datos es muy pequeña, pero la distancia que recorren los elementos de datos es muy pequeña. Esto es muy eficiente. A medida que h disminuye, la cantidad de elementos que deben moverse por clasificación aumenta, pero los elementos de datos ahora están más cerca de sus posiciones finales después de la clasificación, lo que es más eficiente para la clasificación por inserción. Es la combinación de estas dos cosas lo que hace que Hill sort sea tan eficiente.
Se puede decir que la selección de incrementos es una especie de magia. En el borrador original de Hill, sugirió un espaciamiento inicial de N/2, que simplemente dividía cada viaje de clasificación a la mitad. Sin embargo, resulta que este no es el mejor arreglo. Si bien este enfoque todavía funciona mejor que la ordenación por inserción para la mayoría de los números, este enfoque a veces reduce el tiempo de ejecución a O(N2) y no es más eficiente que la ordenación por inserción. Generalmente se cree que los números en una secuencia de intervalos deben ser coprimos: es decir, no tienen otra convención que 1. Esta restricción hace que sea más probable que cada tipo conserve los efectos del tipo anterior. La ineficiencia inicial de Hill al utilizar el intervalo N/2 se debió a que no siguió este criterio.
Resumen: lo anterior es una descripción de cuatro algoritmos clásicos de clasificación de nivel O (n2). De hecho, la clasificación por selección y la clasificación por burbujas básicamente no se utilizan en diversas situaciones porque básicamente no existen escenarios de uso. Para la clasificación por inserción y la clasificación Hill, cuando los datos a ordenar están básicamente en orden, todavía existen escenarios de uso. Por ejemplo, algunos registros almacenados en archivos de registro pueden tener la mayoría de los registros ordenados según el tiempo, pero solo en algunos casos. En casos extremos, algunos registros se almacenan tarde, lo que genera inconsistencia temporal.
Soy Xu Jianhang, este es mi artículo número 31, bienvenidos a todos a unirse a la comunidad 007, escribir un artículo en siete días, escribir juntos durante siete años e ir juntos a la Antártida en siete años.