ホームページ > Java > &#&チュートリアル > マージソートアルゴリズム

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

Susan Sarandon
リリース: 2025-01-21 22:04:18
オリジナル
862 人が閲覧しました

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

Merge Sort Algorithm

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

アルゴリズムのデモ

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

Merge Sort Algorithm

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

Merge Sort Algorithm

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

Merge Sort Algorithm

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

Merge Sort Algorithm

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

Merge Sort Algorithm

コード実装 (Java)

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

<code class="language-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++];
        }
    }
}</code>
ログイン後にコピー

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

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

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

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート