Detailed explanation of radix sort algorithm in PHP

Detailed explanation of radix sorting algorithm in PHP

Radix sorting is a relatively stable and efficient sorting algorithm, which is suitable for sorting numbers. In the case of large data volumes, radix sort is more efficient than other sorting algorithms. This article will introduce the radix sorting algorithm in PHP in detail and show the implementation process of the algorithm through code examples.

The core idea of ​​radix sorting is to sort numbers according to the number of digits. First, starting from the lowest digit, sort all the numbers by single digits; then sort by tens digits; and so on until the highest digit is sorted. Each round of sorting distributes numbers into corresponding buckets until the final round of sorting is completed.

The following is an example of a radix sorting algorithm based on 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);

In the above code, first obtain the maximum value in the given array and calculate the number of digits in the maximum value. Then create an array of 10 buckets to store numbers allocated in digits. Next, perform each round of sorting through a loop. In each round of sorting, the numbers in the array are traversed and allocated to the corresponding buckets according to the current number of digits. After the sorting is completed, the numbers are taken out of the bucket and put back into the original array in order. Finally, the sorted array is returned.

Use the above code example for testing. The output results are as follows:

Before sorting: Array
(

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

)

After sorting: Array
(

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

)

As you can see, the radix sort algorithm successfully sorts the array according to numerical size.

The time complexity of the radix sort algorithm is O(k*n), where k is the maximum number of digits and n is the array length. Radix sort has lower time complexity compared to other sorting algorithms. However, the radix sort algorithm requires additional space to store the bucket array, so in the case of large data volumes, memory usage needs to be considered.

To sum up, radix sort is an efficient sorting algorithm suitable for sorting numbers. By understanding the principles and implementation process of radix sort, you can better learn and apply the algorithm.

The above is the detailed content of Detailed explanation of radix sort algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!