//2.7.7 计数排序(非比较排序)
//时间复杂度：O(N+range) =>标准的是 N+N+range;(表示：范围小就快，范围大就慢) 适用于范围集中的一组整形排序，并且只适用于整形，不像是上述的代码，就算不是整形也可以排，只要可以比较大小就可以
//空间复杂度：O(range)     思想很强，但是作用局限
#include<string.h>
void CountSort(int* arr, int n)
{
  int max = arr[0];
  int min = arr[0];
  int i;
  for (i = 0; i < n; i++)
  {
    //遍历比较，获取此数组中的最大值和最小值
    if (arr[i] > max)
    {
      max = arr[i];
    }
    if (arr[i] < min)
    {
      min = arr[i];
    }
  }
  //算此时的我们要创建的数组的范围的大小
  int range = max - min + 1;
  //算出了范围，我们就可以创建一个此范围的数组
  int* count = (int*)malloc(sizeof(int) * range);
  if (count == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  else
  {
    //此时就是根据计数排序的原理，统计我要排的元素出现的次数
    //代码如下：
    memset(count, 0, sizeof(int) * range);//这个就是一个函数，可以用来初始化一个数组，让数组中放上自己想要放的东西的（因为我此时想要将我的数组初始化为0，所以我要将我创建的整个数组range给memset为0）
    for (i = 0; i < n; i++)
    {
      count[arr[i] - min]++;//此时的这个（-min）就是为了映射出一个相对位置，因为只有相对位置才可以进行排序
      //这个就是按照原理：一个数出现一次就在这个数相应的下标处加1，所以这个就是对下边加加，对数组中的元素进行统计的关键代码
      //这步不明白就是画一个图 例：此时的arr数组中的元素是 ：    4 4 6 8 9 3 3 0 0 
                                   //我malloc出来的数组是：   0 0 0 0 0 0 0 0 0 0
                                  // 数组的下标是：           0 1 2 3 4 5 6 7 8
            //所以此时的count[arr[i]]++;的意思就是，arr[0]的位置处的数据是4，那么此时就对数组count[4]的位置处进行加加，arr[1]一样，arr[2]是6，我就对count[6]的位置进行加加
                                   //以此类推：最后得到       2 0 0 2 2 0 1 0 1 1   
      //然后按照count中的数据进行排序：得到                   0 0 3 3 4 4 6 8 9    这样我们就得到了有序的数组了
    }                 
    //统计完次数之后我们就可以将count数组给真正的拿过来排序了
    int j = 0;
    for (i = 0; i < range; i++)
    {
      while (count[i])
      {
        arr[j++] = i + min;
        count[i]--;
      }
    }
  }
  free(count);