Javaを使用してマージソートを実装する方法

マージソートとは何ですか?

マージ ソートでは、再帰および分割統治手法を使用して、データ シーケンスをますます小さい半分のサブテーブルに分割し、次に半分のサブテーブルを並べ替え、最後に再帰的手法を使用して並べ替えられた半分のサブテーブルを並べ替えます。 -テーブルは、ますます大きな順序付けされたシーケンスにマージされます。

中心的なアイデア

2 つの順序付けられたシーケンスを結合して、大きな順序付けられたシーケンスにします。再帰によりレイヤーが結合されます。これをマージといいます。

(推奨チュートリアル: java クイック スタート)

実装コード:

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/1/13
 */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

実行結果:

推奨される関連ビデオ チュートリアル: Java ビデオ チュートリアル

以上がJavaを使用してマージソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。