Learn the principles and time complexity analysis of counting sorting algorithm in PHP.

Learn the principle and time complexity analysis of counting sorting algorithm in PHP

Counting sorting is a non-comparative sorting algorithm, suitable for small and known data ranges in the case of. Its basic idea is to count the number of occurrences of each element and then fill it into the output array in order to achieve sorting. This article will introduce the principles, steps and time complexity analysis of counting sorting, and provide specific PHP code examples.

1. Principle:
   The principle of counting sorting is relatively simple. Assume that the array to be sorted is an array, and the element range is [0, k]. We need to first create a counting array count with a size of k 1 to count the number of occurrences of each element. While iterating over the original array, the elements are counted and stored in the count array. Then, we sequentially accumulate the elements in the count array to determine the position of the element in the output array. Finally, traverse the original array array and place each element into the corresponding position (according to the index in count) to complete the sorting.
2. Steps:
3. Create a count array count with a size of k 1 and initialize it to 0.
4. Traverse the original array array, count the number of occurrences of each element, and store it in the count array.
5. Accumulate the count array to determine the position of each element in the output array.
6. Create an output array output with the same size as the original array.
7. Traverse the original array array again and place each element into the output array according to the index in the count array.
8. The output array output is the result after counting sorting.
9. Time complexity analysis:
10. The time complexity of creating the count array is O(k).
11. The time complexity of traversing the original array and counting the occurrences of each element is O(n).
12. The time complexity of accumulating the count array is O(k).
13. The time complexity of creating the output array is O(n).
14. The time complexity of traversing the original array again and placing elements into the output array is O(n).
15. The total time complexity is O(k) O(n) O(k) O(n) O(n), which is simplified to O(n k).

The following is a code example of using the PHP language to implement the counting sorting algorithm:

function countingSort($array)
{
    $maxValue = max($array);
    $count = array_fill(0, $maxValue + 1, 0);
    $n = count($array);

    foreach ($array as $value) {
        $count[$value]++;
    }

    for ($i = 1; $i <= $maxValue; $i++) {
        $count[$i] += $count[$i - 1];
    }

    $output = array_fill(0, $n, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        $output[$count[$array[$i]] - 1] = $array[$i];
        $count[$array[$i]]--;
    }

    return $output;
}

$array = [4, 2, 0, 1, 3, 2, 1]; // 待排序数组
$sortedArray = countingSort($array);
print_r($sortedArray);

The above is the content of learning the principle and time complexity analysis of the counting sorting algorithm in PHP. I hope this helps you understand counting sorting.

The above is the detailed content of Learn the principles and time complexity analysis of counting sorting algorithm in PHP.. For more information, please follow other related articles on the PHP Chinese website!