一、概念
计数排序是非比较排序，是对哈希直接定址法的变形应用。
二、思想
利用数组统计相同数据出现的次数，例如整型数据m出现n次，就在数组m位置记录数据为n。
最后从头遍历数组打印数据即可。
通俗来讲就是，数组下标即为数据，下标所指位置的值即为数据出现的次数。
对于较大的数据，可以利用映射关系。用所有数据减去最小的数据，映射到计数数组的0-range位置上。
三、优缺点
优点：1.数据较为集中时，效率极高
缺点：1.只适合较为集中的数据，不适合分散的数据
2.只适合整型数据，不适合浮点型、字符型数据
四、代码实现（C语言）
void CountSort(int* a, int n) { int min = a[0]; int max = a[0]; //找到数据中的最大值与最小值 for (int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } //数据范围 int range = max - min + 1; //计数数组，初始值为0 int* count = (int*)calloc(range, sizeof(int)); //统计相同数据出现的次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //输出数据 for (int i = 0; i < range; i++) { while (count[i])//计数数组该位置存在数据 { printf("%d ", i + min); count[i]--; } } }
