マージソートアルゴリズム

マージソートアルゴリズムについての深い理解

マージソートアルゴリズムの核となる考え方は分割統治法、つまり「分割統治」です。各部分配列に要素が 1 つだけ含まれるまで (現在はソートされています)、配列をより小さな部分配列に再帰的に分割します。次に、これらの部分配列をより大きなソートされた配列にマージします。ソートプロセスは分割フェーズではなくマージフェーズ中に発生することに注意してください。

アルゴリズムのデモ

並べ替える配列があるとします。

配列を左と右のサブ配列に分割します。

各部分配列の要素が 1 つだけになるまで再帰的分割を続けます:

次に、これらの部分配列をマージして並べ替えます。小さい値が左側、大きい値が右側になります。

最終的に並べ替えられた:

コード実装 (Java)

元の Java コードには、最適化できる効率性の問題がいくつかあります。改良されたコードは次のとおりです:

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < left.length || rightIndex < right.length) {
        if (leftIndex < left.length && (rightIndex >= right.length || left[leftIndex] <= right[rightIndex])) {
            array[arrayIndex++] = left[leftIndex++];
        } else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

この最適化されたコードは、Arrays.copyOfRange() メソッドを使用して配列要素をより効率的にコピーし、マージ処理におけるループ条件と判定ステートメントを簡素化し、コードの可読性と効率を向上させます。

この改善された説明とコードが、マージ ソート アルゴリズムをより深く理解するのに役立つことを願っています。

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