How does the counting sort algorithm count?

preface

The concept is introduced

Counting sorting algorithm is a non-comparison sorting algorithm, so there is no comparison and exchange operation between elements in the sorting process
Counting sort algorithm is a practice of trading space for time, so it is faster than any comparison sort algorithm when sorting integers within a certain range

The principle of interpretation

We take the sequence [1 7 8 7 9 8 10 4] as an example to illustrate the implementation principle of counting sorting algorithm

When sorting is not started, the effect is shown below
First find the maximum value 10 and minimum value 1 in the sequence to be sorted, and then the effect is shown as follows
Create an array whose length is N= the maximum value 10- the minimum value 1+1=10. The values in the new array are all 0
Start iterating through the sequence to be sorted. The first element is 1, so place the element with value 1 at position 1 of the new array. Its value is the number of occurrences of element 1 in the original sequence 1. The effect is shown below
Continuing the loop, the second element is 7, so the element with value 7 is placed at position 7 in the new array, and its value is the number of occurrences of element 7 in the original sequence 1. The effect is shown below
Continuing through, the third element is 8, so place the element with value 8 at position 8 in the new array, and its value is the number of occurrences of element 8 in the original sequence 1. The effect is shown below
Continuing through, the fourth element is 7, so the element with value 7 is placed at position 7 in the new array, and its value is the second occurrence of element 7 in the original sequence. The effect is shown below
As we continue to iterate, the fifth element is 9, so we place the element with value 9 at position 9 in the new array, and its value is the number of occurrences of element 9 in the original sequence 1. The effect is shown below
Continuing through, the sixth element is 8, so the element with value 8 is placed at position 8 in the new array, and its value is the second occurrence of element 8 in the original sequence. The effect is shown below
Continuing through, the seventh element is 10, so the element with value 10 is placed at position 10 in the new array, and its value is the number of occurrences of element 10 in the original sequence 1. The effect is shown below
Continuing with the loop, the eighth element is 4, so the element with value 4 is placed at position 4 in the new array, and its value is the number of occurrences of element 4 in the original sequence 1. The effect is shown below
At this point, the entire array to be sorted is traversed, and the effect is shown below

Each value in the new array represents the number of times its index appears in the array to be sorted.
Finally, we iterate over the new array, printing out the subscript values of the elements of the new array as many times as they correspond to the subscript values. The effect is shown below