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

在这里插入图片描述

🎬 鸽芷咕：个人主页 🔥 个人专栏: 《数据结构&算法》

⛺️生活的理想，就是为了理想的生活!

📋 前言

哈喽各位铁汁们常用的八大排序我们都一起实现了，但是前面我们的实现过程大部分都是比较排序，不知道大家听说过计数排序这种非比较排序？它的性能再某些场景甚至能达到惊人的 O(N)

文章目录

• 📋 前言
• 一、计数排序的概念
  • 1.1 计数排序的缺陷
  • 1.2 计数排序的优化
• 二、计数排序的实现
• • 2.1 计数排序的代码
  • 2.2 计数排序的惊人性能
  • 实际性能
• 三、计数排序的特性总结

一、计数排序的概念

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

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

在这里插入图片描述

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

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

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

1.1 计数排序的缺陷

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

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

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]--;
		}
	}
	
}

2.2 计数排序的惊人性能

前面我们一直在说计数排序性能好多少多少现在我们就来和快排希尔排序堆排序归并排序这些经典高性能对手来比比：

🔥 注：本次我们采用10万个随机数来进行排序，为避免随机数重复所以都加 i 。

在这里插入图片描述

实际性能

在这里插入图片描述

这里可以看到计数排序完胜，排10万个数据只需要一毫秒

• 🔥 接下来我们看看1000万个数

在这里插入图片描述

这里依旧是完爆各种排序哦豁是不是，拳踢快排老师傅，脚打归并小年轻。

三、计数排序的特性总结

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

这里需要注意的是 计数排序只适合，在一个特定范围内数据特别多的情况或者范围集中都数据性能绝对是最棒的！

🔥 注：计数排序还有一个遗憾由于是使用下标统计来排序所以只能排序整形。