计数排序🌟🌟🌟🌟
我们之前学习过了快速排序和归并排序等排序算法，特别是在平时的应用中，这两种排序算法的使用都很广泛。
但是我们注意到这两种排序算法的时间复杂度都是 ${O(NlogN)}$ ，我们想有没有一种排序算法的时间复杂度能够达到 ${O(N)}$ 呢？
其实是有的，就是我们要学习的计数排序。
计数排序思想介绍
计数排序在排序的过程中，会统计相同元素出现的次数，并将其记录到统计数组中，从而实现有序。
举个例子，假设待排序数组的元素大小范围都是 [0, 10]，那么我们可以创建一个大小为 11 ，数组元素初始值都为 0 的统计数组，
在遍历排序数组中的过程中，如果元素等于 8，那么统计数组下标为 8 的元素则 + 1。
如下图所示：
完成统计之后，统计数组的结果如下图所示
计数排序算法的思想和代码都是比较简单的，我们重在理解，因为其思想我们在解决其他算法题的时候，也经常会用到。
代码实现
public class Solution {
public int[] sort (int[] nums) {
int[] cnt = new int[11];
for (int i = 0; i < nums.length; i++) {
cnt[nums[i]]++;
}
int j = 0;
for (int i = 0; i < cnt.length; i++) {
while (cnt[i]-- > 0) {
nums[j++] = i;
}
}
return nums;
}
}
时间复杂度
计数排序的最大特点就是他只需要遍历排序数组一次进行计数即可，所以时间复杂度是 ${O(N)}$
空间复杂度
计数排序需要一个统计数组来辅助计数，统计数组的范围又与排序数组的元素的大小范围有关，如果大小范围不能确定，或者范围很大，那么这一点也是我们在选择排序算法需要慎重考虑的一点。
稳定性
因为计数排序的使用场景只适用于整数数字的排序，因此也不会对稳定性有什么要求了。
写在最后
总的来说，计数排序是一种优点和缺点都很明显的排序算法，优点是时间复杂度是 ${O(N)}$，缺点是适应场景的局限以及空间复杂度的不确定性。
我们重在学习通过统计数组进行计数的思想，后面我们在讲具体的算法题的时候会经常用到。
好了，今天就讲到这里，希望大家在仅剩的假期里好好充电啊！