Count sort

The content and code of this article are from 《 Comics algorithm 》
Bubble sort practiced before 、 Cocktail ordering 、 Quick sort 、 Heap sorting is based on element comparison and position element exchange , There are some special sorts that are not based on element comparisons , Such as Count sorting 、 Bucket sort 、 Radix sorting .
In terms of counting and sorting , This sort algorithm uses array subscripts to determine the correct position of elements .
Let's look at an example ：
Suppose there is 20 A random integer , Value range 0-10, Ask for the fastest speed to put this 20 An integer is sorted from small to large
Create a length of 11 Array of , Subscript 0-10, All elements are 0.

hypothesis 20 The numbers are as follows
9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9
Let's go through this 20 A numerical sequence of elements , Each integer is numbered according to its value , At the same time, the elements of the array subscript are added 1 operation .
For example, the first integer is 9, So the subscript is 9 The element of plus 1.

The second integer is 3, So the subscript is 3 The element of plus 1.

Continue to traverse and modify the array …
Finally, when the series is modified , The status of the array is as follows .

The value of each subscript position of the array represents the number of occurrences of the corresponding integer in the sequence . With this statistical result , Sorting is simple . Traversing arrays directly , Output the subscript values of array elements , What is the value of the element , Just output it a few times .
0 1 1 2 3 3 3 4 4 5 5 6 7 7 8 9 9 9 9 10
obviously , Now the output sequence is ordered .
This is the basic process of counting and sorting , It is suitable for integer sorting in a certain range . When the value range is not very large , Its performance is even faster than those with a time complexity of O(nlogn) Sort .

There are many pictures behind , It's not like calligraphy and painting . The most important is the sequential processing involved when there is duplicate data . Or look at the original book , It's a little bit easier to understand . Except for the problem of repeated data order , Another is not to follow the sequence 0 Handling of the initial situation .
The final java The implementation is as follows

	int[] countSort(int[] arr) {
    
		// 1. Get the maximum value of the array 、 minimum value , And calculate the travel value d
		int max = 0, min = 0;
		for (int i = 0; i < arr.length; i++) {
    
			if (arr[i] > max) {
    
				max = arr[i];
			}
			if (arr[i] < min) {
    
				min = arr[i];
			}
		}
		int d = max - min;

		// 2. Create a statistical array and count the number of corresponding elements 
		int[] countArr = new int[d + 1];
		for (int i = 0; i < arr.length; i++) {
    
			countArr[arr[i] - min]++;
		}
		// 3. Statistics array deformation , The element after is equal to the sum of the elements before 
		for (int i = 1; i < countArr.length; i++) {
    
			countArr[i] += countArr[i - 1];
		}
		// 4. Traverse the original array in reverse order , Find the right position from the statistical array , Output to the result array 
		int[] sortedArr = new int[arr.length];
		for (int i = arr.length - 1; i >= 0; i--) {
    
			sortedArr[countArr[arr[i] - min] - 1] = arr[i];
			countArr[arr[i] - min]--;
		}
		return sortedArr;
	}
	
	@Test
	public void fun1() {
    
		// int[] arr=new int[]{95,94,91,98,99,90,99,93,91,92};
		int[] arr = new int[] {
     49, 38, 65, 97, 76, 13, 27, 49 };
		int[] sortedArr = countSort(arr);
		System.out.println(Arrays.toString(sortedArr));
	}

Operate on the operand of the original array n, The calculation amount of the operation statistics sequence is m
Time complexity O(n+m)
Do not consider the result array and statistical array ,
Spatial complexity O(m)
Its time complexity is linear , However, its limitations are also very serious
1. When the difference between the maximum value and the minimum value of a sequence is too large , It's not suitable to sort by count
Give, for example 20 A random integer , The scope is 0 To 1 Billion between , Need to create 1 An array of 100 million elements , Not only a serious waste of space , And the time complexity will also increase .
2. When a sequence element is not an integer , It's not suitable to sort by counting
If all the elements in the sequence are decimals , Such as 25.213, or 0.00 000 001 Numbers like this , The corresponding statistics array cannot be created . This obviously makes it impossible to sort by count .