Since many algorithm problems in LeetCode involve some basic data structures, in order to better understand the animation of some complex problems updated later, a new series —– “Illustrated Data Structures” is launched, mainly using animation to describe common data structures and algorithms. This series includes ten kinds, heap, queue, tree, and search set, graph and so on about dozens of articles.

You can learn algorithm in five minutes to get more sorting content in the public account

Count sorting

Counting sort is a kind of sorting algorithm which is not based on comparison. Its spatial complexity and time complexity are O(n+k), where K is the range of integers. The minimum time complexity of comparison sorting algorithm is O(nlogn). The algorithm was proposed by Harold H. Seward in 1954.

The core of counting sort is to convert input data values into keys and store them in extra array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.

Algorithm steps

  1. Take O(n) time to scan the entire sequence A to get min and Max

  2. Create a new array B of length (max-min + 1)

  3. The element of index in array B records the number of occurrences of an element in A

  4. Finally output the sequence of target integers, the specific logic is to traverse the number group B, output the corresponding elements and the corresponding number

Algorithm demo

Sort animation process explanation

  1. First, scan the entire sequence

  2. Obtain a minimum value of 2 and a maximum value of 7

  3. Create an array that contains elements from 2 to 7

  4. Scan the sequence again, placing the values of the sequence in the newly created array

  5. Scan the number 5, the value of index 3 in the array is 5, the number of times 1

  6. Scan the number 3, the value of index 1 in the array is 3, the number of times is 1

  7. Scan the number 4, the value of index 2 in the array is 4, the number of times is 1

  8. Scan the number 7, the value of index 5 in the array is 7, the number is 1

  9. Scan the number 2, the value of index 0 in the array is 2, the number of times 1

  10. Scan the number 4, the value of index 2 in the array is 4, the number of times is 2

  11. Scan the number 3, the value of index 1 in the array is 3, the number of times is 2

  12. At this pace, after the scan, a new array is created to store the entire sequence and the number of occurrences of each number

  13. Finally, the target integer sequence is output

  14. Print the number 2, and the number of elements in the array whose index is 0 becomes 0

  15. Print the number 3, and the number of elements in the array whose index is 1 becomes 1

  16. Do the same, and the entire sequence is printed out

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post a variety of programming language reference code, code all from the Internet.

Go code implementation

Java code implementation

Python code implementation

JavaScript code implementation

If you’re an iOS developer, you can go to GitHub at github.com/MisterBooo/… Get more intuitive debug run source code.

You can learn algorithm in five minutes to get more sorting content in the public account