Implementation principle of counting sort algorithm in PHP

Principle of implementation of counting sorting algorithm in PHP

Counting sorting is a non-comparative sorting algorithm. Its basic idea is to count the occurrences of each element and then place it according to its size. into an orderly position. Counting sorting is suitable for situations where the range of elements is small and there are many repeated elements. The time complexity is O(n), and it is an efficient sorting algorithm.

Implementation principle:

1. First, traverse the array to be sorted and find the maximum and minimum values ​​to determine the size of the counting array.
2. Create a count array whose length is the difference between the maximum value and the minimum value plus 1, and initialized to 0.
3. Traverse the array to be sorted again, count the number of occurrences of each element, and save the number to the count array.
4. Perform an accumulation operation on the counting array, that is, sum the elements at the current position and the elements at the previous position.
5. Create a temporary array with the same length as the array to be sorted to store the sorting results.
6. Traverse the array to be sorted from back to front, and use the accumulated value in the count array to place the elements at the corresponding positions in the temporary array.
7. Copy the elements in the temporary array to the original array to complete the sorting.

The following is a PHP code example:

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

The above is the implementation principle of the counting sorting algorithm in PHP. By counting the number of occurrences of each element, the elements are then placed according to the number of times. In the order position, the sorting of the array to be sorted is implemented. This algorithm is suitable for situations where the range of elements is small and there are many repeated elements, and the sorting operation can be completed in a shorter time.

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