マージは、2つの（または2つ以上）順序付けられたテーブルを新しい順序付けられたテーブルにマージすることです。つまり、シーケンスをいくつかのサブシーケンスに分割し、各サブシーケンスが順序付けられます。次に、順序付けられたサブシーケンスが全体的な順序付きシーケンスに結合されます。
マージソートは、マージ操作に基づいて効果的なソートアルゴリズムです。このアルゴリズムは、Divide and Conquerの非常に典型的なアプリケーションです。 順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。 2つの順序付けられたテーブルが1つの順序テーブルにマージされている場合、2ウェイマージと呼ばれます。
マージのソートアルゴリズムは、O（n）の追加スペースが必要であり、o（n）の追加スペースが必要です適応性がなく、データは必要ありません。
それがどのように機能するか：
1.そのサイズが2つのソートされたシーケンスの合計であるようにスペースを適用します。これは、結合されたシーケンスを保存するために使用されます
2。2つのポインターを設定すると、初期位置はそれぞれ2つのソートされたシーケンスの開始位置です。
3. 2つのポインターで指された要素を比較し、比較的小さな要素を選択してマージスペースに入れ、ポインターを次の位置に移動します
4.ポインターがシーケンスの端に達するまでステップ3を繰り返します
5.別のシーケンスの残りの要素をすべてコピーして、マージされたシーケンスの端に直接コピーします
コードを実行します
コードコピーは次のとおりです。
パッケージcom.zc.manythread;
java.util.randomをインポートします。
/**
*注文
* @author私は
*
*/
パブリッククラスmergesort {
public static void mergesort（int [] data）{
sort（data、0、data.length -1）;
}
public static void sort（int [] data、int left、int右）{
if（左> =右）
戻る;
//中間インデックスを見つけます
int center =（左 +右） / 2;
//左配列を再帰します
ソート（データ、左、中央）;
//適切な配列を再帰します
ソート（データ、センター + 1、右）;
//マージ
マージ（データ、左、中央、右）;
print（data）;
}
/**
* 2つの配列をマージし、最初の2つの配列を順序にマージし、マージした後も注文します
*
* @paramデータ
*配列オブジェクト
* @param左
*左配列の最初の要素のインデックス
* @paramセンター
*左配列の最後の要素のインデックス、中央+1は、右配列の最初の要素のインデックスです
* @param右
*右配列の最後の要素のインデックス
*/
public static void merge（int [] data、int left、int center、int right）{
//一時配列
int [] tmparr = new int [data.length];
//右配列の最初の要素のインデックス
int mid = center + 1;
// 3番目の一時的な配列のインデックスを記録します
int 3番目=左;
//左配列の最初の要素のインデックスをキャッシュ
int tmp =左;
while（左<= center && mid <=右）{
// 2つの配列から最小を取り出して、一時配列に入れます
if（data [left] <= data [mid]）{
tmparr [third ++] = data [left ++];
} それ以外 {
tmparr [third ++] = data [mid ++];
}
}
//残りの部分を順番に一時配列に入れます（実際、2つのうちの1つだけが実行されます）
while（mid <=右）{
tmparr [third ++] = data [mid ++];
}
while（left <= center）{
tmparr [third ++] = data [left ++];
}
//一時配列の内容を元の配列に戻します
//（元の左右範囲のコンテンツが元の配列にコピーされます）
while（tmp <=右）{
data [tmp] = tmparr [tmp ++];
}
}
public static void print（int [] data）{
for（int i = 0; i <data.length; i ++）{
System.out.print（data [i] + "/t"）;
}
System.out.println（）;
}
/**
*ランダム配列を生成します
* @param count
* @戻る
*/
private static int [] createdate（int count）{
int [] data = new int [count];
ランダムrand = new Random（）;
boolean [] bool = new boolean [100];
int num = 0;
for（int i = 0; i <count; i ++）{
する {
//生成された数値が同じ場合、ループを続けます
num = rand.nextint（100）;
} while（bool [num]）;
bool [num] = true;
データ[i] = num;
}
データを返す;
}
public static void main（string [] args）{
int [] data = createdate（10）;
print（data）;
mergesort（data）;
system.out.println（ "sorted array："）;
print（data）;
}
}
実行結果：
上記はすべてこの記事についてです。あなたがそれを好きになることを願っています。