Memahami Algoritma Isih Gabung (dengan Contoh dalam Java)

Isih Gabungan: Panduan Komprehensif

Merge Sort ialah algoritma pengisihan yang sangat cekap yang kerap digunakan dalam pelbagai bahasa pengaturcaraan, sama ada secara bebas atau sebagai sebahagian daripada pendekatan hibrid. Asasnya terletak pada paradigma Divide and Conquer: masalah dipecahkan kepada submasalah yang lebih kecil, diselesaikan secara individu, dan penyelesaiannya digabungkan untuk hasil akhir. Gabung Isih membahagikan senarai input secara rekursif kepada separuh, mengisih setiap separuh, dan kemudian menggabungkan bahagian yang diisih untuk menghasilkan senarai yang diisih sepenuhnya.

Memahami Proses Isih Gabung

Mari kita gambarkan proses Isih Gabung menggunakan tatasusunan contoh:

Imej ini menggambarkan pembahagian rekursif tatasusunan.

Imej ini menunjukkan penggabungan subarray yang diisih.

Melaksanakan Isih Gabung

Di bawah ialah pelaksanaan Java bagi algoritma Isih Gabung:

<code class="language-java">import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

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

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}</code>

Penjelasan Kod

Kaedah mergeSort membahagikan tatasusunan secara rekursif sehingga subarray hanya mengandungi satu elemen. Kaedah merge adalah penting; ia mengambil subarray yang diisih dan menggabungkannya dengan cekap ke dalam tatasusunan tersusun tunggal. Proses penggabungan melibatkan membandingkan elemen daripada kedua-dua subarray dan meletakkan elemen yang lebih kecil ke dalam tatasusunan utama.

Imej ini menggambarkan langkah penggabungan.

Keluaran kod ialah:

Tatasusunan tidak diisih: [8, 2, 6, 4, 9, 1] Tatasusunan diisih: [1, 2, 4, 6, 8, 9]

Kerumitan Algoritma

• Kerumitan Masa: O(n log n) dalam semua kes (terbaik, purata dan paling teruk). Ini kerana pendekatan bahagi-dan-takluk kekal konsisten tanpa mengira susunan awal tatasusunan input.
• Kerumitan Ruang: O(n) disebabkan oleh ruang tambahan yang diperlukan untuk tatasusunan sementara semasa operasi gabungan.

Atas ialah kandungan terperinci Memahami Algoritma Isih Gabung (dengan Contoh dalam Java). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!