What is counting sort?

Counting sort is not a comparison-based sorting algorithm. Its core is to convert the input data values into keys and store them in an extra array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range

The most important thing about counting sort is that integers in the range, say, 0 to 10, have values in the array between 0 and 10

chestnuts

Sequence: 9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9, 7,9

First determine that the range of the sequence is 0-10, and list the sequence of ranges, as shown in Figure 1

For example, if the first integer is 9, then the element with index 9 in the array is added by 1

Figure 1 #

The second integer is 3, so the element with subscript 3 in the array is added by 1, as shown in Figure 2

Figure 2 #

And so on…

The state after the final traversal is as follows, as shown in Figure 3

# 3

The value of each subscript position in the array represents the number of occurrences of the corresponding integer in the sequence

With this “statistical result,” sorting is easy. Iterate through the array directly, output the subscript value of the array element, the value of the element is several, output several times

0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10

The final output sequence is already sorted

At this point one might ask, what if the minimum of the sequence doesn’t start at zero?

That’s when you compute the offset

How do I calculate the offset?

Take the minimum value of the sequence as the offset. For example, if the minimum value is 90, then the index of the statistics array for the integer 95 is 95-90 = 5

Resources: Top 10 Classic sorting Algorithms comics: What is Counting Sorting?

The content/inspiration of the article is taken from below

  • Continuous maintenance/update 500+ front end questions/notes github.com/noxussj/Int…

  • [Big data visualization chart plug-in] www.npmjs.com/package/ns-…

  • [3D city modeling using three.js (Zhuhai)] 3D.noxussJ.top /