Shell Sort adalah jenis penyisipan penyortiran dan versi penyisipan langsung yang lebih efisien dan lebih baik. Shell Sort memanfaatkan sepenuhnya dua karakteristik penyisipan penyortiran:
1) Sangat efisien bila ukuran datanya kecil.
2) Kompleksitas waktu ketika data tertentu sudah diurutkan adalah O(n).
Oleh karena itu, penyortiran Shell membagi data menjadi beberapa blok setiap kali menggunakan penyortiran penyisipan, dan kemudian menggabungkan blok-blok kecil ini menjadi blok-blok kecil yang lebih besar setelah diurutkan, dan terus menggunakan penyortiran penyisipan untuk terus menggabungkan blok-blok kecil hingga potongan kecil terakhir .
Di sini, setiap pembagian menjadi beberapa blok kecil dikendalikan oleh "kenaikan". Pada awalnya, kenaikannya besar, mendekati n/2, sehingga pembagian tersebut mendekati n/2 blok kecil, dan "kenaikan" dilakukan secara bertahap. dikurangi. ”, akhirnya dikurangi menjadi 1.
Misalnya:
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//Hitung nilai h maksimum inth=1; while(h<=data.length/3){h=h*3+1;}sementara(h > 0){untuk(inti=h;i<data.length;i+=h){if(data[i]<data[ih]){inttmp=data[i];intj=ih;sementara(j>= 0&&data [j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//Hitung nilai h selanjutnya 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(data);shellSort(data); data);}}Hasil yang berjalan adalah sebagai berikut:
461958146958145698145689145689