Shell Sort ist eine Art Einfügungssortierung und eine effizientere und verbesserte Version der direkten Einfügungssortierung. Shell Sort nutzt zwei Merkmale der Einfügungssortierung vollständig aus:
1) Sehr effizient, wenn die Datengröße klein ist.
2) Die Zeitkomplexität, wenn die gegebenen Daten bereits sortiert sind, beträgt O(n).
Daher unterteilt die Shell-Sortierung die Daten jedes Mal in mehrere Blöcke, um die Einfügungssortierung zu verwenden, und kombiniert diese kleinen Blöcke nach der Sortierung zu größeren kleinen Blöcken. Anschließend wird die Einfügungssortierung verwendet, um kleine Blöcke kontinuierlich zusammenzuführen, bis der letzte kleine Block erreicht ist .
Hier wird jede Aufteilung in mehrere kleine Blöcke durch „Inkrement“ gesteuert. Zu Beginn ist das Inkrement groß, nahe bei n/2, sodass die Aufteilung nahe bei n/2 kleinen Blöcken liegt und das „Inkrement“ schrittweise erfolgt reduziert.“, schließlich auf 1 reduziert.
Zum Beispiel:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//Berechnen Sie den maximalen h-Wert 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);}}//Berechnen Sie den nächsten h-Wert 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(data);shellSort(data); Daten);}}Die Laufergebnisse sind wie folgt:
461958146958145698145689145689