Javaデータ構造のソートアルゴリズム (2) マージソート

この記事では主にJavaデータ構造のソートアルゴリズムのマージソートを紹介し、具体的な例に基づいてマージソートの原理、実装テクニック、関連する注意事項を詳しく分析します。 Java データ構造 ソート アルゴリズム マージ ソート。参考までに、詳細は次のとおりです。

前述の並べ替えの種類はすべて、キーワードのサイズに応じてレコードのグループを順序付けされたシーケンスに配置します。マージに基づいて、2 つを結合します 2 つ以上の順序付きリストを新しい順序付きリストにマージします

マージソートアルゴリズム:最初のシーケンスに n 個のレコードが含まれていると仮定し、最初にこれらの n レコードを n 個の順序付きサブシーケンスとして扱います。各サブシーケンスは 1 であり、ペアでマージされて、長さ 2 の n/2 個の順序付きサブシーケンスが得られます (n が奇数の場合、最後のシーケンスの長さは 1)。これに基づいて、長さ 2 の順序付きサブシーケンスが明るくマージされ、長さ 4 のいくつかの順序付きサブシーケンスが得られます。長さ n の順序付けされたシーケンスが得られるまで、これを繰り返します。この方法は、2 方向マージ ソートと呼ばれます (基本的な操作は、並べ替えられるシーケンス内の 2 つの隣接する順序付けされたサブシーケンスをマージして、順序付けされたシーケンスにすることです)。

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

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路归并排序算法，递归实现
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

コードの説明: マージソートでは、マージの 1 つのパスで双方向マージ アルゴリズムへの複数の呼び出しが必要です。マージのパスが O (n) である場合、最大で n-1 回の比較が行われるため、2 つのソートされたリストをマージする時間は明らかに線形です (n は要素の総数)。数値が複数ある場合、つまり n が 1 以外の場合、データの前半と後半を再帰的にマージおよびソートし、ソートされた 2 つのデータを取得し、それらをマージします。

アルゴリズム分析: このアルゴリズムは、マージ操作 (マージ アルゴリズムとも呼ばれ、2 つの並べ替えられたシーケンスを 1 つのシーケンスにマージする操作を指します) に基づいた効果的な並べ替えアルゴリズムです。このアルゴリズムは、

分割統治法

(pide and Conquer) の非常に典型的な応用であり、問​​題をいくつかの小さな問題に分割し、それらを再帰的に解決します。征服段階では、分割段階で得られた答えを 1 つにまとめます。分割統治は再帰の非常に強力な使用法です。注: マージソートの最大の特徴は、クイックソートやヒープソートと比較して、安定したソート方法であることです。速度はクイック ソートに次いで 2 番目であり、通常は不規則であるがサブ項目が比較的順序付けられている配列に使用されます。

複雑度: 時間計算量は次のとおりです:

O(nlogn)

——このアルゴリズムの最高、最低、平均時間パフォーマンス。 空間計算量は次のとおりです: O(n)
比較演算の数は、(nlogn) / 2 と nlogn - n + 1 の間です。 代入演算の回数は(2nlogn)です。マージ アルゴリズムの空間複雑さは 0 (n) です
メイン メモリのソートに使用するのは困難です (マージ ソートはより多くのメモリを必要とします。主な問題は、2 つのソートされたテーブルをマージするには線形の追加メモリが必要であり、データのコストもかかることです)一時的な
配列
にコピーしてからコピーし直すなど、いくつかの追加操作はソート速度を大幅に低下させます) が、これは非常に効率的であり、主に重要な内部ソート アプリケーションに使用されます。 、一般的にはクイックソートが選択されます。

マージ操作の手順は次のとおりです: ステップ 1: サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。このスペースは、マージされたシーケンスを保存するために使用されます。 2 つのポインターを設定します。初期位置は、それぞれ 2 つのソートされたシーケンスの開始位置です

ステップ 3: 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージスペースに置き、ポインターを次の位置

特定のポインターがシーケンスの最後に到達するまでステップ 3 を繰り返す
他のシーケンスの残りのすべての要素をマージされたシーケンスの最後に直接コピーする

マージソートの手順

は次のとおりです (仮定シーケンスには合計 n 個の要素があります): シーケンスの各要素をコピーします。 2 つの隣接する数値がマージされて、floor(n/2) シーケンスが形成されます。 ソート後、各シーケンスには上記の 2 つの要素が再度マージされ、floor( が形成されます。 n/4) シーケンス、それぞれ シーケンスには 4 つの要素が含まれますすべての要素がソートされるまでステップ 2 を繰り返します

1.
Java データ構造ソート アルゴリズム (1) ツリー選択ソート

2. Java での選択ソートの説明 (Selection Sort_java) サンプル チュートリアル

3. Java データ構造ソート アルゴリズム (3) 単純な選択ソート

4. Javaデータ構造ソートアルゴリズム(4)選択ソート

以上がJavaデータ構造のソートアルゴリズム (2) マージソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。