计数排序是一种稳定的线性时间排序算法，原理是使用一个额外的数组，其中第i个元素是待排序数组中值等于i的元素的个数。
计数排序的局限性：
- 计数排序只适用于 整数 排序；
- 计数排序只适用于一定范围，如果待排序整数最大值和最小值差较大则不适用（引发大量存储空间浪费）。
复杂度分析
代码中遍历过原始待排序数列和临时的统计数列，假设原始待排序数列规模是N，临时统计数列规模是M，则时间复杂度是O(N+M)，空间复杂度O(M)。
Java 代码实现
import java.util.Arrays;
public class CountSort {
public static void sort(int[] data) {
if (data == null || data.length == 0) {
return;
}
// 获取数列最大值
int max = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
}
}
// 创建长度为“最大值+1”的统计数组
int[] count = new int[max + 1];
// 遍历待排序元素，填充统计数组
for (int i = 0; i < data.length; i++) {
count[data[i]]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
for (int j = 0; j < count[i]; j++) {
data[index++] = i;
}
}
}
}
public static void main(String[] args) {
int[] data = {5, 8, 2, 9, 1, 0, 3, 4, 7, 4, 6, 2, 5};
sort(data);
System.out.println(Arrays.toString(data));
}
}
运行结果
[0, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9]
思考：以上代码存在什么问题？如果待排序整数都是大整数，如针对121, 123, 101, 119, 110, 149, 136排序，一共需要排序的整数有7个，但是按照以上代码逻辑会创建一个容纳150个整数的额外数组，大部分存储空间实际是浪费了。
优化方法：不再以最大值 + 1作为数组长度，以最大值 - 最小值 + 1作为数组长度，同时数组最小位存储偏移量。以121, 123, 101, 119, 110, 149, 136为例，数组长度为149 - 101 + 1 = 49，偏移量为最小值101。优化后代码实现如下：
import java.util.Arrays;
public class CountSort {
public static void sort(int[] data) {
if (data == null || data.length == 0) {
return;
}
// 获取数列最大值
int max = data[0];
int min = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
} else if (data[i] < min) {
min = data[i];
}
}
// 创建长度为“最大值+1”的统计数组
int[] count = new int[max - min + 1];
// 遍历待排序元素，填充统计数组
for (int i = 0; i < data.length; i++) {
count[data[i] - min]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
for (int j = 0; j < count[i]; j++) {
data[index++] = i + min;
}
}
}
}
public static void main(String[] args) {
int[] data = {121, 123, 101, 119, 110, 123, 149, 136};
sort(data);
System.out.println(Arrays.toString(data));
}
}
运行结果
[101, 110, 119, 121, 123, 123, 136, 149]
