Java マージ ソート コードの実装プロセスの段階的な分析
はじめに:
マージ ソートは、配列を分割する古典的な分割統治アルゴリズムです。 2 つの小さな配列に分割し、次に 2 つの配列を別々にソートし、最後にソートされた 2 つの配列を 1 つの順序付き配列にマージします。この記事では、Java でのマージ ソートの実装プロセスを段階的に分析し、具体的なコード例を示します。
class MergeSort { // 归并排序函数 public void mergeSort(int[] array, int left, int right) { if (left < right) { // 找出中点 int mid = (left + right) / 2; // 递归排序左半部分和右半部分 mergeSort(array, left, mid); mergeSort(array, mid + 1, right); // 合并排序好的左半部分和右半部分 merge(array, left, mid, right); } } // 合并函数 public void merge(int[] array, int left, int mid, int right) { // 定义临时数组来存储合并后的数组 int[] temp = new int[right - left + 1]; int i = left; int j = mid + 1; int k = 0; // 将左半部分和右半部分按顺序合并到临时数组中 while (i <= mid && j <= right) { if (array[i] <= array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 将剩余的元素复制到临时数组中 while (i <= mid) { temp[k++] = array[i++]; } while (j <= right) { temp[k++] = array[j++]; } // 将临时数组中的元素复制回原数组 for (int m = 0; m < temp.length; m++) { array[left + m] = temp[m]; } } // 测试 public static void main(String[] args) { int[] array = {8, 5, 2, 9, 5, 6, 3}; int n = array.length; MergeSort mergeSort = new MergeSort(); mergeSort.mergeSort(array, 0, n - 1); System.out.println("归并排序结果:"); for (int i = 0; i < n; i++) { System.out.print(array[i] + " "); } } }
mergeSort
Method は、ソート対象の配列と配列の左右の境界を受け取るマージ ソートのエントリ関数です。この関数では、最初に左右の境界が分割の条件を満たすかどうかを判断します (つまり、left )。満たしている場合は、配列の中点を見つけて、<code>mergeSort## を再帰的に呼び出します。 . #関数は左半分と右半分をソートします。最後に、
merge 関数を呼び出して、2 つの順序付きサブ配列を 1 つの順序付き配列にマージします。
merge関数では、マージされた部分配列を格納するための一時配列を作成し、3 つのポインター
i、
j# を定義します。 # #、k
はそれぞれ、左半分の開始位置、右半分の開始位置、および一時配列の開始位置を指します。左半分と右半分の要素のサイズを比較し、小さい方の要素を一時配列に入れ、対応するポインタを 1 ビット戻します。特定の部分配列のすべての要素が一時配列に配置されている場合、部分配列の残りの要素を一時配列の末尾にコピーします。最後に、一時配列の要素を元の配列にコピーします。
以上がJava マージ ソートの実装手順の段階的な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。