鸽巢原理：揭秘计数排序的奇妙思想-阿里云开发者社区

鸽巢原理：揭秘计数排序的奇妙思想

2024-01-18 31

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 鸽巢原理：揭秘计数排序的奇妙思想

一、计数排序的概念

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。以前我们选择排序的时候一般都是使用大数比较小数来进行比较

而计数排序是统计每个数字出现的个数来进行排序，哈哈哈是不是突然就发现了新大陆这个思想太奇妙了，非常值得我们学习一下他的思想

其计数排序的思想就是把每个当某个数字出现时就在其下标下面 ++ 如果没有这个数字的话就默认为零。

诶是不是非常简单要对一组数据进行排序的话我们顶多遍历三遍就可以了

第一遍找到最大值进行开空间
第二遍进行统计个数
第三遍根据统计好的个数来直接写入

1.1 计数排序的缺陷

但是这样的话就有一个非常大的缺陷就是我们的数据多大就要开多少空间这样空间浪费的实在的是太大了：

空间开辟太大了，数值多大就得开辟多少空间
既然是使用下标进行统计排序那么肯定只能排序整数

1.2 计数排序的优化

所以我们先找出需要排序的最大值和最小值，把他们的差值标记住用于开辟空间：

当我们开空间时就只开他们差值个空间就可以了

当需要统计个数的时候就把原本的数减去 最小值 来存放下标

而恢复排序的时候只需要将下标加上 最小值 就可以了

这样一来性能就得到了极大的优化

二、计数排序的实现

2.1 计数排序的代码

//计数排序
void CountSort(int* a, int n)
{
  int max = 0, min = 0;
  for (int 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* tmp = (int*)calloc(range,sizeof(int));
  if (tmp == NULL)
  {
    perror("calloc file");
    exit(-1);
  }
  //统计数据出现的个数
  for (int i = 0; i < n; i++)
  {
    tmp[a[i]-min]++;
  }
  //排序
  int index = 0;
  for (int i = 0; i < range; i++)
  {
    while (tmp[i])
    {
      a[index++] = i+min;
      tmp[i]--;
    }
  }
}