目录
计数排序算法的思想
计数排序算法的实现
计数排序算法的思想
遍历数组，找出数组中的最大值 max 和 最小值 min
最大值 max 减去最小值 min 再加 1 得出数组元素的范围 range
利用 range 的大小 malloc 一个 count 数组用来计数
再对 count 数组进行初始化，全初始化为 0
在计数时要把原数组的每个元素各自减去最小值 min，这样做才能和 count 数组的下标一一对应，只要有相同的元素，就在对应的位置自增 1 ，而且以上的做法称之为相对映射
如果原数组的元素是多少就直接映射到 count 数组的对应位置的话，这样的映射叫做绝对映射，但是这样的映射可能会导致 count 数组多开很多不必要的空间，会造成空间浪费
当 count 数组计数完成后，再对 count 数组进行遍历，遍历 count 数组上的每个元素的个数，只要是非 0 的个数，那么就在原数组上面覆盖，注意，覆盖是需要先加 min
最后走完 count 数组时，原数组也就完成了排序
计数排序算法的实现
代码演示：
void CountSort(int* a, int size)
{/*找到数组中的最小值和最大值*/int min = a[0];int max = a[0];for (int i = 0; i < size; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}// 得出元素范围int range = max - min + 1;// 开辟 range 个空间用来计数int* countArr = (int*)malloc(sizeof(int) * range);// 判断是否开辟成功if (countArr == NULL){perror("malloc fail");return;}// 初始化为 0memset(countArr, 0, sizeof(int) * range);// 计数for (int i = 0; i < size; i++){countArr[a[i] - min]++;}// 排序int k = 0;for (int i = 0; i < range; i++){while (countArr[i]--){a[k++] = i + min;}}
}代码解析：
解析：countArr[a[i] - min]++
用 i 遍历原数组 a 中的每个值，再减去最小值 min ，得到的就是 [0,range] 区间的值
那么 [0,range] 区间也就是 countArr 数组下标对应的值，因为初始是 0 ，所以通过 countArr[a[i] - min] 找到后直接++即可
最后再排序，排 countArr 数组中非 0 元素的值，再一一覆盖到 a 数组，注意覆盖时要加上最小值 min，才是原数组中的值
代码验证：