Shulou(Shulou.com)05/31 Report--

This article will explain in detail how to achieve counting sorting in jdk. 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 sorting is a non-comparison-based sorting algorithm. Its advantage is that when sorting integers in a certain range, its complexity is equal (n = k) (where k is the range of integers), which is faster than any comparative sorting algorithm. We may have doubts about why there are other sorting algorithms when this sorting algorithm is so fast, which requires us to synthesize the optimal time complexity and space complexity.

The bottom layer of Java implements a variety of sorting algorithms for different data, but for counting sorting, it is only effective when comparing numbers of byte types, that is, the maximum number, that is, the implementation of this algorithm is quite exquisite at the bottom of 256.Java. The basic implementation process is as follows: (you can open jdk java.util.Arrays.sort (byte []) for details.

1: initialize a count array whose size is the largest in the input array.

2: traverse the input array and add one to the corresponding position of the counting array when you encounter a number. For example, if you encounter 7, add one to the number of the seventh position in the counting array.

3: overwrite the count array directly to the output array (save space).

The source code is as follows

There is still room for optimization in this code in jdk. I can make the initialization array smaller and more memory-saving, that is, how much to initialize, for example:

For example, I enter an array {4, 1, 4, 2, 3} and initialize the array with a size of 4. (according to the theory of sorting counting in the introduction to the algorithm, that is, the size of the counting array is the largest number in the sorted array).

Establish the count array {0,0,0,0}.

Traverse the input array:

{3,4,3,2,1}-> {0,0,1,0}

{3,4,3,2,1}-> {0,0,1,1}

{3,4,3,2,1}-> {0,0,2,1}

{3,4,3,2,1}-> {0,1,2,1}

{3,4,3,2,1}-> {1,1,2,1}

The counting array is now {1, 1, 2, 1}, and we will now write it back into the input array:

{0,1,2,1}-> {1,4,3,2,1}

{0,0,2,1}-> {1,2,3,2,1}

{0,0,1,1}-> {1,2,3,2,1}

{0,0,0,1}-> {1,2,3,3,1}

{0,0,0,0}-> {1,2,3,3,4}

So it's in order.

Time: O (n + k), n is the length of the input array, k is the size of the largest number.

Space: O (n + k), n is the length of the input array, k is the size of the largest number.

This is the end of this article on "how to achieve count sorting in jdk". 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.