Shulou(Shulou.com)06/01 Report--

This article will explain in detail the example analysis of counting sorting in web development. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

Counting and sorting

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

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

Algorithm step

Take O (n) time to scan the entire sequence A to get the minimum min and the maximum max

Open up a new space to create a new array B of length (max-min + 1)

The value recorded by the element of index in array B is the number of occurrences of an element in A.

Finally, output the target integer sequence, the specific logic is to traverse array B, output the corresponding elements and the corresponding number

Algorithm demonstration

Process interpretation of sorting animation

First, scan the whole sequence.

The minimum value is 2 and the maximum value is 7

Create a new array containing elements of 2 to 7

Scan the sequence again and place the values of the sequence in the new array

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

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

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

Scan the number 7, the value of index 5 in the array is 7, and the number of times is 1

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

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

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

At this pace, after the scan is over, the entire sequence and the number of occurrences of each number are stored in the new array.

Finally, output the target integer sequence

Output the number 2, while the number of elements in the array with a value of 2 with index 0 becomes 0

Output the number 3, while the number of elements in the array with a value of 3 with index 1 becomes 1

With the same operation, the whole sequence is completely output.

Code implementation

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

Go code implementation

Java code implementation

Python code implementation

JavaScript code implementation

This is the end of this article on "sample Analysis of count sorting in web Development". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.