Implementation of PHP counting sorting algorithm (code example)

Counting sort is an algorithm for sorting a set of objects based on small integer keys; that is, it is an integer sorting algorithm. It determines the position of each key value in the output sequence by counting the number of objects with different key values ​​and using arithmetic on these numbers.

#Counting sorting is only suitable for use when the change in the key is not greater than the total number of elements. It is often used as a subroutine of another sorting algorithm (radix sort), which can handle larger keys efficiently.

In short, counting sort is a stable linear time sorting algorithm. Counting sort uses an additional array C, where the i-th element is the number of elements whose value is equal to i in the array A to be sorted. Then arrange the elements in A to the correct position according to the array C.

The usual implementation steps of the counting sorting algorithm are:

1. Find the largest and smallest elements in the array to be sorted;

2 . Count the number of occurrences of each element with value i in the array, and store it in the i-th item of array C;

3. Accumulate all counts (starting from the first element in C, each Add the item to the previous item);

4. Reverse fill the target array: put each element i in the C[i]th item of the new array, and add C[i] each time an element is placed. Subtract 1.

The implementation code example of PHP counting sorting algorithm is as follows:

<?php
function counting_sort($my_array, $min, $max)
{
    $count = array();
    for($i = $min; $i <= $max; $i++)
    {
        $count[$i] = 0;
    }

    foreach($my_array as $number)
    {
        $count[$number]++;
    }
    $z = 0;
    for($i = $min; $i <= $max; $i++) {
        while( $count[$i]-- > 0 ) {
            $my_array[$z++] = $i;
        }
    }
    return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,counting_sort($test_array, -1, 5)). PHP_EOL;

Output:

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 :-1, 0, 1, 2, 3, 4, 5

Related recommendations: "PHP Tutorial 》

This article is an introduction to the implementation method of PHP counting sorting algorithm. I hope it will be helpful to friends in need!

The above is the detailed content of Implementation of PHP counting sorting algorithm (code example). For more information, please follow other related articles on the PHP Chinese website!