Java Hillソートの例の詳細な説明

この記事では、主にヒルソートのJavaデータ構造とアルゴリズムを紹介し、サンプルの形でヒルソートの概念、原理、実装方法、および関連する注意事項を分析します。必要な友人はそれを参照できます

この記事の例。データ構造とアルゴリズムの Java Hill ソートについて説明します。参考までに皆さんと共有してください。詳細は以下の通りです:

ここで紹介したいのは、ヒルソート(縮小増分ソート法)です。

ヒルソート: 間隔をあけて配置された要素を比較することで機能します。アルゴリズムが進行するにつれて、最後の並べ替えパスで隣接する要素のみが比較されるまで、各比較に使用される距離 (増分) が減少します。これは挿入ソートの一種であり、直接挿入ソート アルゴリズムを改良したものです。

アルゴリズムのアイデア: まず、ソート対象のシーケンスを特定の増分 d に従っていくつかのサブシーケンスに分割し、各サブシーケンス内のすべての要素に対して直接挿入ソートを実行し、その後、より小さい増分を使用して グループ化 してからソートします。各グループ。増分が 1 になると、ソート対象の数値全体が 1 つのグループに分割され、ソートが完了します。注: 増分の値 - 通常、最初はシーケンスの半分が増分として取得され、その後は増分が 1 になるまで毎回半分になります。

アルゴリズムの実装コードは次のとおりです:

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //设置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步长
      for (int i = average; i < array.length; i++) { //子序列进行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

アルゴリズム分析: このアルゴリズムは、要素が最初に非常に無秩序である場合、ステップ サイズが最大になり、異なるステップ サイズに従って要素を挿入および並べ替えます。要素が基本的に順序付けされており、ステップ サイズが小さい場合、挿入ソートは順序付けされたシーケンスに対して非常に効率的です。したがって、Hill ソートの時間計算量は O(n^2) よりも優れており、O(n^1.5) となり、ソート効率は挿入ソートよりもはるかに高くなります。複数の挿入ソートにより、1 つの挿入ソートは安定しており、同じ要素の相対的な順序は変更されないことがわかっています。ただし、異なる挿入ソート プロセスでは、同じ要素がそれぞれの挿入ソートで移動する可能性があり、最終的には安定性が低下します。変更が中断されているため、シェルのソートが不安定です。 ヒルソートはクイックソートアルゴリズムO(N*(logN))ほど高速ではないため、中規模のデータのソートにはより適していますが、非常に大規模なデータのソートには最適な選択肢ではありません。ただし、O(N^2) 複雑度アルゴリズムよりもはるかに高速です。また、ヒル ソートは実装が非常に簡単で、アルゴリズム コードは短くてシンプルです。 さらに、最悪の場合のヒルのアルゴリズムのパフォーマンス効率と平均的な場合の差はそれほど大きくありませんが、最悪の場合のクイック ソートの効率は非常に低くなります。

【関連推奨事項】

1. 特別な推奨事項: 「php Programmer Toolbox」V0.1バージョンのダウンロード

2. YMPオンラインマニュアル

以上がJava Hillソートの例の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。