Shell Sort es un tipo de ordenación por inserción y una versión más eficiente y mejorada de la ordenación por inserción directa que aprovecha al máximo dos características de la ordenación por inserción:
1) Muy eficiente cuando el tamaño de los datos es pequeño.
2) La complejidad temporal cuando los datos dados ya están ordenados es O (n).
Por lo tanto, la clasificación de Shell divide los datos en varios bloques cada vez para usar la clasificación por inserción, y luego combina estos bloques pequeños en bloques pequeños más grandes después de ordenarlos, y continúa usando la clasificación por inserción para fusionar continuamente bloques pequeños hasta el último fragmento pequeño. .
Aquí, cada división en varios bloques pequeños se controla mediante "incremento". Al principio, el incremento es grande, cercano a n/2, de modo que la división se acerca a n/2 bloques pequeños, y el "incremento" se realiza gradualmente. reducido”, finalmente reducido a 1.
Por ejemplo:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//Calcular el valor máximo de h inth=1; while(h<=data.length/3){h=h*3+1;} while(h > 0){for(inti=h;i<data.length;i+=h){if(data[i]<data[ih]){inttmp=data[i];intj=ih; while(j>= 0&&data [j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}// Calcular el siguiente valor h h= (h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t); .out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(datos);shellSort(data); datos);}}Los resultados de ejecución son los siguientes:
461958146958145698145689145689