Algoritma Isih Gabung

Pemahaman mendalam tentang algoritma isihan gabungan

Idea teras algoritma isihan gabungan ialah kaedah bahagi dan takluk, iaitu, "bahagi dan takluk". Ia membahagikan tatasusunan secara rekursif kepada subarray yang lebih kecil sehingga setiap subarray mengandungi hanya satu elemen (yang kini diisih). Ia kemudian menggabungkan subarray ini ke dalam tatasusunan tersusun yang lebih besar. Perlu diingat bahawa proses pengisihan berlaku semasa fasa gabungan, bukan fasa perpecahan.

Demonstrasi Algoritma

Andaikan kita mempunyai tatasusunan untuk diisih:

Kami membahagikan tatasusunan kepada dua subtatasusunan kiri dan kanan:

Teruskan pemisahan rekursif sehingga setiap subarray hanya mempunyai satu elemen:

Seterusnya, gabungkan dan susun subarray ini: nilai yang lebih kecil di sebelah kiri, nilai yang lebih besar di sebelah kanan.

Akhirnya diisih:

Pelaksanaan kod (Java)

Kod Java asal mempunyai beberapa isu kecekapan yang boleh kami optimumkan. Kod yang dipertingkatkan adalah seperti berikut:

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < left.length || rightIndex < right.length) {
        if (leftIndex < left.length && (rightIndex >= right.length || left[leftIndex] <= right[rightIndex])) {
            array[arrayIndex++] = left[leftIndex++];
        } else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

Kod yang dioptimumkan ini menggunakan kaedah Arrays.copyOfRange() untuk menyalin elemen tatasusunan dengan lebih cekap, dan memudahkan keadaan gelung dan pernyataan pertimbangan dalam proses penggabungan, sekali gus meningkatkan kebolehbacaan dan kecekapan kod.

Semoga penjelasan dan kod yang dipertingkatkan ini dapat membantu anda memahami algoritma isihan gabungan dengan lebih baik!

Atas ialah kandungan terperinci Algoritma Isih Gabung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!