Penjelasan terperinci tentang algoritma isihan radix dalam PHP

Penjelasan terperinci tentang algoritma isihan radix dalam PHP

Isihan Radix ialah algoritma isihan yang agak stabil dan cekap, yang sesuai untuk mengisih nombor. Dalam kes volum data yang besar, isihan radix adalah lebih cekap daripada algoritma pengisihan lain. Artikel ini akan memperkenalkan algoritma pengisihan radix dalam PHP secara terperinci dan menunjukkan proses pelaksanaan algoritma melalui contoh kod.

Idea teras pengisihan radix adalah untuk mengisih nombor mengikut bilangan digit. Mula-mula, mulai dari digit paling rendah, susun semua nombor dengan satu digit kemudian susun dengan sepuluh digit dan seterusnya sehingga digit tertinggi diisih. Setiap pusingan pengisihan mengagihkan nombor ke dalam baldi yang sepadan sehingga pusingan akhir pengisihan selesai.

Berikut ialah contoh algoritma pengisihan radix berdasarkan PHP:

function radixSort($array) {
    // 获取最大值
    $max = max($array);
    
    // 获取最大值的位数
    $numDigits = strlen((string) $max);
    
    // 创建桶数组
    $buckets = array_fill(0, 10, []);
    
    for ($i = 0; $i < $numDigits; $i++) {
        // 将数字分配到桶中
        foreach ($array as $num) {
            $digit = floor($num / pow(10, $i)) % 10;
            $buckets[$digit][] = $num;
        }
        
        // 将数字从桶中取出，并按顺序放回原数组
        $array = [];
        for ($j = 0; $j < 10; $j++) {
            foreach ($buckets[$j] as $num) {
                $array[] = $num;
            }
            $buckets[$j] = [];
        }
    }
    
    return $array;
}

// 测试排序算法
$array = [23, 6, 78, 12, 456, 2, 56, 11];
$result = radixSort($array);

echo "排序前：";
print_r($array);

echo "排序后：";
print_r($result);

Dalam kod di atas, mula-mula dapatkan nilai maksimum dalam tatasusunan yang diberikan dan kirakan bilangan digit dalam nilai maksimum. Kemudian buat tatasusunan 10 baldi untuk menyimpan nombor yang diperuntukkan dalam digit. Seterusnya, lakukan setiap pusingan pengisihan melalui gelung. Dalam setiap pusingan pengisihan, nombor dalam tatasusunan dilalui dan diperuntukkan kepada baldi yang sepadan mengikut bilangan digit semasa. Selepas pengisihan selesai, nombor dikeluarkan dari baldi dan dimasukkan semula ke dalam tatasusunan asal mengikut tertib. Akhirnya, tatasusunan yang diisih dikembalikan.

Gunakan contoh kod di atas untuk ujian, dan hasil output adalah seperti berikut:

Sebelum mengisih: Array
(

[0] => 23
[1] => 6
[2] => 78
[3] => 12
[4] => 456
[5] => 2
[6] => 56
[7] => 11

)

Selepas mengisih: Array
(

[0] => 2
[1] => 6
[2] => 11
[3] => 12
[4] => 23
[5] => 56
[6] => 78
[7] => 456

)

anda boleh lihat

)

algoritma isihan radix berjaya mengisih tatasusunan Diisih mengikut saiz berangka.

Kerumitan masa algoritma isihan radix ialah O(k*n), dengan k ialah bilangan digit maksimum dan n ialah panjang tatasusunan. Isihan Radix mempunyai kerumitan masa yang lebih rendah berbanding dengan algoritma pengisihan lain. Walau bagaimanapun, algoritma isihan radix memerlukan ruang tambahan untuk menyimpan tatasusunan baldi, jadi dalam kes volum data yang besar, penggunaan memori perlu dipertimbangkan.

Ringkasnya, isihan radix ialah algoritma pengisihan yang cekap sesuai untuk mengisih nombor. Dengan memahami prinsip dan proses pelaksanaan isihan radix, anda boleh mempelajari dan menggunakan algoritma dengan lebih baik. 🎜

Atas ialah kandungan terperinci Penjelasan terperinci tentang algoritma isihan radix dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!