Bagaimana untuk melaksanakan algoritma pengisihan gabungan menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma isihan gabungan

Pengenalan:
Isih gabung ialah algoritma isihan klasik berdasarkan kaedah bahagi dan takluk Ideanya adalah untuk membahagikan tatasusunan untuk diisih kepada lapisan sub-tatasusunan yang lebih kecil mengikut lapisan, dan kemudian lulus Operasi cantum secara berurutan menggabungkan subarrays ke dalam tatasusunan keseluruhan tersusun. Dalam artikel ini, kami akan memperkenalkan secara terperinci cara melaksanakan algoritma isihan gabungan menggunakan Java dan memberikan contoh kod khusus.

Langkah algoritma:
Algoritma isihan gabungan terutamanya merangkumi tiga langkah: pemisahan, penggabungan dan pengisihan. . Dari segi pelaksanaan khusus, kaedah rekursif boleh digunakan untuk membahagikan tatasusunan secara berterusan kepada dua sehingga panjang tatasusunan ialah 1.

Gabung:
1. Seterusnya, kita perlu menggabungkan sub-tatasusunan berpecah lapisan demi lapisan. Dari segi pelaksanaan khusus, anda boleh bermula dari sub-array bawah dan menggabungkan dua sub-array bersebelahan untuk membentuk sub-array tertib baharu. Kemudian, gabungkan ke atas lapisan demi lapisan sehingga keseluruhan tatasusunan digabungkan. Operasi cantum boleh menggunakan kaedah penunjuk berganda untuk membandingkan unsur-unsur dua sub-tatasusunan secara bergilir-gilir, dan meletakkan elemen yang lebih kecil ke dalam tatasusunan hasil sehingga kedua-dua sub-tatasusunan telah dilalui.
   
Isih:
2. Akhir sekali, selepas gabungan selesai, keseluruhan tatasusunan adalah teratur. Kerumitan masa algoritma bergantung pada bilangan operasi pemisahan dan gabungan, iaitu, pada bilangan tahap pengulangan. Khususnya, kerumitan masa ialah O(nlogn), dengan n ialah panjang tatasusunan.
   
3. Pelaksanaan kod Java:
   Berikut ialah contoh kod algoritma isihan cantuman yang ditulis dalam Java:

public class MergeSort {
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

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

    public static void main(String[] args) {
        int[] arr = { 38, 27, 43, 3, 9, 82, 10 };
        mergeSort(arr, 0, arr.length - 1);

        System.out.println("归并排序后的数组为：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Analisis kod:

Kod sampel di atas melaksanakan tiga langkah pemisahan, penggabungan dan pengisihan algoritma isihan gabungan. Antaranya, kaedah merge() digunakan untuk menggabungkan dua subarray tertib, dan kaedah mergeSort() digunakan untuk membahagi dan menggabungkan tatasusunan secara rekursif. Dalam kaedah main(), kita boleh memanggil kaedah mergeSort() dengan menghantar tatasusunan untuk diisih, dan akhirnya mendapatkan tatasusunan tertib.

Ringkasan:

Isih Gabung ialah algoritma pengisihan yang cekap yang boleh mencapai prestasi yang baik dalam kes yang paling teruk. Isih Cantum boleh mengisih tatasusunan dari mana-mana panjang dengan membelah dan menggabungkan tatasusunan untuk diisih lapisan demi lapisan. Dalam aplikasi praktikal, kita boleh menggunakan pengisihan gabungan untuk menyelesaikan masalah pengisihan data berskala besar.

Saya harap artikel ini akan membantu anda memahami dan menggunakan algoritma isihan gabungan, terima kasih kerana membaca!

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pengisihan gabungan menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!