Hill ソート アルゴリズムと関連する Java コード実装の詳細な解釈

Shell のソートは、非常に「魔法の」ソート アルゴリズムです。それが「魔法」と呼ばれるのは、その性能が何であるかを誰も明確に説明できないためです。 DLによるヒルソート。シェルは 1959 年に提案されたことにちなんで名付けられました。 1962 年に C. A. R. Hoare がクイック ソートを提案して以来、より簡単なクイック ソートが一般的に使用されています。しかし、多くの数学者は今もヒルソートの最適な複雑さを見つけるために精力的に研究を続けています。普通のプログラマーとして、私たちはヒルのアイデアから学ぶことができます。
ちなみに、ヒルソートが登場する前は、コンピュータ業界では「ソートアルゴリズムはO(n2)を突破できない」という共通認識がありました。ヒルソートの登場によりこの呪縛は打ち破られ、やがてクイックソートなどのアルゴリズムが次々と登場しました。その意味で、ヒルソーティングは私たちを新しい時代へと導きます。

アルゴリズムの概要/アイデア
ヒル ソートの提案は主に次の 2 つの点に基づいています:
1. 配列が基本的に順序付けされている場合、挿入ソート アルゴリズムはおよそ O(n) の複雑さに達することができ、非常に効率的です。
2. ただし、挿入ソートは一度に 1 ビットしかデータを移動できないため、配列が大きく、基本的に順序付けされていない場合、パフォーマンスが急速に低下します。

これに基づいて、グループ化された挿入ソート方法を使用できます。具体的な方法は次のとおりです: (例として 16 個の要素の配列を使用します)
1. 1 より大きい増分デルタを選択し、配列から を押します。この増分により、直接挿入ソートのサブ配列が選択されます。たとえば、選択した増分が 5 の場合、インデックス 0、5、10、および 15 を持つ要素が並べ替えられます。
2. 増分デルタを保持し、1 ラウンドが完了するまで直接挿入ソートのために最初の要素を順番に移動します。上の例では、配列 [1, 6, 11]、[2, 7, 12]、[3, 8, 13]、[4, 9, 14] が順番にソートされます。
3. 増分を減らし、増分が 1 になるまで上記のプロセスを繰り返します。明らかに、最後は直接挿入ソートです。
4. 並べ替えが完了しました。
上記からわかるように、増分は常に減少しているため、ヒルソートは「縮小増分ソート」とも呼ばれます。

コード実装

package sort; 
  
public class ShellSortTest { 
  public static int count = 0; 
  
  public static void main(String[] args) { 
  
    int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; 
    print(data); 
    shellSort(data); 
    print(data); 
  
  } 
  
  public static void shellSort(int[] data) { 
    // 计算出最大的h值 
    int h = 1; 
    while (h <= data.length / 3) { 
      h = h * 3 + 1; 
    } 
    while (h > 0) { 
      for (int i = h; i < data.length; i += h) { 
        if (data[i] < data[i - h]) { 
          int tmp = data[i]; 
          int j = i - h; 
          while (j >= 0 && data[j] > tmp) { 
            data[j + h] = data[j]; 
            j -= h; 
          } 
          data[j + h] = tmp; 
          print(data); 
        } 
      } 
      // 计算出下一个h值 
      h = (h - 1) / 3; 
    } 
  } 
  
  public static void print(int[] data) { 
    for (int i = 0; i < data.length; i++) { 
      System.out.print(data[i] + "\t"); 
    } 
    System.out.println(); 
  } 
  
}

実行結果:

5  3  6  2  1  9  4  8  7   
1  3  6  2  5  9  4  8  7   
1  2  3  6  5  9  4  8  7   
1  2  3  5  6  9  4  8  7   
1  2  3  4  5  6  9  8  7   
1  2  3  4  5  6  8  9  7   
1  2  3  4  5  6  7  8  9   
1  2  3  4  5  6  7  8  9

アルゴリズムのパフォーマンス/複雑さ
ヒルソートの増分シーケンスは任意に選択できます。必要な唯一の条件は、最後のものが 1 であることです (1 ずつ順序付けされる必要があるため)。 。ただし、シーケンスの選択が異なると、アルゴリズムのパフォーマンスに大きな影響を与えます。上記のコードは 2 つの増分を示しています。
覚えておいてください: インクリメンタル シーケンス内の 2 つの要素ごとに 1 以外の共通因数を持たないことが最善です。 (明らかに、シーケンスを 4 で並べ替えてから 2 で並べ替えることはあまり意味がありません)。
ここでは、一般的なデルタ シーケンスをいくつか示します。
最初の増分は、ドナルド シェルによって当初提案された増分であり、1 になるまで半分に減らされます。研究によると、ヒル インクリメントを使用しても、時間計算量は依然として O(n2) です。
2 番目の増分 Hibbard: {1, 3, ..., 2^k-1}。この増分シーケンスの時間計算量は約 O(n^1.5) です。
3 番目のインクリメント Sedgewick インクリメント: (1, 5, 19, 41, 109,...)、生成されるシーケンスは 9*4^i - 9*2^i + 1 または 4^i - 3*2^ のいずれかですi+1。

アルゴリズムの安定性
挿入ソートが安定したアルゴリズムであることは誰もが知っています。ただし、シェル ソートは複数の挿入プロセスです。 1 回の挿入では、同じ要素の順序が移動しないことを保証できますが、複数の挿入では、同じ要素が異なる挿入ラウンドで移動する可能性があり、最終的には安定性が損なわれるため、シェルのソート アルゴリズムは安定しません。 。

アルゴリズムの適用シナリオ
シェルソートは高速ですが、所詮は挿入ソートであり、新星であるクイックソーティングO(n㏒n)ほど高速ではありません。シェルソートは、大量のデータを扱う場合には適切なアルゴリズムではありません。ただし、小規模から中規模のデータにはまったく問題ありません。

Hill ソート アルゴリズムの詳細な説明と関連する Java コード実装関連の記事については、PHP 中国語 Web サイトに注目してください。