Pengisihan tatasusunan dan algoritma carian dalam PHP

PHP ialah bahasa pengaturcaraan yang sangat popular yang menyokong pelbagai jenis data dan algoritma, di mana pengisihan tatasusunan dan algoritma carian adalah bahagian asas dan penting. Artikel ini akan memperkenalkan algoritma pengisihan tatasusunan dan carian yang biasa digunakan dalam PHP, serta senario aplikasi dan analisis kecekapan mereka.

1. Pengisihan tatasusunan

PHP menyediakan pelbagai kaedah pengisihan tatasusunan, termasuk isihan gelembung, isihan sisipan, isihan pemilihan, isihan pantas, isihan gabungan, dsb. Berikut ialah pengenalan dan contoh kod untuk beberapa algoritma yang biasa digunakan:

1. Isih Buih (Isih Buih)

Isih Buih ialah kaedah yang mudah tetapi tidak cekap Idea asas untuk Algoritma pengisihan adalah bermula dari elemen pertama tatasusunan dan membandingkan saiz elemen bersebelahan dalam urutan Jika elemen kiri lebih besar daripada elemen kanan, kedudukannya ditukar. Selepas pusingan perbandingan ini, elemen terbesar dialihkan ke penghujung tatasusunan. Kemudian mulakan dari elemen pertama dan ulangi operasi di atas, kerumitan masa ialah O(n^2).

Kod contoh:

function bubble_sort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

2. Isih Sisipan

Isih sisipan ialah algoritma pengisihan yang agak mudah Idea asasnya ialah A data yang akan diisih ialah dimasukkan ke dalam urutan yang telah disusun untuk mencapai tujuan pengisihan. Dengan mengandaikan bahawa elemen sebelumnya telah diisih, mulakan dari elemen kedua tatasusunan dan berharap untuk mencari kedudukan yang sesuai untuk operasi sisipan. Sama seperti isihan gelembung, kerumitan masanya juga O(n^2).

Kod contoh:

function insertion_sort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
        for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$j + 1] = $temp;
    }
    return $arr;
}

3. Isih Pantas (Isih Pantas)

Isih Pantas ialah algoritma pengisihan cekap yang biasa digunakan. Idea asasnya ialah memilih Mana-mana elemen dalam tatasusunan digunakan sebagai nilai asas, dan kemudian elemen yang tinggal dibahagikan kepada dua urutan: nombor di sebelah kiri semuanya lebih kecil daripada nilai asas, dan nombor di sebelah kanan semuanya lebih besar daripada nilai asas. Kemudian ulangi langkah di atas untuk urutan kiri dan kanan sehingga panjang urutan adalah 1 atau 0. Kerumitan masa isihan pantas ialah O(n log2 n), dan ia adalah jenis tidak stabil.

Kod contoh:

function quick_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $pivot_key = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] <= $pivot_key) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($pivot_key), $right_arr);
}

2. Carian tatasusunan

Algoritma carian tatasusunan dalam PHP terutamanya termasuk carian linear, carian binari dan carian cincang. Berikut ialah pengenalan dan contoh kod untuk beberapa algoritma yang biasa digunakan:

1. Carian Linear

Carian linear ialah algoritma carian mudah Idea asasnya adalah untuk bermula dari elemen pertama tatasusunan dan bandingkan nilai dan kata kunci elemen satu demi satu untuk melihat sama ada ia adalah sama Jika ia wujud, kembalikan subskrip elemen, jika tidak -1 akan dikembalikan. Kerumitan masa carian linear ialah O(n).

Kod contoh:

function linear_search($arr, $key) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        if ($arr[$i] == $key) {
            return $i;
        }
    }
    return -1;
}

2. Carian Perduaan

Carian binari juga dipanggil carian separuh Idea asasnya ialah membahagikan tatasusunan tertib kepada Kedua-duanya bahagian membandingkan saiz elemen tengah dan kata kunci setiap kali Jika ia sama, subskrip elemen dikembalikan. Jika tidak, julat carian dikurangkan separuh mengikut perhubungan saiz sehingga elemen sasaran ditemui. Kerumitan masa carian binari ialah O(log2 n).

Kod contoh:

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($arr[$mid] == $key) {
            return $mid;
        } elseif ($arr[$mid] > $key) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

3. Carian Cincang

Carian cincang ialah algoritma carian cekap yang menggunakan jadual cincang. Idea asas adalah untuk memetakan kunci setiap elemen ke dalam jadual cincang, mengira lokasinya melalui fungsi cincang, dan kemudian cari elemen yang diperlukan di lokasi tersebut. Kerumitan masa carian cincang ialah O(1), tetapi jadual cincang perlu dibina dan diselenggara.

Di atas ialah pengenalan dan contoh kod untuk menyusun tatasusunan dan algoritma carian yang biasa digunakan dalam PHP Memilih algoritma yang berbeza mengikut senario aplikasi dan saiz data sebenar boleh meningkatkan kecekapan kod.

Atas ialah kandungan terperinci Pengisihan tatasusunan dan algoritma carian dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!