マージソートアルゴリズムについての深い理解
マージソートアルゴリズムの核となる考え方は分割統治法、つまり「分割統治」です。各部分配列に要素が 1 つだけ含まれるまで (現在はソートされています)、配列をより小さな部分配列に再帰的に分割します。次に、これらの部分配列をより大きなソートされた配列にマージします。ソートプロセスは分割フェーズではなくマージフェーズ中に発生することに注意してください。
アルゴリズムのデモ
並べ替える配列があるとします。
配列を左と右のサブ配列に分割します。
各部分配列の要素が 1 つだけになるまで再帰的分割を続けます:
次に、これらの部分配列をマージして並べ替えます。小さい値が左側、大きい値が右側になります。
最終的に並べ替えられた:
コード実装 (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 サイトの他の関連記事を参照してください。