Java のマージ ソート アルゴリズムの原理とその実装方法は何ですか?

1. 基本的な考え方

マージ ソートは、マージ操作に基づく効果的な並べ替えアルゴリズムです。このアルゴリズムは、分割統治法 (Divide and Conquer) を使用する非常に典型的なアプリケーションです。すでに順序付けられているサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。

2. アルゴリズム分析

1. アルゴリズムの説明

長さ n の入力シーケンスを長さ n/2 の 2 つのサブシーケンスに分割します; これら 2 つのサブシーケンスにはマージ ソートが使用されますそれぞれ; 2 つのソートされたサブシーケンスが最終的なソート シーケンスにマージされます。

2. プロセス分析

(1). 次に、項目 [1] (0 から 0 のインデックス、両側を含む) と [28] 1 から 1 のインデックス、両方を分割します。側面を含む）が結合されます。

(2)、1 (左分割)

(3) 左側の分割は空なので、28 (右側の分割) を新しい配列にコピーします。

(4). 新しい配列の要素を元の配列にコピーします。

(5)、3 (左分割)

(6). 左側の分割は空なので、21 (右側の分割) を新しい配列にコピーします。

(7)、次に、項 [1,28] (0 から 1 までのインデックス、両側を含む) と [3,21] を次のインデックスで分割します。 2 ～ 3、両面を含む）をマージします。

(8)、1 (左分割)

(9)、28 (左分割) > 3 (右分割) なので、{rightPart} を新しい配列にコピーします。

(10)、28 (左分割) > 21 (右分割) であるため、{rightPart} を新しい配列にコピーします。

(11)、右側の分割は空であるため、28 (左側の分割) を新しい配列にコピーします。

# (12)、新しい配列の要素を元の配列にコピーします。

(13)、次に、項 [11] (インデックス 4 から 4、両側を含む) とインデックス 5 から 5 の [7] を分割します。両面がすべて含まれます) が結合されます。

(14)、11 (左分割) > 7 (右分割) であるため、{rightPart} を新しい配列にコピーします。

(15)、右側の分割は空であるため、11 (左側の分割) を新しい配列にコピーします。

(16). 新しい配列の要素を元の配列にコピーします。

(17) など

(18)、1 (左分割)

(19)、3 (左分割)

(20)、21 (左分割) > 6 (右分割) であるため、{rightPart} を新しい配列にコピーします。

(21)、21 (左分割) > 7 (右分割) であるため、{rightPart} を新しい配列にコピーします。

# (22) など、新しい配列の要素を元の配列にコピーして戻します。

3. GIF デモ

3. アルゴリズムの実装

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class MergeSort {
    private static void mergeSort(int[] arr, int low, int high) {
        if (low < high) { //当子序列中只有一个元素时结束递归
            int mid = (low + high) / 2; //划分子序列
            mergeSort(arr, low, mid); //对左侧子序列进行递归排序
            mergeSort(arr, mid + 1, high); //对右侧子序列进行递归排序
            merge(arr, low, mid, high); //合并
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[arr.length]; //辅助数组
        int k = 0, i = low, j = mid + 1; //i左边序列和j右边序列起始索引,k是存放指针
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        //同上
        while (j <= high) {
            temp[k++] = arr[j++];
        }
        //复制回原数组
        for (int t = 0; t < k; t++) {
            arr[low + t] = temp[t];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

以上がJava のマージ ソート アルゴリズムの原理とその実装方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。