Javaでの挿入ソートの実装例を詳しく解説

この記事では、主に Java のデータ構造と挿入ソートのアルゴリズムを紹介し、Java 挿入ソートの概念、分類、原理、実装方法、および関連する注意事項をサンプルの形式で分析します。この記事では、Java データ構造とアルゴリズム挿入ソートについて説明します。詳細は以下の通りです:

データ構造におけるソートに関する知識を整理したので、より多くの人に共有したいと思い、書き留めました。将来の参照のためにバックアップを作成することです。

ソート

1. 概念:

n 個の記録されたシーケンス {R1, R2,....,Rn} があります (ここで注意: 1,2,n は次のテーブルシーケンスです、以下も同じ効果があります)、対応するキーワードのシーケンスは {K1, K2,.......,Kn} です。ソートを通じて、対応するキーワードが次の非減少 (非増加) 関係を満たすように、現在の添え字シーケンス 1,2,...,n の配列 p1, p2,...pn を見つける必要があります。 、つまり、Kp1

2. 分類

ソート中にデータが占有するメモリの違いに基づいて、ソートは 2 つのカテゴリに分類できます。

内部ソート:

以下のように、ソートプロセス全体がメモリ内で完全に実行されます:

挿入ソート (直接挿入ソート、半挿入ソート、ヒルソート)

交換ソート (

バブルソート) 、クイックソート);

選択ソート(単純な

選択ソート、ツリー選択ソート、ヒープソート);

分散ソート(複数キーワードソート、チェーン基数ソート、基数)ソート シーケンス テーブルの実装));

外部ソート:

ソートするレコード データが大量であるため、メモリにすべてのデータを収容できず、ソートは外部ストレージ デバイスの助けを借りて完了する必要があります ()ディスクのソート、テープのソート )。

3. 安定性 ソート対象のシーケンス内に同じキーワードを持つ複数のレコードがあると仮定します。 Ki=Kj(1

挿入ソート: アイデア: すべてのレコードが挿入されるまで、キー サイズに従って、ソート対象のレコードが以前にソートされたサブファイル内の適切な位置に挿入されるたびに。

直接挿入ソート:

アルゴリズムのアイデア: ソートされるレコードが arrayR[1..n] に格納されていると仮定します。最初に、R[1] は順序付き領域を形成し、順序なし領域は R[2..n] になります。 i=2 から i=n まで、R[i] が現在の順序付け領域 R[1..i-1] に順番に挿入され、n 個のレコードを含む順序付き領域が生成されます。 Java で実装されたコードは次のとおりです:

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      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 };
    DircstSort(array);
  }
}

アルゴリズム分析:

最良のケースは、ソートされるレコード自体がキーワードに従って順序付けされている場合であり、最悪のケースは、ソートされるレコードはキーワードに従って逆順に配置されます。

時間計算量は O(N^2)、空間計算量は O(1) です。

このアルゴリズムは安定したソート アルゴリズムです。ソートするレコードの数が少なく、基本的に順序が整っている状況 に適しています。 目的挿入ソート:

アルゴリズムのアイデア: 順序付きリストの半分検索のパフォーマンスは、順次検索よりも優れています。

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

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = 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};
    sort(array);
  }
}

アルゴリズム分析:

は安定した並べ替えアルゴリズムであり、直接挿入アルゴリズムよりもキーワード間の比較の数が大幅に削減されるため、

は直接挿入よりも高速ですソート アルゴリズム

を変更しましたが、レコードの移動数は変わっていないため、半減挿入ソート アルゴリズムの

時間計算量は依然として O(n^2) であり、

直接挿入ソート アルゴリズムと同じです。 追加スペース O(1)。 【関連推奨事項】1.

特別な推奨事項

: 「php Programmer Toolbox」V0.1バージョンのダウンロード

2. Java 無料ビデオチュートリアル

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

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