计数排序（Counting Sort）
一、概念
- 用空间换时间，在某些时候，平均时间复杂度可以比
O(nlogn)更低。 - 计数排序的思想是，统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引。
- 例如有如下一组数：
image
- 统计每个数出现的次数：
image
- 接着就可以顺序输出获得排序后的结果：
image
- 代码实现如下：
image
- 这个版本的时间复杂度是
O(n)。 - 这个版本存在以下问题：
- 无法对负整数进行排序。
- 极其浪费内存空间。
- 不稳定的排序。
二、改进思路
- 有如下一组数，最小值为
3，最大值为8：
image
- 我们只需要一个数组，能存放
3-8之间的数即可，则实际需要的数组空间为：max - min + 1。
image
- 将每个元素出现的次数累加上其前面的所有次数，得到的就是元素在有序序列中的位置信息。
image
- 元素
8获得的累计次数为8，前一个元素7出现的次数是7，那么可以知道元素8在数组中出现的次数为1，排序后的索引为7。
image
- 总结：
image
三、实际操作
- 首先，拥有
蓝色数组array，即可获得绿色counts数组，为了排序我们再新建一个紫色数组。
image
- 从后往前遍历数组，首先是元素
5，元素5在紫色数组中的索引应该是4-1 = 3，所以将5插入数组索引为3的位置，并且将元素5的次数减1。
image
- 接着遍历元素
4,其在紫色数组中的索引为1。
image
- 按照以上逻辑，依次遍历蓝色数组剩下的元素：
image
image
image
image
- 我们发现，从后往前遍历数组，可以保证不改变相同元素在新数组中的前后顺序。
四、代码实现
protected void sort() {
// 找出最值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[I];
}
if (array[i] < min) {
min = array[I];
}
}
// 开辟内存空间，存储次数
int[] counts = new int[max - min + 1];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i] - min]++;
}
// 累加次数
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
int[] newArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
newArray[--counts[array[i] - min]] = array[I];
}
// 将有序数组赋值到array
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[I];
}
}
复制代码
- 最好，最坏，平均时间复杂度为
O(n + k) - 空间复杂度为
O(n + k)。 -
k是整数的取值范围。 - 属于
稳定排序。
