[数据结构与算法]排序算法：计数排序（java实现）

计数排序是一种非比较排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

int[] a = {5,3,5,8,2,10}

对数组a进行计数排序
数组中最大的数是10，所有我们需要建立一个大小为11的计数数组
计数数组中每一位的大小就是该数组下标在a数组中出现的次数。

int[] count = {0,0,1,1,0,2,0,0,1,0,1}

最后只需要遍历一遍统计数组，更新一下原数组a就完成了计数排序

import java.util.Arrays;

public class CountSort {
	public static void main(String[] args) {
		int[] arr = {108, 109, 106, 101, 107, 102, 103, 102, 104, 106, 101, 110};
	    countSort(arr);
	    System.out.println(Arrays.toString(arr));
	}
	public static void countSort(int[] arr) {
		int max = arr[0];
		int min = arr[0];
		for(int i=0; i<arr.length; i++) {
			if(arr[i]<min) {
				min = arr[i];
			}
			if(arr[i]>max) {
				max = arr[i];
			}
		}
		int[] count = new int[max-min+1]; 
		//当遇到所有数都特别大的时候不应该开一个大小为最大值大小的数组；
		//优化成为最大值-最小值+1大小的数组
		for(int i=0; i<arr.length; i++) {
			count[arr[i]-min]++;
		}
		int k = 0;
		//System.out.println(Arrays.toString(count));
		for(int i=0; i<count.length; i++) {
			while(count[i]>0) {
				arr[k++] = i + min;
				count[i] --;
			}
		}	
	}
}