计数排序（Counting Sort）是一种非比较排序算法，特别适用于一定范围内的整数排序。它的核心思想是统计每个值的出现次数，然后根据这些计数将每个元素放到其正确的位置上。计数排序的时间复杂度为O(n+k)，其中n是数组长度，k是待排序数据的最大值与最小值的差加一，也就是数据的范围。计数排序的局限性在于它只能应用于整数排序，并且要求数据范围不是太大，否则会占用过多的内存空间。
计数排序的基本步骤：
- 找出待排序数组中的最大值和最小值，以确定计数数组的大小。
- 初始化计数数组：创建一个长度为
最大值 - 最小值 + 1的数组，所有元素初始化为0。这个数组用来记录每个值出现的次数。 - 统计每个元素的出现次数：遍历原数组，对于每个元素，将其对应的计数数组中的计数加一。
- 累加计数数组：修改计数数组，使得每个位置的值变为它之前所有位置的值之和。这样，计数数组中的每个索引i将表示原数组中小于或等于i的元素总数。
- 根据计数数组构建输出数组：遍历原数组，对于每个元素，将其放入输出数组的计数数组中对应索引的位置，同时将该位置的计数减一，以确保相同的元素在输出数组中的顺序不变（这一步保证了排序的稳定性）。
- 复制输出数组到原数组（如果需要的话），完成排序。
特点总结：
- 时间复杂度：O(n+k)，在数据范围k不是很大时，此算法非常高效。
- 空间复杂度：O(k)，需要额外的计数数组，空间消耗与数据范围成正比。
- 稳定性：计数排序是稳定的排序算法，即相等的元素的相对顺序不会改变。
- 适用场景：适用于数据范围不大的整数排序，尤其当输入数据是均匀分布时效率更高。
计数排序由于其对整数的限制和对空间的需求，在处理特定类型的排序问题时非常有效，但并不适用于所有类型的排序需求。在数据范围过大或者数据类型不是整数时，应考虑其他排序算法。
计数排序的实现示例图：
计数排序的实现Java代码如下：
/* 计数排序 */
// 简单实现，无法用于排序对象
void countingSortNaive(int[] nums) {
// 1. 统计数组最大元素 m
int m = 0;
for (int num : nums) {
m = Math.max(m, num);
}
// 2. 统计各数字的出现次数
// counter[num] 代表 num 的出现次数
int[] counter = new int[m + 1];
for (int num : nums) {
counter[num]++;
}
// 3. 遍历 counter ，将各元素填入原数组 nums
int i = 0;
for (int num = 0; num < m + 1; num++) {
for (int j = 0; j < counter[num]; j++, i++) {
nums[i] = num;
}
}
}
