核心思想
计数排序不是基于比较的排序算法，算法的核心有3点：
- 统计原数组中每个元素出现的次数。
- 以原数组中的元素为下标，元素出现的次数为值，存入另一个计数数组中。
- 从下标0开始遍历计数数组，反向填充到目标数组。
时间复杂度和稳定性
当数组的元素是 n 个 0 到 m 之间的整数时，时间复杂度是O(n+m)，空间复杂度也是O(n+m)，其排序速度快于任何比较排序算法。
计数排序是一个很稳定的排序算法。
适用范围
由于计数数组的长度取决于原数组中最小元素和最大元素，所以当最小元素和最大元素之间的差值比较大时，计数数组将占用很大的存储空间。
因此计数排序算法仅适用于 元素值比较小、元素数量有限而且比较集中 的数组。
Java 实现
注意点：
当数组中的 元素 出现 负值 时，需要考虑负值元素如何正确地表示为计数数组的下标：
- 根据数组中的最小值计算出一个偏移量（即负的最小值），计数数组的下标=数组中的元素+偏移量。
- 偏移量还有个好处是可以使计数数组从下标0开始就存放有效数据。
import java.util.Arrays;
/**
* 计数排序
*
* @author Alisallon
* Created on 2021/6/5 9:38 上午.
*/
public class CountingSort {
public static void main(String[] args) {
int[] nums = {2, 3, 6, 8, 4, 2, 1, 8, 9, 4, 8, 0, 2, 3, 4, 9, 6, 5, 7, -3, -1, -7, -4, -9, -10, -5, -6};
System.out.println(Arrays.toString(sort(nums)));
}
/**
* 计数排序实现
*
* @param nums 原数组
* @return 排序后的数组
*/
private static int[] sort(int[] nums) {
// 找出原数组nums中最小值和最大值,用来确定计数数组bucket的长度和bucket索引的偏移量
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int a : nums) {
min = Math.min(a, min);
max = Math.max(a, max);
}
// 为了防止原数组中的元素a为负值的情况,所以需要计算偏移量
// 即使元素a不可能出现负数,该偏移量也能确保计数数组bucket从下标0开始存放有效数据,尽量使存储空间更紧凑
int offset = -min;
// 统计数组nums中每个值为a的元素出现的次数，存入计数数组bucket的第a项
int[] bucket = new int[max + offset + 1];
for (int a : nums) {
// 把计数数组bucket的第a项的计数累加
// 为了防止原数组中的元素a为负值的情况(负数不能作为bucket的下标),这时需要a减去偏移量变成不小于0的数
// 即使元素a不可能出现负数,该偏移量也能确保计数数组bucket从下标0开始就存放有效数据
bucket[a + offset]++;
}
// 从位置0开始循环计数数组bucket，把原值反向填充到原数组nums
int index = 0;
for (int i = 0; i < bucket.length; i++) {
// 根据偏移量计算出原值
int a = i - offset;
// 把原值反向填充到原数组nums
Arrays.fill(nums, index, index + bucket[i], a);
index += bucket[i];
}
return nums;
}
}
