Concept:


Counting sort is not a comparison sorting algorithm, which was proposed by Harold H. Seward in 1954. It reduces the time complexity to O(N) by counting, using array subindexes to locate missing elements in the correct position


Case study:


Assume that there are 10 random numbers in the array, ranging from 0 to 10. Sort the 20 certificates from smallest to largest as soon as possible

The value range is limited because the integers can only be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. So, based on this finite range, we can create an array of length 11, with indices from 0 to 10, with all elements starting at 0

Suppose 10 random integer values are as follows

9，3，5，4，9，1，2，7，8，1

First count

Second count

Third count

Fourth count

Fifth count

Sixth count

Seventh count

Eighth count

Ninth count

Tenth count

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 result, sorting is much easier, directly convenient array, output array element subscript value, the value of the element, output several times

1，1，2，3，4，5，7，8，9，9

Obviously, the output sequence is now in order.

This is the basic process of counting sort, and it applies to integer sorts within a range. In the case of small value range, its performance is even faster than those of time complexity O(nlogn).





public class test {

    public static void main(String[] args) {
        int[] array = new int[] {4.4.6.5.3.2.8.1.7.10};
        int[] sortedArray = countSort(array);
        System.out.println(Arrays.toString(sortedArray));
    }

    public static int[] countSort(int[] array){
        //1. Get the maximum value of the array
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max){ max = array[i]; }}//2. Determine the length of the array according to the maximum value of the array
        int[] countArray = new int[max+1];
        for(int i=0; i<array.length; i++){
            countArray[array[i]]++;
        }
        // Iterate over the statistics array to print the result
        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; }}Copy the code

[1, 2, 3, 4, 4, 5, 6, 7, 8, 10]

The code begins with a step to find the maximum integer value Max. The statistics array countArray is created with Max +1 length to ensure that the last subscript of the array is Max.


Advantages and disadvantages of counting sort


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

For example, given 20 random integers ranging from 0 to 100 million, if counting sort is used, it is necessary to create an array with a length of 100 million, which not only wastes space, but also increases the time complexity

  1. When the sequence elements are not integers, counting sort is also not appropriate

If the elements of the array are all decimals, such as 25.213, or 0.00 000 001, then the corresponding statistics array cannot be created, which obviously does not allow counting sort.

To compensate for these limitations, another linear time sorting algorithm is called bucket sorting



“When there is a high wind, life does not give up”