Método de clasificación de conchas
Idea básica:
Tome un número entero d1 menor que n como primer incremento y luego divida todos los registros del archivo en grupos d1 . Todos los registros cuya distancia sea múltiplo de dl se agrupan. Primero realice la clasificación por inserción directa en cada grupo; luego, tome el segundo incremento d2 Este método es esencialmente un método de inserción de grupos. El proceso de clasificación de Shell en el ejemplo dado Supongamos que el archivo a ordenar tiene 10 registros y las palabras clave son las siguientes: 49 , 38, 65 , 97, 76, 13, 27, 49, 55, 04. Los valores de la secuencia incremental son los siguientes: 5, 3, 1 Proceso de clasificación Demostración en forma de simulación animada. Implementación del algoritmo de clasificación de Shell 1. Descripción del algoritmo de centinela no supervisado void ShellPass(SeqList R, int d) { //Una clasificación en clasificación Hill, d es el incremento actual for(i=d+1;i<=n; i++) //Coloque R[d+1..n] respectivamente Inserte el área de clasificación actual de cada grupo if(R[i].key R[0]=R[i];j = i-d; //R[0] es solo una unidad de tránsito, no un centinela do {//Encuentra la posición de inserción de R[i] R[ j +d] = R[j]; //Grabar hacia atrás j=j-d //Buscar el registro anterior } while(j>0&&R[ 0]. key R[j+d]=R[0]; //inserta R[i] en la posición correcta }// endif }//ShellPass void ShellSort(SeqList R) { int increment=n; incrementar el valor inicial, también podría establecer n>0 do { increment= increment/3+1; //buscar el siguiente incremento ShellPass( R, incremento); //un viaje al orden de inserción de Shell con incremento } while(increment>1) } Incremento=n>. Nota: Cuando el incremento d = 1, ShellPass e InsertSort son básicamente iguales, excepto que no hay centinela y se agrega una condición de bucle "j>0" en el bucle interno para evitar que el subíndice cruzando la línea. 2. Algoritmo de clasificación de shell con centinelas Para algoritmos específicos, consulte la referencia [12] Análisis de algoritmos 1. Incrementar selección de secuencia El tiempo de ejecución de la ordenación de Shell depende de la secuencia delta. ****, una buena secuencia incremental debe tener las siguientes características: ①El último incremento debe ser 1; ②Debemos hacer todo lo posible para evitar situaciones en las que los valores de la secuencia (especialmente los valores adyacentes) son múltiplos entre sí. Hasta ahora, algunas personas han dado mejores resultados a través de una gran cantidad de experimentos: cuando n es grande, el número de comparaciones y desplazamientos es aproximadamente entre nl.25 y 1.6n1.25. 2. El rendimiento temporal de la clasificación Shell es mejor que el de la clasificación por inserción directa. Las razones por las que el rendimiento temporal de la clasificación Shell es mejor que el de la clasificación por inserción directa: ① Cuando la base del archivo Cuando el metaestado está básicamente en orden, la clasificación por inserción directa requiere menos comparaciones y menos movimientos. ②Cuando el valor de n es pequeño, la diferencia entre n y n2 también es pequeña, es decir, la mejor complejidad temporal de la ordenación por inserción directa es O (n) y la peor complejidad temporal es 0 (n2 ). La diferencia entre ellos es muy pequeña. ③Al comienzo de la clasificación Hill, el incremento es grande, la cantidad de grupos es grande y la cantidad de registros en cada grupo es pequeña, por lo que la velocidad de inserción directa en cada grupo es más rápida, y luego el incremento di disminuye gradualmente, el número de grupos disminuye gradualmente y el número de registros en cada grupo aumenta gradualmente. Sin embargo, dado que los archivos se han ordenado según di-1 como distancia, los archivos se acercan más a un estado ordenado. el nuevo proceso de clasificación también es más rápido. Por lo tanto, la clasificación Hill es mucho más eficiente que la interpolación directa. 3. Estabilidad La clasificación por colinas es inestable. Vea el ejemplo anterior donde el orden relativo de dos palabras clave idénticas 49 cambia antes y después de la clasificación.