Bagaimana untuk menggunakan kaedah bahagi dan takluk untuk melaksanakan algoritma isihan gabungan dalam PHP dan meningkatkan kecekapan pengisihan?

Bagaimana untuk menggunakan kaedah bahagi dan takluk untuk melaksanakan algoritma isihan gabungan dalam PHP dan meningkatkan kecekapan pengisihan?

Merge sort ialah algoritma pengisihan yang cekap Ia menggunakan idea kaedah bahagi dan takluk untuk membahagikan tatasusunan untuk diisih kepada dua bahagian, mengisih dua sub-tatasusunan masing-masing, dan kemudian mengisih. dua sub-tatasusunan. Isih gabungan boleh mengubah tatasusunan yang tidak diisih menjadi tatasusunan tertib secara stabil dengan memecahkan masalah secara berterusan kepada sub-masalah yang lebih kecil dan menggabungkan penyelesaian kepada sub-masalah tersebut.

Dalam PHP, untuk melaksanakan algoritma isihan gabungan dan meningkatkan kecekapan pengisihan, anda boleh mengikuti langkah berikut:

1. Tulis fungsi bernama mergeSort sebagai fungsi kemasukan . Fungsi ini Menerima tatasusunan untuk diisih sebagai parameter.

function mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = floor(count($arr) / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    $left = mergeSort($left);
    $right = mergeSort($right);
    return merge($left, $right);
}

2. Tentukan fungsi yang dipanggil cantum, yang digunakan untuk menggabungkan dua subarray yang diisih.

function merge($left, $right) {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    while (count($left) > 0) {
        $result[] = array_shift($left);
    }
    while (count($right) > 0) {
        $result[] = array_shift($right);
    }
    return $result;
}

Dalam fungsi mergeSort, mula-mula tentukan sama ada panjang tatasusunan kurang daripada atau sama dengan 1. Jika ya, tatasusunan asal dikembalikan terus tanpa mengisih. Jika tidak, bahagikan tatasusunan kepada dua subarray dan panggil fungsi mergeSort untuk mengisih subarray masing-masing. Akhir sekali, fungsi gabungan dipanggil untuk menggabungkan dua subarray yang diisih ke dalam tatasusunan tertib.

Dalam fungsi cantum, dua gelung sementara digunakan untuk mengeluarkan unsur-unsur yang lebih kecil daripada dua sub-tatasusunan secara berurutan dan menambahkannya pada tatasusunan hasil $hasil sehingga salah satu sub-tatasusunan kosong. Kemudian, elemen dalam subarray yang tinggal ditambah pada tatasusunan hasil mengikut tertib. Akhirnya, tatasusunan hasil dikembalikan.

Melalui langkah di atas, kita boleh menggunakan kaedah bahagi dan takluk untuk melaksanakan algoritma isihan gabungan dalam PHP, dan memandangkan kerumitan masa isihan gabungan ialah O(nlogn), dalam kes jumlah yang besar data, ia boleh Meningkatkan kecekapan pengisihan.

Kod sampel adalah seperti berikut:

$arr = [5, 3, 8, 6, 2, 9, 1, 7, 4];
$sortedArr = mergeSort($arr);
print_r($sortedArr);

Hasil output ialah: [1, 2, 3, 4, 5, 6, 7, 8, 9]#🎜 🎜##🎜 🎜#Di atas ialah kaedah dan kod sampel untuk menggunakan kaedah bahagi dan takluk untuk melaksanakan algoritma isihan gabungan dalam PHP dan meningkatkan kecekapan pengisihan. Dengan mempelajari dan memahami idea dan pelaksanaan algoritma isihan cantuman, kami boleh menggunakan dan menguasai algoritma bahagi-dan-takluk yang lain dengan lebih baik dan meningkatkan kecekapan kami dalam menyelesaikan masalah.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan kaedah bahagi dan takluk untuk melaksanakan algoritma isihan gabungan dalam PHP dan meningkatkan kecekapan pengisihan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!