🕒 1. 计数排序

💡 算法思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

void CountSort(int* a, int n)
{assert(a);  // 创建计数数组，数组大小为原数组中最大值-最小值+1int max = a[0], min = a[0];int i = 0;for (i = 0; i < n; i++){if (a[i] > max)  {max = a[i];}if (a[i] < min)  {min = a[i];}}int range = max - min + 1;// 统计次数int* count = (int*)malloc(sizeof(int) * range);assert(count);// 初始化计数数组为0memset(count, 0, sizeof(int) * range);// 统计每个值出现的次数for (i = 0; i < n; i++){count[a[i] - min]++;}// 根据计数数组进行排序int j = 0;for (i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;  // 将排序后的值放回原数组}}free(count);count = NULL;  
}

注意：计数排序在排负数时，可将负数的类型转化成 unsigned int。

只适合整数，不适合浮点数、字符串等。 数组中元素有正有负的情况时不适用计数排序。

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(N+range)
3. 空间复杂度：O(range)
4. 稳定性：稳定

---

❗ 转载请注明出处
作者：HinsCoder
博客链接：🔎 作者博客主页