This is the 8th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Count sorting

A non-comparative sort. Counting sort is very fast for a range of integers, generally faster than other sorting algorithms. But the limitation of counting sort is great, which is limited to sorting integers, and the distribution of elements to be sorted is continuous and the span is small.

If all the elements in an array are integers, and they’re all within 0 minus k. For each element in the array, if you know how many items in the array are less than or equal to that element, you can tell exactly where that element is in the sorted array.

For example, given an array [2,5,3,0,2,3,0,3] in the range of 0 to 5, create a count array of size (5-0+1 = 6), if the value in the original array corresponds to the index of the count array, then the index corresponds to the value of the count array plus 1.

The problem

The length of the count array is determined by the maximum value of the array, but if you need to sort the students’ scores, such as: [95,93, 93, 94, 94,92,93,95,90], if we follow the above method, we need an array of size 100, but we can see that the minimum value is 90, that is to say, there is no data stored in the first 0~89 positions, resulting in a waste of resources.

If we know the maximum and minimum values of the array, then the size of the count array is (Max – min + 1). For example, if the maximum value of the array is 99 and the minimum value is 90 above, then define the size of the count array to be (95-90 + 1 = 6). And the indexes correspond to the values of the original array 90 and 95. Let’s express the range 0, 90 as an offset, so that the minimum value 90 is the offset.

Code implementation

public class CountSort { public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3}; Public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90}; Private static int[] sort(int[] array) {if (array. Length < 2) return array; Int Max = array[0]; for (int i : array) { if (i > max) { max = i; Int [] countArray = new int[Max + 1]; for (int i = 0; i < countArray.length; i++) { countArray[i] = 0; } for (int temp: array) {countArray[temp]++; } int o_index = 0; Int n_index = 0; While (o_index < array. Length) {if (o_index < array. Length) {if (o_index < array. = 0) { array[o_index] = n_index; CountArray [n_index]--; // Count the array value to -1 o_index++; } else { n_index++; }} return array;}} return array; } private static int[] sort2(int[] array) {if (array. Length < 2) return array; Int min = array[0], Max = array[0]; for (int i : array) { if (i > max) { max = i; } if (i < min) { min = i; } // Bias = 0; // Bias = 0; // Bias = 0; Int [] countArray = new int[max-min + 1]; for (int i = 0; i < countArray.length; i++) { countArray[i] = 0; } for (int temp : array) { countArray[temp + bias]++; } // Fill the count array with int o_index = 0; Int n_index = 0; While (o_index < array.length) {if (countArray[n_index]! = 0) { array[o_index] = n_index - bias; countArray[n_index]--; o_index++; } else { n_index++; } } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); System. The out. Println (" = = = = = = = = = = = = = = = = = optimization = = = = = = = = = = = = = = = = = = = = "); print(ARRAY2); System.out.println("============================================"); print(sort2(ARRAY2)); }}Copy the code

Time complexity

It is clear that during the sorting process we are traversing the original array at least three times, and counting the array once, so its complexity is of the o (n+m). Therefore, counting sort is more block than any sort, which is a kind of sacrifice of space for time, because the sorting process requires a counting array to store the number of occurrences of the element group.

Algorithm stability

The number of each element in the original array is recorded in the newly created counting array. If the original array has the same elements, the original sorting of the elements cannot be guaranteed when output. It is an unstable sorting algorithm.