Shell Sort est un type de tri par insertion et une version plus efficace et améliorée du tri par insertion directe qui utilise pleinement deux caractéristiques du tri par insertion :
1) Très efficace lorsque la taille des données est petite.
2) La complexité temporelle lorsque les données données sont déjà triées est O(n).
Par conséquent, le tri Shell divise les données en plusieurs blocs à chaque fois pour utiliser le tri par insertion, puis combine ces petits blocs en petits blocs plus grands après leur tri, et continue d'utiliser le tri par insertion pour fusionner continuellement les petits blocs jusqu'au dernier petit morceau. .
Ici, chaque division en plusieurs petits blocs est contrôlée par « incrément ». Au début, l'incrément est grand, proche de n/2, de sorte que la division est proche de n/2 petits blocs, et « l'incrément » est progressivement. réduit. », finalement réduit à 1.
Par exemple:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//Calculer la valeur h maximale 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);}}//Calculer la valeur h suivante h= (h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t }Système); .out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(data);shellSort(data); données);}}Les résultats en cours d'exécution sont les suivants :
461958146958145698145689145689