javaデータ構造並べ替えアルゴリズムのまとめと並べ替えの詳細

本明細書の例は、Javaデータ構造の順序付けアルゴリズムの規格化および順序付けについて述べる。皆さんに参考にしてあげます。具体的には以下の通りです。
前述のいくつかの並べ替えは、キーワードの大きさに従って1つの順序で記録され、並べ替えられたものである。統合に基づいて、2つまたは2つ以上の順序テーブルを新たな順序表に統合するという思想である。
正規化アルゴリズム：最初のシーケンスがn個の記録を含むと仮定して、まずn個の記録をn個の秩序化されたサブシーケンスと見なし、各サブシーケンスの長さは1であり、その後、2つの正規化が行われ、n／2個の長さは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("
----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("
");
  }
}

コードの説明:
正規化された順を並べ替えて、2回の正規化アルゴリズムを呼び出さなければならないが、1回の正規化の時間複雑さはO（n）であり、2つの順序が既に並べられているテーブルを結合する時間は明らかに線形であり、n−1回の比較が最も多く行われているため、ここでnは要素の総数である。複数の数がある場合、すなわちnが1でない場合、再帰的に前半のデータと後半のデータをそれぞれ並べ替えて並べ替え、並べ替えられた2つの部分のデータを得て、再結合します。
アルゴリズム解析:
アルゴリズムは、正規化動作（いわゆる帰納アルゴリズムと呼ばれる）において確立された効率的な並べ替えアルゴリズムである。このアルゴリズムはディヴィッドアンド・コンクラーの非常に典型的な応用を採用しています。問題をいくつかの小さな問題に分けてから再帰的に解決します。治療の段階は段階的に解いた答えを一つに補修します。分治は再帰的に非常に有力な用法である。注意：高速・並べ替えと積み上げと比較して、並び替えの最大の特徴は、安定した並び方です。速度は速い秩序に次ぎ，一般的には全体無秩序に用いられるが，各サブ項の相対的に秩序化した数列である。
複雑度:
時間の複雑さはO（nlogn）――このアルゴリズムが一番良くて、最悪で、平均的な時間性能です。
空間複雑度は：O（n）
比較動作の回数は(nlogn)/2とnlogn-n+1の間です。
割り当て操作の回数は（2 nlogn）です。正規化アルゴリズムの空間複雑さは、0（n）
メインメモリの並べ替えに使用するのは難しいです。二つの並べ替えのテーブルを統合するには、線形メモリが必要です。アルゴリズム全体では、データを一時的な配列にコピーして戻すという追加的な操作も必要です。結果としては、並べ替えの速度が大幅に遅くなりました。重要な内部並べ替えアプリケーションに対しては、一般的には高速の並べ替えが選択されます。
まとめて操作する手順は以下の通りです。
第1のステップ：統合されたシーケンスを保存するために使用される、2つの並べ替えられたシーケンスの合計のサイズを適用するための空間。
第二ステップ：2つのポインタを設定し、最初の位置はそれぞれ2つの順序付けられたシーケンスの開始位置です。
ステップ3：2つのポインタが指す要素を比較し、比較的小さい要素を結合空間に入れて、ポインタを次の位置に移動します。
ステップ3を繰り返します。
他のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーします。
並べ替えの手順は以下の通りです。
シーケンスを隣接する2つの数字ごとにまとめて動作し、flover（n/2）のシーケンスを形成し、並べ替え後の各シーケンスは2つの要素を含む。
上記のシーケンスを再びまとめて、flor（n/4）のシーケンスを形成し、各シーケンスは4つの要素を含む。
すべての要素がソートされるまで、手順2を繰り返します。
javaアルゴリズムに関する詳細について興味がある読者は、当駅のテーマを見ることができます。「Javaデータ構造とアルゴリズム教程」、「Java操作DOMノード技術のまとめ」、「Javaファイルとディレクトリの操作テクニックのまとめ」、「Javaキャッシュ操作テクニックのまとめ」
本論文で述べたように、皆さんのjavaプログラムの設計に役に立ちます。