计数排序
基本思想：
计数排序与其他排序不同，它没有数据的比较；
基本思想是：计数+排序
计数：
先开一个大小为range（大小后面有讲）的数组tmp，遍历一遍待排序的数据，遍历到某个数据（如5）时，就在tmp数组中下标为5的位置上＋1，遍历完待排数据，就计数完成；
排序：
计数完，只需要根据tmp数组，数据就是tmp组的下标，有多少个就是对应下标上的数据，例如
tmp[5]=3；即数据为5的有3个
图解：
优化：
为了避免空间的浪费，range的大小为待排数据打最大值减去最小值加1；
range=max-min+1；
例如：如果数据最小值为100，最大值为199，如果用上面的思想，就需要开辟空间为200个int数组，但是前面100个数组位置没有存储数据，就造成了空间浪费，这种情况就需要开100个int空间的数组，数组下标0的位置计数100的出现的次数，当排序时只需要相应的加上100（min）即可；
实现代码：
void CountSort(int* a,int n ) { //找出最大最小值 int min = a[0], max = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //确定要开辟空间的大小 int range = max - min+1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } //将开辟数组初始化为0 memset(count, 0, sizeof(int) * range); //计数 for (int i = 0; i < n; i++) { count[a[i]-min]++; } //排序 int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } }
性能分析：
时间复杂度：O(N+range)
空间复杂度：O(range)
稳定性：不稳定
