一、计数排序
🔑 核心思想 🔑
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
计数排序核心步骤：
1️⃣ 统计相同元素出现次数
2️⃣ 根据统计的结果将序列回收到原来的序列中
❗ 动图演示：❕
🧿 实现代码 ：
void CountSort(int* a, int n) { //遍厉一遍找出最小值和最大值 int min = a[0], max = a[0]; int i = 0; for (i = 1; i < n; i++) { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } //求出这个区间 int range = max - min + 1; //calloc空间，并初始化为0 int* count = (int*)calloc(range, sizeof(int)); //统计 for (i = 0; i < n; i++) { //相对位置 count[a[i] - min]++; } //根据count数组排序 i = 0; int j = 0; for (j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } free(count); }
❗ 计数排序的特性总结：❕
1️⃣ 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限
2️⃣ 时间复杂度：O(MAX(N,范围))
3️⃣ 空间复杂度：O(范围)
4️⃣ 稳定性：稳定
5️⃣ 只适合整数排序，浮点数/字符串不能排
一、基数排序
🔑 核心思想 🔑
基数排序又称桶排序，它分别按数据的个、十、百、千、万 … 排序，当然也可以先万、千、…
❗ 动图演示：❕
❓ 这里就不实现了，为什么 ❔
因为这种排序实际在校招中和现实中已经很少使用了，各位码友有兴趣的也可以自己了解下
