シェル ソートは挿入ソートの一種であり、直接挿入ソートのより効率的かつ改良されたバージョンであり、挿入ソートの 2 つの特性を最大限に活用します。
1) データサイズが小さい場合に非常に効率的です。
2) 指定されたデータがすでにソートされている場合の時間計算量は O(n) です。
したがって、シェル ソートでは、挿入ソートを使用するたびにデータをいくつかのブロックに分割し、ソート後にこれらの小さなブロックをより大きな小さなブロックに結合し、最後の小さなチャンクまで挿入ソートを使用して小さなブロックを連続的にマージし続けます。 。
ここで、いくつかの小ブロックへの分割は「増分」によって制御されます。最初は増分が大きく、n/2 に近くなり、徐々に「増分」が増加します。減少しました」、最終的には 1 に減少しました。
例えば：
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//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);}}//次の 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(data);shellSort(data);データ）;}}実行結果は次のとおりです。
461958146958145698145689145689