Java プログラミングスキル - データ構造とアルゴリズム「マージソート」

[[393503]]

基本的な紹介

マージソートは、マージの考え方を使用するソート方法です。このアルゴリズムは、古典的な分割統治戦略を採用しています（分割統治法では、問題をいくつかの小さな問題に分割してから再帰的に解決し、統治段階では分割された段階で得られた答えを「パッチ」でまとめます。つまり、分割統治です）。

概略図

注: この構造は完全な二分木に非常に似ていることがわかります。この記事では、再帰を使用してマージソートを実装します (反復的な方法で実装することもできます)。ステージは、サブシーケンスを再帰的に分割するプロセスとして理解できます。

処理段階を見てみましょう。2 つの順序付けられたサブシーケンスを 1 つの順序付けられたシーケンスにマージする必要があります。たとえば、下の図の最後のマージでは、2 つの順序付けられたサブシーケンス [4,5,7,8] と [1,2,3,6] を最終シーケンス [1,2,3,4,5,6,7,8] にマージする必要があります。実装手順を見てみましょう。

コードサンプル

パッケージ com.structures.sort; 
 
 blic クラス MergeSort {
公共 静的void main(String[] args) {
 int [] arr = 新しいint [80000];
 ( int i = 0; i < 80000; i++) {
          arr[i] = ( int ) (Math.random() * 8000000);
      }
 int [] temp = 新しいint [arr.length];
      長い開始 = System.currentTimeMillis(); 
 
      マージソート(arr,0,arr.length-1, temp );
      長い終了= System.currentTimeMillis();
      System.out.println ( "所要時間:" +((終了- 開始))+ "ミリ秒" );
      /*
      所要時間: 15ms
       */
  } 
 
  //分離+組み合わせ
公共 静的void mergeSort( int [] arr, int  左、 int  右、 int [] temp ){
      （左<右）の場合{
 int中央 = (左+右) / 2;
          //左に再帰的に分解する
          mergeSort(arr、 left 、mid、 temp );
          //右方向に再帰的に分解する
          mergeSort(arr, mid + 1, right , temp );
          //マージ
          マージ(arr、左、中央、右、一時);
      }
  } 
 
  /**
   * マージ
   * @param arr ソートされた元の配列
   * @param left左順序シーケンスの初期インデックス
   * @param mid 中間インデックス
   * @param right右インデックス
   * @param tempは転送配列です
   */
公共 静的voidマージ( int []arr, int  左、 int中央、 int  右、 int [] temp ){
 int i = left ; // 左の順序付きシーケンスの初期インデックス i を初期化します
int j = mid + 1; // 右側の順序付きシーケンスの初期インデックス j を初期化します
int t = 0; //一時配列の現在のインデックスを指します
 
      //（1つ）
      //まず、ルールに従って、左側と右側の（順序付けられた）データを一時配列に入力します
      //左側と右側の順序付けられたシーケンスの1つが処理されるまで、つまりすべてが一時配列に入力されるまで
      (i <= 中央 && j <=右) の間 {
          // 左側の順序付けられたシーケンスが右側の順序付けられたシーケンスの現在の要素より小さいか等しい場合
          // 左側の現在の要素を一時配列にコピーします
          //次にt++、i++を後方に移動する
          もし（arr[i] <= arr[j]）{
 temp [t] = arr[i];
              t += 1;
              私 += 1;
          } else // 逆に、右側の順序付きシーケンスの現在の要素を一時配列に入力します
temp [t] = arr[j];
              t += 1;
              1 を越える
          }
      } 
 
      //（二）
      // 残りのデータをtempに順番に埋め込む 
      while (i <= mid){//左側にまだ残っているので、それを一時配列に入力します。
 temp [t] = arr[i];
          t += 1;
          私 += 1;
      }
      (j <=右) の間 {
 temp [t] = arr[j];
          t += 1;
          1 を越える
      } 
 
      //（三つ）
      // temp配列の要素をarrにコピーします
      //毎回すべてがコピーされるわけではないことに注意してください
      // 最初のマージ leftTemp = 0、 right = 1、2 番目のマージ leftTemp = 2、 right = 3、3 番目のマージ leftTemp = 0、 right = 3...
      t = 0;
 int leftTemp =左;
      （左温度<=右）{
          arr[左温度] =温度[t];
          左温度 += 1;
          t += 1;
      }
  }