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

This article mainly introduces "how to achieve counting sorting". In the daily operation, I believe that many people have doubts about how to achieve counting sorting. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts of "how to achieve counting sorting"! Next, please follow the editor to study!

Because the benefit this year is good, the boss wants to give some small benefits to the employees and let the waiter rank them according to their seniority, but the company has 100000 employees and has been in business for 10 years, ranging from 0 to 10 years of service.

It seems that this is really an arduous task.

Of course we can solve it with the help of merge sorting and quick sorting mentioned earlier, but do we have any other better ways?

The brother who knows the sorting algorithm may have guessed what to write today. Yes, today we are going to write about the linear order of space for time.

Before we talk about it, let's review the previous sorting algorithm. The best time complexity is O (nlogn), and the sorting is based on the comparison between elements.

Let's talk about the sorting algorithm which is not based on element comparison, and the time complexity is O (n), and the time complexity is linear, so we call it linear sorting algorithm.

Its advantage is that when sorting integers in a certain range, its complexity is equal (n = k), and k represents the range of integers. Faster than any comparative sorting algorithm, but it also needs to sacrifice some space in exchange for time.

Let's first take a look at what the counting sort is, and what does this count mean?

We assume that there are 10 employees in a branch store.

The length of service is 1, 2, 3, 5, 0, 2, 2, 4, 5, 9, 4, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5.

So we store it in an array of length 10, but we notice that what our array stores at this time is not the value of the element, but the number of elements. See the picture below

Note: at this time, the array length of the statistical times here is determined according to the maximum value. In the above example, the maximum value is 9, then the length is 9 + 1 = 10. Let's understand it this way for a while, and we'll optimize it later.

Let's continue with the example in the figure above to illustrate that in this array, the index represents the element value (that is, the length of service in the above example), and the value of the array represents the number of elements (that is, the number of times different seniority occurs).

In other words, there are 1 employee with 0 seniority, 1 employee with 1 seniority, and 3 employees with 2 seniority.

Then we take them out in turn according to the number of occurrences to see what the effect is.

0,1,2,2,2,3,4,5,5,9

We find that the elements are ordered at this time, but this is not sorting, but simply according to the subscript of the statistical array, the element value is output, and the original array is not really sorted.

After this operation, we do not know which employee's seniority belongs to.

See the picture below

Give an example

Although Brother Meow and Brother Jie have the same length of service, if we output according to the above operation, we cannot know which of the two employees with a seniority of 4 is Brother Meow and Brother Jie.

So we need to sort the elements in other ways.

Do you remember the prefixes and the prefixes we talked about before? let's find out the prefixes and arrays from the array of statistical times above.

Since we get prefixes and arrays by counting the number of times, let's analyze the meaning of the face value in the presum array.

For example, our presum [2] = 5 means that the original array has 5 values less than or equal to 2. Presum [4] = 7 means there are seven elements less than or equal to 4.

Do you feel that the meaning of counting and sorting is going to be revealed slowly.

As a matter of fact, we can already understand it so far, and we are still short of the last step.

At this point, we need to traverse the original array from back to front, then put the traversed elements in the appropriate position of the temporary array, and modify the value of the presum array. After traversing, the sorting is achieved.

At this time, someone is going to ask, why do we have to go through it from back to front?

The answer to this question, we'll talk about it later, let's move on.

Counting and sorting

We traverse from back to front, nums [9] = 9, then we take this value to look in the presum array and find that presum [nums [9]] = presum [9] = 10

Do you remember the meaning of each value in our presum array? when we presum [9] = 10, it means that there are 10 numbers less than or equal to in the array, then we have to put him in the 10th position of the temporary array, that is, temp [9] = 9.

What else do we need to do? Let's think about it, we've put 9 in the temp array, and we've sorted it, so our presum array should no longer count him, so we can subtract the corresponding position by 1, that is, presum [9] = 10-1 = 9.

Let's continue to traverse 5, and then perform the same appeal steps.

We continue to query the presum array and find that presum [5] = 9, which means that there are 9 numbers less than or equal to 5, and we put them in the ninth position of the temp array, that is,

Temp [8] = 5. Then subtract 1 from presum [5].

Is not here to understand the general idea of counting and sorting.

So why do we need to traverse from back to front? Let's think about it, if we traverse the same element from the back, the previous element will return first and then minus one, which will make the counting sort an unstable sorting algorithm.

Is this sorting process like looking up a dictionary? By querying the presum array, you can figure out where you should rank in the temporary array. Then modify the dictionary until the traversal is over.

So let's first animate our bug version of the counting order to deepen our understanding.

Note: our process of getting the presum array is omitted in the animation. Directly simulate the sorting process.

But is it over by now? Obviously not. Let's think about the situation.

If we set the length of the presum array according to the above method, then we need to set the length of the array to 95 (because the maximum is 94), which is obviously unreasonable and will waste a lot of space.

There is also a problem when we need to sort negative numbers, because we fill the presum array according to the value of nums [index] when we calculate the number, so when nums [index] is negative, there will be an error when filling the presum array.

It is also unreasonable to define the array length by the maximum value at this time.

So we need to take another approach to define the length of the array.

Let's talk about the concept of offset.

For example, 90BEI 93pr 94jue 91J 92, we can use the values of max and min to set the array length 94-90 + 1 = 5. The offset is the min value, which is 90. Then our 90 corresponds to index 0.

See the picture below.

So we don't waste space when we populate the presum array, negative numbers? Of course, it is also possible to have negative numbers. Keep looking.

For example:-1pm, 3pm, 0pm, 2pm, 1e

The same can be done, oh, at this point we have done the counting and sorting, let's take a look at the code.

Class Solution {public int [] sortArray (int [] nums) {int len = nums.length; if (nums.length)

< 1) { return nums; } //求出最大最小值 int max = nums[0]; int min = nums[0]; for (int x : nums) { if (max < x) max = x; if (min >

X) min = x;} / / set the length of the presum array, and then find our prefixes and arrays. / / here we can treat the degree arrays and prefixes and arrays as an array int [] presum = new int [max-min+1]; for (int x: nums) {presum [x-min] + + } for (int I = 1; I

< presum.length; ++i) { presum[i] = presum[i-1]+presum[i]; } //临时数组 int[] temp = new int[len]; //遍历数组，开始排序,注意偏移量 for (int i = len-1; i >

= 0;-- I) {/ / look up the presum dictionary and put it in a temporary array, notice that the degree of offset int index = temp [nums [I]-min]-1; temp [index] = nums [I]; / / minus one presum [nums [I]-min]-- } / / copy return array System.arraycopy (temp,0,nums,0,len); return nums;}}

All right, we've got the sorting algorithm, so let's pick it up.

Analysis of time complexity of counting sorting

Our total operation is n+n+k+n, and the total operation is 3n + k, so the time complexity is O (Numbk).

Analysis of space complexity of counting sort

We use an auxiliary array with a space complexity of O (n).

Stability analysis of counting sort

Stability is reflected when we finally put it in the temporary array, when we put it in the right place in the temporary array and minus one, so that the same element in front of an element, in the temporary array, is still in front of it. So counting sorting is a stable sorting algorithm.

Although the counting sorting efficiency is good, it is not used much.

This is because it is not suitable for counting and sorting when the range of array elements is too large, which is not only a waste of time, but also greatly reduced in efficiency.

It doesn't apply when the element to be sorted is not an integer. Think about why.

At this point, the study on "how to achieve counting sorting" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.