目录

CountSort计数排序

整体思想

图解分析

代码实现

时间复杂度&优缺分析

CountSort计数排序

计数排序是一种非比较排序，不需要像前面的排序一样去比较。

计数排序的特性总结：
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)

4. 稳定性：稳定

整体思想

  • 思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
  • 1. 统计相同元素出现次数
  • 2. 根据统计的结果将序列回收到原来的序列中

Count数组

  • Count数组中的元素需要全部初始化为0（calloc就可以满足这个要求）
  • Count元素是 计算a数组元素个数出现的次数
  • Count数组的下标是a数组元素的范围
  • 绝对隐射：范围0~max（a中最大的元素）
  • 相对隐射：范围0~max-min<<<<<<<<<min~max
  • range = max-min+1（映射0~max-min，个数max-min+1)

整个流程

  • 遍历一遍：找到最大值 / 最小值
  • 计算出Count数组下标范围并且开辟动态空间
  • rangge=max-min+1
  • 计数Count[a[i]-min]++ (i++)
  • 相对隐射回去

注意tips

  • i和j能不能公用❓
  • a数组的元素可以是负数吗？
  • 除了整型其他类型可以吗？
  • 后置–&前置–
  • calloc>>>>>>calloc – C++ Reference (cplusplus.com)
  • Count的下标表示a的元素的范围
  • Count的元素表示a的元素出现的个数（计数）

图解分析

代码实现

void CountSort(int* a, int n){//找最大值/最小值/创建的tmp的范围在这个之间int max = a[0];int min = a[0];for (int i = 0; i  max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;//注意int* count = (int*)calloc(range, sizeof(int));//计数for (int j = 0; j < n; j++){count[a[j]-min]++;}//相对隐射回去int i = 0;for (int k = 0; k < range; k++){while (count[k]--){a[i++] = k + min;}}}

时间复杂度&优缺分析

时间复杂度：O（N）

  • 时间复杂度：O（a（N）+coun（N））（count的N是a的数据范围）
  • 计数排序不需要比较元素大小
  • 优势：效率极高
  • 局限性：不适合范围很大，计数排序只适用于整型，不同数据类型的，实践意义不高。（现实实践，更多的是结构体排序，不能适用计数排序）

感谢大家的阅读，若有错误和不足，欢迎指正。下篇总结各个排序。