La clasificación de Shell es un algoritmo de clasificación muy "mágico". Se dice que es "mágico" porque nadie puede explicar claramente lo que realmente puede lograr su rendimiento. Clasificación de la colina porque DL. Shell llevó el nombre de que se propuso en 1959. Dado que el automóvil Hoare propuso una clasificación rápida en 1962, generalmente se usa una clasificación rápida porque es más simple. Sin embargo, muchos matemáticos todavía buscan incansablemente la mejor complejidad de la clasificación de las colinas. Como programadores comunes, podemos aprender las ideas de Hill.
Por cierto, antes de que apareciera la clasificación de Hill, había una vista general en el mundo de las computadoras de que "los algoritmos de clasificación no pueden romper o (N2)". La aparición de la clasificación de Hill rompió esta maldición, y pronto, los algoritmos como la clasificación rápida se lanzaron uno tras otro. En este sentido, la clasificación de Hill nos lleva a una nueva era.
Descripción general del algoritmo/Ideas
La propuesta de clasificación de colinas se basa principalmente en los siguientes dos puntos:
1. El algoritmo de clasificación de inserción puede lograr aproximadamente la complejidad O (n) y extremadamente eficiente cuando la matriz se ordena básicamente.
2. Sin embargo, la clasificación de inserción solo puede mover datos en un bit a la vez, y el rendimiento se deteriorará rápidamente cuando la matriz es grande y básicamente desordenada.
Según esto, podemos usar un método de clasificación de inserción agrupado, que es el método específico: (tome una matriz de 16 elementos como ejemplo)
1. Seleccione un Delta de incremento, que es mayor que 1, y seleccione la subarray de la matriz mediante este incremento para la clasificación de inserción directa. Por ejemplo, si se selecciona el incremento 5, se clasifican los elementos con los subíndices 0, 5, 10, 15.
2. Mantenga el delta de incremento y mueva el primer elemento a su vez para su inserción y clasificación hasta que se complete la ronda. Para el ejemplo anterior, las matrices [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] están ordenadas a su vez.
3. Reduzca el incremento y repita el proceso anterior continuamente hasta que el incremento disminuya a 1. Obviamente, la última vez es el tipo de inserto directo.
4. La clasificación se completa.
Como se puede ver en lo anterior, el incremento disminuye constantemente, por lo que la clasificación de la colina nuevamente se llama "clasificación de incremento reducido".
Implementación del código
sort de paquete; public class ShellSortTest {public static int count = 0; public static void main (string [] args) {int [] data = new int [] {5, 3, 6, 2, 1, 9, 4, 8, 7}; imprimir (datos); shellsort (datos); imprimir (datos); } public static void shellsort (int [] data) {// Calcule el valor H máximo int h = 1; while (h <= data.length / 3) {h = h * 3 + 1; } while (h> 0) {for (int i = h; i <data.length; i += h) {if (data [i] <data [i - h]) {int tmp = data [i]; int j = i - h; while (j> = 0 && data [j]> tmp) {data [j + h] = data [j]; j -= h; } datos [j + h] = tmp; imprimir (datos); }} // Calcule el siguiente valor H h = (h - 1) / 3; }} public static void print (int [] data) {for (int i = 0; i <data.length; i ++) {system.out.print (data [i]+"/t"); } System.out.println (); }} Resultados de ejecución:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Rendimiento del algoritmo/complejidad
Las secuencias incrementales ordenadas por la colina se pueden tomar en cualquier momento, y el único requisito es que la última debe ser 1 (porque es necesario asegurarse de que se ordene por 1). Sin embargo, la diferente selección de secuencias tendrá un gran impacto en el rendimiento del algoritmo. El código anterior demuestra dos incrementos.
Recuerde: ¡es mejor no tener factores comunes que no sea 1 por cada dos elementos en la secuencia incremental! (Obviamente, clasificar por 2 en secuencia no es muy significativo).
A continuación se muestran algunas secuencias incrementales comunes.
El primer incremento es el inicialmente propuesto por Donald Shell, es decir, el pliegue se reduce a 1. Según la investigación, utilizando incrementos de la colina, la complejidad del tiempo sigue siendo O (N2).
El segundo incremento Hibbard: {1, 3, ..., 2^K-1}. La complejidad del tiempo de esta secuencia incremental es aproximadamente O (n^1.5).
El tercer incremento de Sedgewick Incremento: (1, 5, 19, 41, 109, ...), que genera una secuencia 9*4^i - 9*2^i + 1 o 4^i - 3*2^i + 1.
Estabilidad del algoritmo
Todos sabemos que la clasificación de inserción es un algoritmo estable. Sin embargo, la clasificación de shell es un proceso de múltiples inserciones. En una inserción, podemos asegurar que el orden de los mismos elementos no se mueva, pero en múltiples inserciones, es completamente posible que los mismos elementos se muevan en diferentes rondas de inserción, y la estabilidad finalmente se destruye. Por lo tanto, la clasificación de concha no es un algoritmo estable.
Algoritmo escenarios aplicables
Aunque la clasificación de la carcasa es rápida, es una clasificación de inserción después de todo, y su orden de magnitud no es tan bueno como la estrella ascendente: la clasificación rápida O (NN) es rápida. La clasificación de concha no es un buen algoritmo frente a una gran cantidad de datos. Sin embargo, es completamente posible usar datos pequeños y medianos.