基本思想
- 将元素的值，看成计数数组的下标，通过统计每个元素出现的次数完成排序任务；
- leetcode🧑💻 75. 颜色分类 分别数出 0、1、2 的个数，再依次赋值回去，就完成了排序，这种做法就是计数排序；
- 如果是对象数组（多关键字），这样做就会丢失稳定性；
图解
详细步骤
-
在无序数组
[2, 8, 5, 5, 9, 0, 9, 8]中，找出最大值 max 和最小值 min 后，确定需要开辟一个 max - min + 1 大小空间的 计数数组 和 累计数组； -
计数数组：保存每个元素出现的次数：
索引 0 1 2 3 4 5 6 7 8 9 计数数组 1 0 1 0 0 2 0 0 2 2 -
累计数组：保存前面元素累计出现的次数；
索引 0 1 2 3 4 5 6 7 8 9 计数数组 1 0 1 0 0 2 0 0 2 2 累计数组 1 1 1 2 2 3 4 4 5 8 -
遍历 原无序数组 根据累计数组推断有序元素的位置，计算位置后要及时更新累计数组（
累计次数 - 1就是元素有序的位置，因为元素位置是从 0 开始的）- [
2, 8, 5, 5, 9, 0, 9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 1 1 2-1 2 2 4 4 4 6 8 排序数组 2 -
[2,
8, 5, 5, 9, 0, 9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 1 1 1 2 2 4 4 4 6-1 8 排序数组 2 8 -
[2, 8,
5, 5, 9, 0, 9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 1 1 1 2 2 4-1 4 4 5 8 排序数组 2 5 8 -
[2, 8, 5,
5, 9, 0, 9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 1 1 1 2 2 3-1 4 4 5 8 排序数组 2 5 5 8 -
[2, 8, 5, 5,
9, 0, 9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 1 1 1 2 2 2 4 4 5 8-1 排序数组 2 5 5 8 9 -
[2, 8, 5, 5, 9,
0, 9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 1-1 1 1 2 2 2 4 4 5 7 排序数组 0 2 5 5 8 9 -
[2, 8, 5, 5, 9, 0,
9, 8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 0 1 1 2 2 2 4 4 5 7-1 排序数组 0 2 5 5 8 9 9 -
[2, 8, 5, 5, 9, 0, 9,
8]
索引 0 1 2 3 4 5 6 7 8 9 累计数组 0 1 1 2 2 2 4 4 5-1 7 排序数组 0 2 5 5 8 8 9 9 - [
适用场景
非负整数排序，最大值不是很大
范围小；重复键值多；可以与非负整数建立一一对应关系
复杂度
-
时间复杂度：
O(N+K)，这里 N 是数组的长度，K 是数组的最大值；如果 K 很大，会占用很多空间，在计算前缀和计数数组的时候，复杂度也会增加，此时不适合使用计数排序；- 统计数组中数值的范围：
O(N)； - 计数需要遍历数组：
O(N)； - 计算计数数组的前缀和：
O(K)； - 计算排序数组：
O(N)；
- 统计数组中数值的范围：
-
空间复杂度：
O(N+K)
实现代码
function countSort(nums) {
let max = Math.max(...nums);
let min = Math.min(...nums);
if (min < 0) {
throw new Error("该数组不适合使用计数排序");
}
// 第 1 步：对原始数组进行计数，这里将原始数组的值，作为了计数数组的下标
let count = new Array(max + 1).fill(0);
nums.forEach(it => count[it]++);
// 第 2 步：将 count 数组改造成前缀和数组，在原地进行变换即可，由前缀和数组就可以推出这个元素所在的位置
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 第 3 步：从后向前扫描，依次把看到的数写回原始数组，从后向前是为了保证稳定性
let numsCopy = [...nums]; // 为了写回去，需要对原始数组做一个拷贝
for (let i = nums.length - 1; i >= 0; i--) {
let position = count[numsCopy[i]] - 1; // 排序后的位置 = 计数和 - 1
nums[position] = numsCopy[i]; // 把看到的数覆盖回去
count[numsCopy[i]]--; // 前缀和减一，作为下一个看到的相同数存放位置的依据
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 堆排序
上一篇
评论
