La idea de la clasificación Hill
Idea del algoritmo de clasificación Hill: la clasificación Hill consiste en agrupar según el incremento del subíndice y utilizar el algoritmo de clasificación por inserción para ordenar cada grupo a medida que el incremento disminuye, cada grupo contiene más y más palabras clave. disminuye a 1, la secuencia completa se divide en un grupo y el algoritmo termina.
Tomemos como ejemplo la clasificación creciente. Los pasos básicos de la clasificación Hill son: seleccionar el incremento inicial gap=longitud/2 y continuar reduciendo el incremento en gap=gap/2 hasta que el incremento gap=. Hasta 1, cada cambio en el incremento dividirá la secuencia original en varios grupos y ordenará cada grupo por separado.
Cada vez que la ordenación por inserción se realiza mediante división incremental de grupos, los números pequeños se mueven macroscópicamente al frente y los números grandes se mueven hacia atrás. Finalmente, la secuencia ordenada final se inserta con el. brecha de incremento = 1.
Debido a las múltiples clasificaciones de inserción, sabemos que una clasificación de inserción es estable y no cambiará el orden relativo de los mismos elementos. Sin embargo, en diferentes procesos de clasificación de inserción, los mismos elementos pueden moverse en su respectiva inserción. sorts. y eventualmente su estabilidad se verá afectada, por lo que la clasificación de shell es inestable.
Historia del desarrollo
La clasificación Hill lleva el nombre de su diseñador, Donald Shell. El algoritmo se derivó del artículo "Una clasificación de alta velocidad" publicado por Hill en 1959. Procedimiento".
En 1961, Marlene Metzner Norton, una programadora de IBM, implementó por primera vez el algoritmo de clasificación Hill utilizando programación en lenguaje FORTRAN. En su programa, se utiliza un método simple y efectivo para establecer la secuencia de incremento requerida para la clasificación Hill: el primer incremento es la mitad del número de registros a ordenar, luego se reduce a la mitad sucesivamente y el último incremento es 1.
El algoritmo más tarde se conoció como el algoritmo Shell-Metzner. El propio Metzner dijo en un correo electrónico en 2003: "No hice nada para este algoritmo y mi nombre no debería aparecer en el nombre".