Prinsip pelaksanaan algoritma pengiraan pengiraan dalam PHP

Prinsip pelaksanaan algoritma pengisihan mengira dalam PHP

Isihan mengira ialah algoritma pengisihan bukan perbandingan Idea asasnya ialah mengira kejadian setiap elemen dan kemudian meletakkannya dalam kedudukan tersusun mengikut saiz elemen. Pengisihan mengira sesuai untuk situasi di mana julat elemen adalah kecil dan terdapat banyak elemen berulang Kerumitan masa ialah O(n), dan ia merupakan algoritma pengisihan yang cekap.

Prinsip pelaksanaan:

1. Pertama, lintasi tatasusunan untuk diisih dan cari nilai maksimum dan minimum untuk menentukan saiz tatasusunan kiraan.
2. Buat tatasusunan kiraan yang panjangnya ialah perbezaan antara nilai maksimum dan nilai minimum tambah 1, dan mulakannya kepada 0.
3. Lintas tatasusunan untuk diisih sekali lagi, kira bilangan kejadian setiap elemen dan simpan nombor itu pada tatasusunan kiraan.
4. Lakukan operasi pengumpulan pada tatasusunan kiraan, iaitu jumlah elemen pada kedudukan semasa dan elemen pada kedudukan sebelumnya.
5. Buat tatasusunan sementara dengan panjang yang sama dengan tatasusunan yang hendak diisih untuk menyimpan hasil pengisihan.
6. Lintas tatasusunan untuk diisih dari belakang ke hadapan, dan gunakan nilai terkumpul dalam tatasusunan kiraan untuk meletakkan elemen pada kedudukan yang sepadan dalam tatasusunan sementara.
7. Salin elemen dalam tatasusunan sementara ke tatasusunan asal untuk melengkapkan pengisihan.

Berikut ialah contoh kod PHP:

function countSort($arr) {
    $min = min($arr); // 寻找最小值
    $max = max($arr); // 寻找最大值
    $count = array_fill($min, $max - $min + 1, 0); // 创建计数数组

    foreach ($arr as $num) {
        $count[$num]++; // 统计每个元素的出现次数
    }

    for ($i = $min + 1; $i <= $max; $i++) {
        $count[$i] += $count[$i - 1]; // 计算累加值
    }

    $temp = array_fill(0, count($arr), 0); // 创建临时数组

    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $temp[--$count[$arr[$i]]] = $arr[$i]; // 将元素放置到临时数组中的相应位置上
    }

    for ($i = 0; $i < count($arr); $i++) {
        $arr[$i] = $temp[$i]; // 将临时数组中的元素复制到原始数组中
    }

    return $arr;
}

// 测试示例
$arr = [8, 3, 5, 4, 7, 6, 1, 6, 4, 4];
$result = countSort($arr);
echo implode(' ', $result); // 输出：1 3 4 4 4 5 6 6 7 8

Di atas adalah prinsip pelaksanaan algoritma pengisihan mengira dalam PHP Dengan mengira bilangan kejadian setiap elemen, dan kemudian meletakkan elemen dalam kedudukan tersusun mengikut nombor, tatasusunan yang diisih dilaksanakan pengisihan. Algoritma ini sesuai untuk situasi di mana julat elemen adalah kecil dan terdapat banyak elemen berulang, dan operasi pengisihan boleh diselesaikan dalam masa yang lebih singkat.

Atas ialah kandungan terperinci Prinsip pelaksanaan algoritma pengiraan pengiraan dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!