————— the next day —————










— — — — — —



















Suppose 20 random integers have the following values:


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


How do you sort these unordered random integers?


Very simply, let’s iterate over an unordered, random sequence of numbers, each integer indexed by its value, and increment the element of the array index by one.


For example, if the first integer is 9, then the element with subscript 9 is incremented by 1:



The second integer is 3, then the element with subscript 3 is incremented by 1:



Continue iterating through the number column and modifying the array……


Finally, when the array is iterated, the array looks like this:



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. Print the subscript value of the element in the array. The value of the element is several times:



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


Obviously, the output sequence is already in order.








public static int[] countSort(int[] array) { //1. Int Max = array[0];for(int i=1; i<array.length; i++){        if(array[i] > max){ max = array[i]; Int [] countArray = new int[Max +1]; //3. Iterate over the number column and populate the statistics arrayfor(int i=0; i<array.length; i++){ countArray[array[i]]++; } int index = 0; int[] sortedArray = new int[array.length];for(int i=0; i<countArray.length; i++){        for(int j=0; j<countArray[i]; j++){ sortedArray[index++] = i; }}returnsortedArray; } public static void main (String [] args) {int [] array = new int [],4,6,5,3,2,8,1,7,5,6,0,10 {4}; int[] sortedArray = countSort(array); System.out.println(Arrays.toString(sortedArray)); }Copy the code


This code adds a step at the beginning to find the maximum integer value Max of the sequence. The statistics array countArray is Max +1 to ensure that the last index of the array is Max.








95，94，91，98，99，90，99，93，91，92








How to solve this problem?


Quite simply, instead of (the maximum value of the input array +1), we use (the difference between the maximum and minimum value of the array +1) as the length of the statistical array.


At the same time, the minimum value of the array is used as an offset for the count of the array.


In the case of the number column, the length of the statistics array is 99-90+1 = 10, and the offset is equal to the minimum value of the column, 90.


For the first integer 95, the corresponding statistical array subscript is 95-90 = 5, as shown in the figure below:









What does that mean? Let’s look at the following example:



Given a list of students’ grades, ask them to be sorted from lowest to highest, and if they are the same, follow the order inherent in the table.


So, when we populate the statistics array, we only know that there are two partners who are tied for 95 points, but we don’t know which one is red and which is green:








The following explanation will be a little brain burn, please hold firmly and sit. Using the student score table as an example, we can transform the previous statistics array into something like this:




How does this get deformed? The statistical array starts with the second element, and each element is added to the sum of the preceding elements.


Why do I add? You may be confused when you meet someone for the first time.


The purpose of this addition is to have the value of the element stored in the statistics array equal to the final sorting position of the corresponding integer. For example, if the value of the element with subscript 9 is 5, which represents the original integer 9, the final order will be the fifth digit.


Next, we create the output array sortedArray with the same length as the input array. The input sequence is then traversed from back to front:


First, we iterate over the little green in the last row of the score table:


Little green is 95 points, we found the countArray element with index 5, and the value is 4, which represents the rank of little green in the 4th place.


At the same time, we subtracted the value of countArray’s element with index 5 by 1, from 4 to 3, which means that the next time we meet a score of 95, the final ranking will be 3.




Step 2, we iterate over the small white in the penultimate row of the score table:


Xiaobai is 94 points, we found the countArray element with the index of 4, the value is 2, which represents xiaobai’s ranking position in the second place.


At the same time, we subtracted 1 from countArray’s index 4 from 2 to 1, which means that the next time we encounter a score of 94 (which we don’t), we will be ranked first.




Step 3, we iterate over the red in the third row from the bottom of the score table:


Xiao Hong is 95 points, we found the countArray element with index 5, the value is 3 (originally 4, minus 1 becomes 3), which represents xiao Hong’s ranking position in the third place.


At the same time, we reduced countArray’s index of 5 by 1 from 3 to 2, which means that the next time you get a 95 score (which you don’t), you’ll end up in 2nd place.




In this way, the same 95 points of the small red and small green can be clearly out of order, and therefore, the optimized version of the counting sort is stable.


The same goes for the following traversal process, which is not described in detail here.





public static int[] countSort(int[] array) { //1. D int Max = array[0]; int min = array[0];for(int i=1; i<array.length; i++) {        if(array[i] > max) {            max = array[i];        }        if(array[i] < min) { min = array[i]; } } int d = max - min; Int [] countArray = new int[d+1];for(int i=0; i<array.length; i++) { countArray[array[i]-min]++; Int sum = 0; int sum = 0;for(int i=0; i<countArray.length; i++) { sum += countArray[i]; countArray[i] = sum; Int [] sortedArray = new int[array.length];for(int i=array.length-1; i>=0; i--) { sortedArray[countArray[array[i]-min]-1]=array[i]; countArray[array[i]-min]--; }returnsortedArray; } public static void main (String [] args) {int [] array = new int [],94,91,98,99,90,99,93,91,92 {95}; int[] sortedArray = countSort(array); System.out.println(Arrays.toString(sortedArray)); }Copy the code












1. When the difference between the maximum and minimum values of a sequence is too large, counting sort is not applicable.


For example, given 20 random integers in the range 0 to 100 million, if counting sort is used, you need to create an array of 100 million. Not only is it a huge waste of space, but time complexity also increases.


2. Counting sort is not applicable when the array elements are not integers.


If the elements of the array are all decimals, such as 25.213 or 0.00000001, the corresponding statistical array cannot be created. So obviously you can’t do counting sort.






— — the END — — –



If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content