Shell Sort é um tipo de classificação por inserção e uma versão mais eficiente e aprimorada da classificação por inserção direta que faz uso total de duas características da classificação por inserção:
1) Muito eficiente quando o tamanho dos dados é pequeno.
2) A complexidade de tempo quando os dados fornecidos já estão classificados é O(n).
Portanto, a classificação Shell divide os dados em vários blocos a cada vez para usar a classificação por inserção e, em seguida, combina esses pequenos blocos em pequenos blocos maiores após serem classificados e continua a usar a classificação por inserção para mesclar continuamente pequenos blocos até o último pequeno pedaço. .
Aqui, cada divisão em vários pequenos blocos é controlada por “incremento”. No início, o incremento é grande, próximo de n/2, de modo que a divisão fica próxima de n/2 pequenos blocos, e o “incremento” é gradual. reduzido”, eventualmente reduzido para 1.
Por exemplo:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//Calcule o 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(dados[i]<dados[ih]){inttmp=dados[i];intj=ih;while(j>= 0&&data [j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//Calcula o próximo valor h h= (h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t }System); .out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(dados);shellSort(dados); dados);}}Os resultados da execução são os seguintes:
461958146958145698145689145689