マージソートアルゴリズムのアイデア:
分割 - 征服; 各再帰プロセスには 3 つのステップが含まれます。まず、分解します。ソートされる n 個の要素のシーケンスを、それぞれが n/2 個の要素を含む 2 つのサブシーケンスに分解します。
2 番目のガバナンス: 各サブシーケンスで個別に MergeSort を呼び出し、再帰操作を実行します。 3 番目のマージ: 2 つの並べ替えられたサブシーケンスをマージして、並べ替え結果を生成します。
public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(a, tmp, left, mid);// 左ソート mergeSort(a, tmp, mid + 1, right);// 右ソート merge(a, tmp, left, mid + 1, right);//左と右をマージする} }public static void merge(int[] a, int[] tmp, int left, int rightPos, int right) { int leftEnd = rightPos - 1; int int num = right - left + 1; while (left <= leftEnd && rightPos <= right) { if (a[left] < a[rightPos]) { tmp[tmpPos++] = a[left++]; } else { tmp[tmpPos++] = a[rightPos++] } } while (left <= leftEnd) { tmp[tmpPos++] = a[left++] } while (rightPos <= right) ] = a[rightPos++]; } for (int i = 0; i < num; i++, right--) { a[right] = tmp[右]; } }マージ アルゴリズムの概略図:
以上がこの記事の全内容です。皆さんに気に入っていただければ幸いです。