Java のマージソートアルゴリズムを実装して最適化する

Java マージ ソート アルゴリズムの実装と最適化

マージ ソートは比較に基づくソート アルゴリズムであり、その主なアイデアは、ソートされるシーケンスをいくつかのサブに分割することです。 - シーケンス、各サブシーケンスを並べ替え、最後に順序付けられたサブシーケンスを全体の順序付けされたシーケンスにマージします。

1. マージ ソート アルゴリズムの実装:
   マージ ソート アルゴリズムの実装は、分割統治とマージの 2 つのステップに分けることができます。

(1) 分割統治:
まず、ソート対象のシーケンスを、各部分シーケンスの要素が 1 つだけになるまで 2 つの部分に分割します。次に、これらのサブシーケンスは順序付けられたサブシーケンスにマージされます。

以下は、マージ ソート アルゴリズムの再帰的実装のサンプル コードです。

public 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 l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

(2) マージ:
マージ関数の機能は、2 つの順序付けられたサブシーケンスをマージすることです。 1 つの順序付けられたシーケンス。特定の実装では、マージされた結果を保存するための一時配列を作成する必要があります。サブシーケンスを走査するときは、サブシーケンス内の要素を比較し、小さい方の要素を一時配列に入れ、対応するポインタを移動します。最後に、一時配列内の要素が元の配列にコピーされて戻されます。

2. マージ ソート アルゴリズムの最適化:
   マージ ソート アルゴリズムは、再帰プロセス中に多くの一時的なサブシーケンス配列を生成します。これにより、メモリの割り当てと解放が頻繁に行われ、メモリのスペースの複雑さが増加します。アルゴリズム、支出。このオーバーヘッドを削減するために、次の最適化方法によってマージ ソート アルゴリズムの効率を向上させることができます。

(1) 小規模なサブシーケンスには挿入ソートを使用します。サブシーケンスのサイズが比較的小さい場合は、挿入ソートの方が効率的です。したがって、マージ ソートの再帰処理中に、部分列のサイズが特定のしきい値未満の場合、再帰処理を挿入ソートを使用して置き換えることができます。

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        if (right - left <= THRESHOLD) {
            // 子序列的规模小于阈值，采用插入排序
            insertionSort(array, left, right);
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

(2) マージ プロセスの最適化:

マージ プロセス中、最初に 2 つのサブシーケンスを 2 つの一時配列に格納し、次に 2 つの一時配列を元の配列にマージできます。こうすることで、マージ プロセス中に一時配列を繰り返し作成することを回避できます。同時に、一時配列のサイズは固定されているため、再帰プロセス中に繰り返し作成されることを避けるために、クラスのメンバー変数として定義できます。

public class MergeSort {
    private int[] temp;

    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            if (right - left <= THRESHOLD) {
                insertionSort(array, left, right);
            } else {
                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 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 l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }
}

要約すると、上記は Java マージ ソート アルゴリズムの実装とその最適化方法です。マージ プロセスを最適化し、小規模なサブシーケンスに挿入ソートを使用することにより、マージ ソート アルゴリズムの効率が向上し、スペースのオーバーヘッドを削減できます。実際のアプリケーションでは、適切な最適化方法を選択し、並べ替えシーケンスの特性に基づいて合理的な選択を行うことで、アルゴリズムをより効率的にすることができます。

以上がJava のマージソートアルゴリズムを実装して最適化するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。