Home > Article > Backend Development > 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:
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!