導入
ヒルソート（増分メソッドの削減）は、挿入クラスのソートに属します。シェルによって提案されています。 Hillの並べ替えにより、挿入並べ替えが直接的に改善されました。挿入ソートの要素間の間隔を増加させ、これらの間隔要素への挿入により、データ項目が大きなスパンに移動します。これらのデータ項目が一度ソートされた後、ヒルソートアルゴリズムはデータ項目の間隔を削減してからソートし、順番に進行します。これらの並べ替えが増分と呼ばれる場合のデータ項目間の間隔、および文字hはこの増分を表すために使用されます。
一般的に使用されるHシーケンスは、Knuthによって提案されています。このシーケンスは1から始まり、次の式で生成されます。
H = 3 * H +1
プログラムは順番にHシーケンスを逆に計算する必要があり、使用する必要があります
h =（h-1）/3
コード実装
実装コード1：
public static void shellsort（int [] arr）{int temp; for（int delta = arr.l.length/2; delta> = 1; delta/= 2）{//各増分を1回（int i = delta; i <arr.length; i ++）{for（int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta） arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // loop i} // loop delta}実装コード2：
public static void shellsort2（int [] arr）{int delta = 1; while（delta <arr.length/3）{// delta delta = delta*3+1を生成します。 // <o（n^（3/2））by Knuth、1973>：1、4、13、40、121、...} int temp; for（; delta> = 1; delta/= 3）{for（int i = delta; i <arr.length; i ++）{for（int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta）{temp = arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // loop i} // loop delta}上記のプログラムが直接挿入方法と比較すると、直接挿入ソートと直接挿入ソートの違いは、直接挿入ソートのHが1に置き換えることであることがわかります。
シェルの並べ替えは不安定で、そのスペースオーバーヘッドもO（1）であり、時間オーバーヘッドはO（N3/2）とO（N7/6）の間であると推定されます。