...彼が何をしていたかを8歳の子供に説明できなかった科学者はだれでもいた。
結局のところ、それはカート・ヴォネガットでした。
私はこの声明を証明しようとしませんでした。 私は自分の愚かさに反論しようとしました。
昇順でソートされた数値の2つの配列があるとします。
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
それらを1つの順序付けられた配列にマージする必要があります。
int[] a3 = new int[a1.length + a2.length];
これはマージソートタスクです。
これは何ですか インターネット上に答えがあり、アルゴリズムの説明がありますが、私は座っている人からそれを理解できず、自分でそれを理解することにしました。 これを行うには、タスクに関連してメモリからアルゴリズムを再作成できるように、アルゴリズムの基本原理を理解する必要があります。
健康のために始めた
徐々に進み、表面にあるものを活用しましょう。各配列から一度に1つの要素を取り出し、それらを比較して1つの配列にマージします。 小さい要素が最初に配置され、大きい要素が2番目に配置されます。 その後、最初のパスの後、すべてが正常です：
10, 21
そして、2回目のパスの後、それはあまりありません：
10, 21, 11, 23
要素をすでに追加されている要素と比較する必要があることは明らかです。
もう一度始めましょう
各ステップで比較される要素からの一時バッファを用意します。 比較後、小さな要素10をバッファーから結果の配列に移動し、その背後に何があるかわからないため、大きな要素21を残します。
2回目のパスの後、バッファは21、23、および11になります。それらをどうするかは明確ではありません。3つ以上の要素を比較することは可能ですが、それほど単純ではありません。
次に、各配列から1つの要素をこのバッファーに取り込むことに同意しましょう。 2つの要素を互いに比較する方が簡単であり、実際には2つのエンティティ（2つの配列）があるためです。 バッファ内の2番目のパスの後、21と11があります。これは、バッファ内の最初の配列の「代表」がすでに存在するためです。これは21です。 次に、2回目のパスの後、結果の配列になります。
10, 11
バッファ内-21。
3番目のパスでは、最初の配列の「代表」がバッファーに残っているため、2番目の配列41からバッファーに移動します。 21と41を比較し、最後にバッファー21から削除します。
3番目のパスの後、結果の配列になります。
10, 11, 21
4番目のパスでは、バッファーの2つの値-41と23を比較します。結果の配列は次のようになります。
10, 11, 21, 23
つまり、今だけ-4回目で、2回目のパスではなく-結果は正しかったのです。 ループでは、各配列の現在のインデックスを覚えておく必要があり、ループ自体の長さは配列の長さの合計に等しいことがわかります。
終わりましたが、突然
結果の配列が以下で構成される場合に行うこと：
10, 11, 21, 23, 24, 40, 41, 50, 65, 75, 76, 78, 77, 86, 98, 101, 190, 900, 1100, 1200, 2100, 2200, 2300, 2400, 2500,
バッファーには、2番目の配列から3000があり、最初の配列では、すべての要素が不足しますか？ 配列はソートされているため、バッファから3000と残りの5000を取得するだけです。つまり、各配列の要素数を超えたかどうかを各インデックスで確認する必要があります。
タスクを複雑にしましょう
そして、ソートされた配列がない場合はどうなりますか？ 通常、タスクは1つの配列をソートすることです。 その後、マージソートも使用できます。
最初の配列（たとえば、そこからいくつかの要素を取得する）が次の要素の配列を持つようにします。
2100, 23, 40, 24, 2, 1.
ソートします。 2つの要素を比較する方が簡単な場合、配列を2つに均等に分割します。
2150, 23, 40
そして
24, 2, 1.
3つの要素が判明します。 たくさん！ 各配列を均等に分割すると、4つの配列が得られます。
2100, 23 40 24, 2 1
次に、最初の要素と2番目の要素（ある場合）の単純な比較によって各配列を並べ替えます。
23, 2100 40 2, 24 1
そして、前のアルゴリズムに従って、バッファを介してマージします。 最初のマージの後、2つの配列を取得します。
23, 40, 2100 1, 2, 24
そして再びマージ-すでに1つの配列に：
1, 2, 23, 24, 40, 2100
そこで、配列をマージしてソートしました。
乾燥残留物中
したがって、マージソートでは、1つの配列からいくつかの小さな配列が取得されるまで、配列を均等に分割します。サイズは2要素以下です。 要件に従って昇順または降順の2つの要素を簡単に比較およびソートできます。
分割後、逆マージが続きます。このマージでは、ある時点（またはループごと）で、各配列から1つの要素が選択され、互いに比較されます。 最小（または最大）要素が結果の配列に送信され、残りの要素は次のステップで別の配列の要素との比較に関連したままです。
コードで表現する（Java）
2つのソートされた配列の昇順ソートの例：
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int[] a3 = new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k<a3.length; k++) { if (i > a1.length-1) { int a = a2[j]; a3[k] = a; j++; } else if (j > a2.length-1) { int a = a1[i]; a3[k] = a; i++; } else if (a1[i] < a2[j]) { int a = a1[i]; a3[k] = a; i++; } else { int b = a2[j]; a3[k] = b; j++; } }
ここに：
a1とa2はマージされる配列です。
a3は結果の配列です。
iとjはそれぞれ配列a1とa2のインデックスで、各ステップでの現在の要素を示し、同じバッファーを形成します。
最初の2つの条件は、インデックスが配列の要素数の制限を超えないことを確認します。 3番目と4番目の条件は、最初の配列と2番目の配列の最小要素がそれぞれ配列に移動することを保証します。
ソート機能の統合
指定されたコードを、最初の呼び出しで配列全体に対応するパラメーター、2番目と3番目の呼び出しで半分に対応するパラメーターなど、配列をできるだけ長く分割する再帰関数として設計してみましょう。
private void SortUnsorted(int[] a, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; SortUnsorted(a, lo, mid); SortUnsorted(a, mid + 1, hi); int[] buf = Arrays.copyOf(a, a.length); for (int k = lo; k <= hi; k++) buf[k] = a[k]; int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = buf[j]; j++; } else if (j > hi) { a[k] = buf[i]; i++; } else if (buf[j] < buf[i]) { a[k] = buf[j]; j++; } else { a[k] = buf[i]; i++; } } }
ここに：
aは配列です。
lo-配列内の最初の要素の位置（最初の反復= 0）;
hi-配列の最後の要素の位置（最初の反復= a.length-1）。
参照資料
Javaアルゴリズム
猫のゆりかごの引用