Count sort (diagram)

One 、 What is counting sort

Counting sort is applicable to those with Define the scope Array of , For example, given an array , And know that all the value ranges are [n,m]. You can use one at this time m-n+1 An array of lengths , The array to be sorted can be scattered on this array , The value of the array is the number of current values , After another traversal expansion , The resulting array is ordered .

Two 、 Implementation steps

（1） Get the maximum value of the elements in the array 、 minimum value ; To determine the length of the array of counts ;

（2） Ergodic primitive group , Count the number of occurrences of each element with the count array ;

（3） Traversal count array , Re store the original array , The output original array is the sorted array ;

3、 ... and 、 Code implementation  

public class CountingSort {

	public static void main(String[] args) {
		int[] arr = { -2, 3, 5, 1, 7, 3, 11, 4 };
		sort(arr);
	}

	public static void sort(int[] arr) {
		int Max = arr[0];
		int Min = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > Max) {
				Max = arr[i];
			}
			if (arr[i] < Min) {
				Min = arr[i];
			}
		}

		int len = Max - Min + 1;
		int[] count = new int[len];
		for (int i = 0; i < arr.length; i++) {
			count[(arr[i] - Min)]++;
		}
		int h = 0;
		for (int m = 0; m < count.length; m++) {
			for (int j = 0; j < count[m]; j++) {
				arr[h] = m + Min;
				h++;
			}
		}

		for (int c = 0; c < arr.length; c++) {
			System.out.print(arr[c]+"  ");
		}
	}

}

Running results ：