计数排序
基本思想：不通过比较，计下每个元素的出现次数，统计小于这个元素的个数N，将其放在N位。例如{7，6，2，4，2，3}这个序列，有5个小于7的元素，那么7在排序后应该放在数组的第5位。
读完这段话，读者可能会有疑问，不通过比较怎么统计小于这个元素的个数？请继续向下看
注意！！！计数排序对将要排序的数组是有限制的
1.只能是整形数组。
2.数组元素必须都大于0。
3.计数排序是一种拿空间换时间的排序算法。
具体步骤如下
1.一个待排序的数组array
1.选出数组的最大值k，创建一个k+1长度的数组countArray，将所有元素初始化为0（Java数组默认是0，节省操作），countArray的数组下标代表array数组中的元素值，而countArray中的元素值代表的是array中每一个元素的出现次数。
疑问：为什么要创建k+1的长度？因为array中最大值为k，那么array的值一定是0-k之间，而且countArray的下标代表array中的数，0-k之间有k+1个数。
2.遍历array数组，统计每个元素的出现次数。例如array[0]是7，那么countArray[7]++，因为countArray的下标代表array中的数。统计完如下图。
3.对countArray进行循环，对每一个元素countArray[i] = countArray[i] + countArray[i-1]，目的是统计每一个元素前面有多少个小于它的元素。例如下图countArray[3]的值是4，那么就代表在array中有4-1个元素小于3。
4.复制array数组存到temp中，循环temp，将temp中i位置的的元素放到array中的--countArray[temp[i]]位置。也就是array[--countArray[temp[i]]] = temp[i]。
例如i等于1时，temp[i]值时6，countArray[6]的值是6，也就代表6这个元素前面有5个元素小于小于它，那么6应该放在array数组的第6个位置也就是array[5]。
完整代码如下
/**
* 计数排序
* Created by ShouJingGuo on 2018/3/24.
*/
public class CountSort{
public static void countSort(int[] array){
int max = getMax(array); //获取数组的最大值，数组所有值都在0 - max之间
int[] countArray = new int[max + 1]; //创建一个max+1大小的数组用于表示从0 - max所有数字的重复次数
int[] resultArray = new int[array.length];
System.arraycopy(array, 0, resultArray, 0, array.length); //用于存储排好序的数组
for(int i = 0; i < array.length; i++){ //循环array数组
countArray[array[i]]++; //因为countArray的下标代表array中的数字，而值代表array中元素的出现次数，所以countArray[array[i]]++
}
for(int i = 1; i < countArray.length; i++){
countArray[i] = countArray[i] + countArray[i - 1]; //将countArray中的每一个元素变成与前一个元素相加的和
}
for(int i = 0; i < resultArray.length ; i++){
array[--countArray[resultArray[i]]] = resultArray[i]; //从array的最后一位开始依次放入resultArray中，放入的位置是 --countArray[array[i]]
}
}
private static int getMax(int[] array){
int max = array[0];
for(int i = 0; i < array.length; i++){
if(array[i] < 0){
throw new RuntimeException("数组中有数小于0");
}
if(max < array[i]){
max = array[i];
}
}
return max;
}
public static void main(String[] args) {
int arr[] = {10,5,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
CountSort.countSort(arr);
System.out.println(Arrays.toString(arr));
}
}
