マージソートアルゴリズムの理解 (Java の例付き)

マージソート: 総合ガイド

マージ ソートは、独立して、またはハイブリッド アプローチの一部として、さまざまなプログラミング言語で頻繁に使用される、非常に効率的な並べ替えアルゴリズムです。 その基礎は分割統治パラダイムにあります。つまり、問題は小さなサブ問題に分割され、個別に解決され、最終結果を得るためにそれらの解決策が組み合わされます。 マージソートは、入力リストを再帰的に半分に分割し、それぞれをソートしてから、ソートされた半分をマージして、完全にソートされたリストを生成します。

マージソートプロセスを理解する

配列の例を使用して、マージソートプロセスを説明してみましょう:

この画像は、配列の再帰的除算を示しています。

この画像は、ソートされた部分配列のマージを示しています。

マージソートの実装

以下はマージソートアルゴリズムの Java 実装です:

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

コードの説明

mergeSort メソッドは、部分配列に要素が 1 つだけ含まれるまで配列を再帰的に分割します。 merge メソッドは重要です。ソートされた部分配列を取得し、それらを単一のソートされた配列に効率的にマージします。 マージ プロセスには、両方のサブ配列の要素を比較し、小さい方の要素をメイン配列に配置することが含まれます。

この画像は結合ステップを示しています。

コードの出力は次のとおりです:

ソートされていない配列: [8, 2, 6, 4, 9, 1] ソートされた配列: [1, 2, 4, 6, 8, 9]

アルゴリズムの複雑さ

• 時間計算量: すべてのケース (最良、平均、最悪) で O(n log n)。これは、入力配列の初期順序に関係なく、分割統治アプローチが一貫しているためです。
• スペースの複雑さ: O(n)。マージ操作中に一時配列に必要な追加スペースが原因です。

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