排序篇(五)----非比较排序

排序篇(五)----非比较排序

基本思想：

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

统计每个元素出现的次数，然后根据元素的大小顺序将它们放入正确的位置。

计数排序是一种小众的排序,它适合于数据密集的场景,按最大数的数值来开空间,比如一组数据中,最大的数据是1000,那么便会开一千个大小的空间,这种属于绝对映射,在极端的场景下,极易造成空间上的浪费.假设现在有10个数:5,99,88,1000,8888,452,635,82,777,555,只有10个数但是最大的数是8888因此要开8888大小的空间,剩余的空间全部都浪费了,

因此绝大多数情况下,都会使用相对映射.

具体的步骤如下：

1. 找出待排序数组中的最大值和最小值，并创建一个计数数组，长度为最大值和最小值之差加1。
2. 遍历待排序数组，统计每个元素出现的次数，并将次数存储在计数数组的相应位置上。
3. 对计数数组进行累加操作，得到每个元素在排序后数组中的最终位置。

1. 创建一个与待排序数组长度相同的临时数组，用于存储排序后的结果。
2. 从后向前遍历待排序数组，根据计数数组中每个元素的值，将元素放入临时数组的相应位置上。
3. 将临时数组中的元素复制回待排序数组，完成排序。

//计数排序
void CountSort(int* a, int n)
{
  int min = a[0];
  int max = a[0];
  for (int i = 0; i < n; i++)
  {
    if (a[i] < min)
    {
      min = a[i];
    }
    if (a[i] > max)
    {
      max = a[i];
    }
  }
  int range = max - min + 1;
  int* count = (int*)malloc(sizeof(int) * range);
  if (count == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  memset(count, 0, sizeof(int) * range);
  for (int i = 0; i < n; i++)
  {
    count[a[i] - min]++;
  }
  int j = 0;
  for (int i = 0; i < range; i++)
  {
    while (count[i]--)
    {
      a[j++] = i + min;
    }
  }
}

代码解析:

1. 找到数组中的最小值和最大值，以确定计数数组的大小。
2. 然后，根据最小值和最大值计算计数数组的大小，并分配内存空间。
3. 接下来，将计数数组的所有元素初始化为0。
4. 然后，遍历原数组，统计每个元素出现的次数，将统计结果保存在计数数组中

1. 接着，使用两个循环，将计数数组中的元素按照次数依次放回原数组中。
2. 最后，释放计数数组的内存空间。

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
   

1. 时间复杂度：O(MAX(N,范围))
   
2. 空间复杂度：O(范围)
   
3. 稳定性：稳定
   

集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度：O(MAX(N,范围))

3. 空间复杂度：O(范围)

4. 稳定性：稳定

计数排序的时间复杂度为O(n+k)，其中n为待排序数组的长度，k为计数数组的长度。计数排序是一种稳定的排序算法，适用于元素范围较小的情况。但是计数排序的缺点是当元素范围较大时，需要创建一个较大的计数数组，可能会占用较多的内存空间。