直接挿入ソートアルゴリズムと関連する Java バージョンのコード実装の詳細な説明

直接挿入ソート

直接挿入ソートの考え方は次のとおりです:
1. ソート対象の配列をソート済みの部分とソートされていない部分に分割します。一連。
2. 2 番目の要素から始めて、ソートされた部分配列内の要素の適切な位置を見つけて、その位置に挿入します。
3. 最後の要素が順序付けられた部分配列に挿入されるまで、上記のプロセスを繰り返します。
4. 並べ替えが完了しました。

例:
アイデアは非常にシンプルですが、コードはバブル ソートほど簡単に記述できません。まず、適切な場所をどのように決定するのでしょうか?左以上、右以下?いいえ、考慮すべき境界条件がたくさんあり、判断の余地が多すぎます。次に、配列に要素を挿入するには、必然的に多数の要素を移動する必要があります。その移動をどのように制御するかです。
実際、これはアルゴリズム自体の問題ではなく、プログラミング言語と関係があります。場合によっては、アルゴリズム自体がすでに非常に成熟していても、特定のプログラミング言語に関しては若干の変更が必要になることがあります。ここで話しているのは Java アルゴリズムなので、Java について話しましょう。
上記の問題を解決するために、2 番目のステップを少し改良して、サブ配列の開始位置から比較を開始するのではなく、逆の順序でサブ配列の末尾から比較を開始します。挿入する必要がある数値よりも大きいため、後退します。数値がこの数値以下になるまで、挿入する必要のある数値がこの空いた位置に配置されます。したがって、次のコードを作成できます:
InsertArray.java

public class InsertArray {
  // 数组
  private long[] arr;
 
  // 数组中有效数据的大小
  private int elems;
 
  // 默认构造函数
  public InsertArray() {
    arr = new long[50];
  }
 
  public InsertArray(int max) {
    arr = new long[max];
  }
 
  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }
 
  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
 
  // 插入排序
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = select;
    }
  }
}

Test クラス:
TestInsertArray.java

public class TestInsertArray {
  public static void main(String[] args) {
    InsertArray iArr = new InsertArray();
    iArr.insert(85);
    iArr.insert(7856);
    iArr.insert(12);
    iArr.insert(8);
    iArr.insert(5);
    iArr.insert(56);
 
    iArr.display();
    iArr.insertSort();
    iArr.display();
  }
 
}

アルゴリズムのパフォーマンス/複雑さ
次に、直接挿入アルゴリズムの時間計算量について説明します。入力に関係なく、アルゴリズムは常に n-1 ラウンドの並べ替えを実行します。ただし、各要素の挿入位置が不定であり、入力データに大きく影響されるため、その複雑さは定かではありません。最良の状況、最悪の状況、平均的な状況について話し合うことができます。
1. 最良のケース: アルゴリズムの特性から、ソートされる配列自体が正の順序である (配列が順序正しく、その順序が必要な順序と同じである) 場合が最適であることがわかります。理由は、この場合、各要素を一度比較するだけで済み、移動する必要がないからです。アルゴリズムの時間計算量は O(n) です。 最悪のケース: 明らかに、最悪のケースは、ソートされる配列が逆の順序である場合です。この場合、各ラウンドの比較の数は i-1 です。 、および i の割り当ての数。合計次数は、系列 2n-1 の最初の n 項の合計、つまり n^2 です。アルゴリズムの時間計算量は、O(n^2) です。上記の分析から、平均的な場合のアルゴリズムの動作が得られます。回数は約 (n^2)/2 (注: ここでの計算は代入と比較に基づいています。移動と比較に基づく場合は、約n^2/4) 明らかに、時間計算量は依然として O(n^2) です。
アルゴリズムの空間複雑さに関しては、すべての動作はデータ内で実行されます。唯一のオーバーヘッドは、一時変数 (一部のデータ構造の本では「センチネル」と呼ばれます) を導入することです。したがって、その空間複雑さ (余分な空間) は次のとおりです。 ○(1)。

アルゴリズムの安定性

直接挿入ソートは、現在の数値以下の位置を見つけるだけで交換する必要がないため、安定したソート方法です。

アルゴリズムの変形

並べ替えるデータが多い場合、毎回後ろから前に検索するとオーバーヘッドが大きくなり、検索速度を向上させるために、パフォーマンスを向上させるために二分探索 (Binary Search) を使用できます。最適化。二分探索は非常に効率的で、O(㏒n) の複雑さを保証するため、データが大量にある場合や入力データが最悪の場合に検索効率を大幅に向上させることができます。この方法は、書籍によっては半挿入ソートと呼ばれています。コードの実装は比較的複雑なので、今後時間があるときに投稿します。

さらに、双方向挿入ソートと表挿入ソートがあります。 2 方向挿入ソートは半挿入ソートをベースにさらに改良され、移動数が約 n^2/8 と大幅に削減されます。ただし、移動の数が減ったり、複雑さのレベルが軽減されるわけではありません。テーブル挿入ソートはストレージ構造を完全に変更し、レコードを移動しませんが、リンク リストを維持し、移動するレコードをリンク リスト内のポインター変更で置き換える必要があります。したがって、その複雑さは依然として O(n^2) です。
双方向挿入ソートとテーブル挿入ソートについては、Yan Weimin および Wu Weimin 編集の書籍「Data Structure」を参照してください。

アルゴリズムに適用可能なシナリオ

O(n^2) の複雑さのため、配列が大きい場合、挿入ソートは適用できません。ただし、これはデータが比較的小さい場合に適しており、通常はクイック ソートの拡張として使用されます。たとえば、STL のソート アルゴリズムや stdlib の qsort アルゴリズムでは、挿入ソートは少数の要素をソートするためのクイック ソートの補足として使用されます。別の例として、JDK 7 java.util.Arrays で使用されるsortメソッドの実装では、ソートされる配列の長さが47未満の場合、挿入ソートが使用されます。

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