Count sorting

Scope of application

Counting sort can be said to be a special case of bucket sort. When sorting n data, if the value range of n is very small, such as 0-K, we can divide k buckets, because the data in the bucket is consistent, so it can reduce the time of bucket sort. For example, we can use this method for the provincial ranking of gaokao scores, which is only a three-digit range.

example

A group of students’ scores are {2,5,3,0,2,3,0,3}. At this time, we can use an array A[8] to store this group of data, and then divide the data into 0-5 according to the bucket sorting standard, establish an initial array C[6] to represent the bucket, and then iterate A[8] to get A new C[6].

It can be seen from the figure that there are 3 people with a score of 3 and 4 people with a score less than 3, so an R can be obtained [8]


//a is array A, n is the size of array A. Public void countingSort(int[] a, int n) {if (n <= 1) {
		return; Int Max = a[0];for (int i = 1; i < n; i++) {
		if(max < a[i]) { max = a[i]; Int [] c = new int[Max + 1];for(int i = 0; i < n; ++i) { c[a[i]]++; } // add upfor(int i = 1; i < max; i++) { c[i] = c[i - 1] + c[i]; Int [] r = new int[n]; // Count the key step of sortfor(int i = n - 1; i > 0; i--) { int index = c[a[i]] - 1; r[index] = a[i]; c[a[i]]--; }}Copy the code

To summarize, count sort can only be used in scenarios with a small range of values, and can only be sorted for non-negative integers