Java マージ ソートの実装手順の段階的な分析

Java マージ ソート コードの実装プロセスの段階的な分析

はじめに:
マージ ソートは、配列を分割する古典的な分割統治アルゴリズムです。 2 つの小さな配列に分割し、次に 2 つの配列を別々にソートし、最後にソートされた 2 つの配列を 1 つの順序付き配列にマージします。この記事では、Java でのマージ ソートの実装プロセスを段階的に分析し、具体的なコード例を示します。

1. 基本的な考え方:
   マージソートの基本的な考え方は、ソート対象の配列を 2 つの小さなサブ配列に再帰的に分割し、次に 2 つのサブ配列をソートし、それらをマージするのは順序付けされた配列です。このプロセスは、最小のサブ配列の要素が 1 つだけになるまで再帰的に続行され、これらの順序付けされたサブ配列をマージすることでソートが完了します。
2. 実装プロセス:
   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] + " ");
        }
    }
}

3. 例の説明:
   上記のコードでは、 mergeSortMethod は、ソート対象の配列と配列の左右の境界を受け取るマージ ソートのエントリ関数です。この関数では、最初に左右の境界が分割の条件を満たすかどうかを判断します (つまり、left )。満たしている場合は、配列の中点を見つけて、<code>mergeSort## を再帰的に呼び出します。 . #関数は左半分と右半分をソートします。最後に、merge 関数を呼び出して、2 つの順序付きサブ配列を 1 つの順序付き配列にマージします。

merge関数では、マージされた部分配列を格納するための一時配列を作成し、3 つのポインター i、j# を定義します。 # #、k はそれぞれ、左半分の開始位置、右半分の開始位置、および一時配列の開始位置を指します。左半分と右半分の要素のサイズを比較し、小さい方の要素を一時配列に入れ、対応するポインタを 1 ビット戻します。特定の部分配列のすべての要素が一時配列に配置されている場合、部分配列の残りの要素を一時配列の末尾にコピーします。最後に、一時配列の要素を元の配列にコピーします。

概要:

マージ ソート アルゴリズムは、ソート対象の配列を再帰的に小さなサブ配列に分割し、これらの順序付けされたサブ配列をマージすることで全体的なソートを実現します。実際には、マージ ソート アルゴリズムの時間計算量は O(nlogn) であり、他のソート アルゴリズムよりも優れた安定性とスケーラビリティを備えています。 Java マージ ソート コードの実装プロセスを徐々に分析することで、その基本的な考え方と実装方法をより深く理解できるようになります。
4. 
   

以上がJava マージ ソートの実装手順の段階的な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。