计数排序（Counting sort）是一种线性时间的排序算法，核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序的工作原理是使用一个额外的数组，其中第个元素是待排序数组中值等于的元素的个数，然后根据数组来将中的元素排到正确的位置。
工作过程：
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为
i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从
C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素
i放在新数组的第C[i]项，每放一个元素就将C[i]减去1
时间复杂度
计数排序的时间复杂度为)，其中代表待排序数据的值域大小
代码实现