Bagaimanakah Kita Boleh Menggabungkan Dua Tatasusunan Isih dengan Cekap?

Menggabungkan Tatasusunan Isih Dengan Cekap: Kaedah Yang Diperbaiki

Untuk menggabungkan dua tatasusunan yang diisih ke dalam tatasusunan tunggal, beberapa pendekatan pengaturcaraan boleh digunakan. Walau bagaimanapun, salah satu teknik yang paling cekap dan kerap disyorkan adalah seperti berikut:

Algoritma ini berulang melalui kedua-dua tatasusunan secara serentak, membandingkan elemen pada setiap indeks semasa dan menambahkan elemen yang lebih kecil pada tatasusunan output. Proses ini berterusan sehingga salah satu tatasusunan habis. Sebarang elemen yang tinggal dalam tatasusunan lain kemudiannya dilampirkan.

Berikut ialah contoh pelaksanaan yang dioptimumkan bagi algoritma ini dalam Java:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)
        answer[k++] = a[i] < b[j] ? a[i++] : b[j++];

    while (i < a.length)
        answer[k++] = a[i++];

    while (j < b.length)
        answer[k++] = b[j++];

    return answer;
}

Pendekatan ini mempunyai kerumitan masa O(n m ), di mana n dan m masing-masing mewakili panjang tatasusunan a dan b. Versi yang dipertingkatkan ini menghapuskan pemeriksaan yang tidak perlu untuk keletihan dan menggunakan pembinaan gelung semasa yang padat untuk penggabungan yang cekap.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Menggabungkan Dua Tatasusunan Isih dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!