【数据结构】深入浅出讲解计数排序【图文详解，搞懂计数排序这一篇就够了】

//计数排序——非比较排序
void CountSort(DataType* a,int n) {
    //遍历一遍数组 => 得出min和max值 => 确定数的范围
  int min = a[0]; int max = a[0];
  for (int i = 0; i < n; i++) {
    if (a[i] < min) {
      min = a[i];
    }
    if (max < a[i]) {
      max = a[i];
    }
    //确定范围 => 确定需要开辟的数组的大小
    int range = max - min + 1;    //[min,max]左闭右闭，所以+1
    //开辟大小为range的空间，避免了 绝对映射 那样的空间的浪费
    DataType* count = (DataType*)malloc(sizeof(DataType)*range);
    if (count == NULL) {
      perror("malloc fail");
      exit(-1);
    }
    //内存重置 将count数组中的值都初始化为0，重置数组大小为sizeof(DataType) * range
    //要进行初始化，否则待会遍历计数数组中，那些并没有统计到有这个数出现的次数的位置，将以该内存原来的值（随机数）进行填入
    memset(count, 0, sizeof(DataType) * range);
                                            //数组中的值
    //遍历数组 => 统计数组中各数据出现的次数 => 通过 a[i]-min 找到对应下标在 count 中的对应下标 => 对该下标的值对应++进行计数
    for (i = 0; i < n; i++) {
      count[a[i] - min]++;
    }
    //排序
    //遍历计数数组，根据统计到的每个数的次数count[i]，就拷贝回去原数组count[i]次，覆盖原数组
    //遍历数组
    int j = 0;     //放外面，遍历a[] j记录的数值 不会别被清
    for (i = 0; i < range; i++) {
    while (count[i]--){             //count[i]=0的进不了循环
      a[j++] = i + min;             //i+min:对应回原数组中的值
    }
    }
    }
}