前言
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。
简介
所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于一个排序算法的优劣，我们需要从它的时间复杂度、空间复杂度和稳定性三个方面来考虑。什么叫稳定性呢？即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的。
本篇文章将为大家介绍一种比较特殊的排序算法，它就是计数排序。（用升序进行讲解）
基本思想
在此之前，我们所讲的排序算法的本质都是通过比较两个数的大小来进行排序，我们称之为比较排序，而计数排序则是一种非比较排序的算法。它的基本思想借助了一个数学原理——抽屉原理。
抽屉原理：
抽屉原理又称鸽巢原理、重叠原理、狄利克雷抽屉原理。举一个简单的例子让大家了解什么是抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。
抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。
抽屉原理是组合数学中一个重要的原理。计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中
接下来我们通过一个例子来具体了解一下何为计数排序：
对于数组 {6，1，2，9，4，2，4，1，4} ，我们可以统计出每个数字出现的次数，如上图所示，接着在按顺序将每一个元素取出即可，从0位置开始，0没有出现，往后看，1位置上的元素是2，说明1出现了两次，依次写入原数组，一遍循环过后得到 {1，1，2，2，4，4，4，6，9} 。这就是计数排序。我们再来看另外一种情况：
当数组中元素过大时，我们发现会有许多的空间没有用到，存在浪费。因此我们不能按数值来开辟空间，而是要按范围来开辟空间，那么如何按范围来开辟空间呢？很简单，我们先遍历一遍数组，找到最大值和最小值，它们的差便是我们需要的开辟空间的大小，也就是它们之间的范围。
虽然我们按范围开空间能够节省一部分空间，但是当最大值与最小值差距过大时用计数排序是很浪费空间的，因此计数排序只有在数据范围集中时，效率才会很高，适用范围及场景有限。
代码实现
计数排序的代码实现比较简单，代码如下：
void Count_Sort(vector<int>& a)
{
int n = a.size();
//找到最大值与最小值
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//通过最大值与最小值计算出数据范围，并开辟出相等大小的数组用来计数
int range = max - min + 1;
vector<int> count(range, 0);
//统计每个元素出现的次数
for (int i = 0; i < n; i++)
{
//注意下标的映射
count[a[i] - min]++;
}
//按顺序取count中的数据存放在原数组中
int index = 0;
for (int i = 0; i < range; i++)
{
while(count[i]--)
{
a[index++] = i + min;
}
}
}总结
1.时空复杂度
计数排序一共用了三个循环，找最大值与最小值与统计元素出现此时的时间复杂度为O（N），取count中的元素存放在原数组的时间复杂度为O（range），因此计数排序的总时间复杂度为O（N + range）。由于需要通过创建一个计数数组来完成我们的排序，因此空间复杂度为O（range）。
计数排序：
时间复杂度：O（N + range）
空间复杂度：O（range）
2.稳定性
在排序算法中，我们不光要关注算法的时空复杂度，还在看看算法的稳定性，什么是稳定性呢？
稳定性是假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
由于计数排序是非交换排序，在整个排序过程中不涉及到交换操作，因此我们认为计数排序是稳定的。
计数排序 ： 稳定
尾声
若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！