计数排序是一种稳定的线性时间排序算法。需要使用一个额外的数组空间。
特征
计数排序要求待排序数组在一个可收敛的整数范围内，因为需要使用额外的数组空间进行存储，并且需要对数据进行遍历计数，所以计数排序不适合范围特别大的数组。
举个例子通俗理解，例如有10个年龄不同的人需要找到小明排在第几位，我们只需要统计出有几个人比小明小或者同龄就行了，比如有8个人，那小明就排在第9位。这里如果有两个小朋友同龄，需要进行特殊的处理，即一个小朋友这里占据了一位之后，统计的比另外一个小朋友小的值应该减一（排序的稳定性），同理可以得到其他每个人的位置，也就排好了序。
算法步骤
找出待排序数组中的最大和最小的元素
这一步主要是为了确定这个额外的数据空间的大小，消费尽可能小的空间 统计数组中每个值为 i 的元素出现的次数，存入临时数组的第i 项对所有的计数累加（即临时数组的每一项和前一项相加）
这个统计之后的值就表示小于或者等于该位置上的值的个数 反向填充目标数组
这一步反向的作用主要是为了保证排序的稳定性
算法实现
public int[] countSort(int[] a
) {
int[] c
= new int[a
.length
];
int min
= a
[0];
int max
= a
[0];
for (int i
= 1; i
< a
.length
; i
++) {
if (min
> a
[i
]) {
min
= a
[i
];
}
if (max
< a
[i
]) {
max
= a
[i
];
}
}
int k
= max
- min
+ 1;
int[] b
= new int[k
];
for (int i
= 0; i
< a
.length
; i
++) {
b
[a
[i
] - min
]++;
}
for (int i
= 1; i
< b
.length
; i
++) {
b
[i
] = b
[i
] + b
[i
- 1];
}
for (int i
= a
.length
- 1; i
>= 0; --i
) {
c
[--b
[a
[i
] - min
]] = a
[i
];
}
return c
;
}
图形化分析
复杂度分析
该算法总共有三个遍历，所以时间复杂度为 O(2n+k)
因为开辟了两个临时数组，所以空间复杂度为 O(n+k)
Leetcode相关题型
75. 颜色分类
参考
wiki-计数排序
