Comment implémenter le tri par fusion en utilisant Java-Javacommencer-php.cn

Comment implémenter le tri par fusion en utilisant Java

王林

Libérer： 2020-03-30 16:25:51

avant

2206 Les gens l'ont consulté

Comment implémenter le tri par fusion en utilisant Java

Qu'est-ce que le tri par fusion ?

Le tri par fusion utilise des techniques de récursion et de division pour régner pour diviser la séquence de données en demi-sous-tableaux de plus en plus petits, puis trier les demi-sous-tableaux et enfin utiliser des méthodes récursives pour trier le demi-sous-tableau trié. -les tables fusionnent en séquences ordonnées de plus en plus grandes.

Idée de base

Fusionner deux séquences ordonnées en une seule grande séquence ordonnée. Par récursivité, les calques sont fusionnés, ce que l'on appelle la fusion.

(Tutoriel recommandé : Démarrage rapide Java)

Code d'implémentation :

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));
    }
}

Copier après la connexion

Résultat d'exécution :

Comment implémenter le tri par fusion en utilisant Java