计数排序学习

计数排序（Counting Sort）

​ 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

例子

数组： 2 3 4 8 7 6 4 3 2 2 1
找到最大最小值：8 1
设置一个计数数组： 对应1 2 3 4 5 6 7 8的空数组
循环数组：
count： 1 3 2 2 0 1 1 1
结果： 1 2 2 2 3 3 4 4 6 7 8
结束
复制代码

算法复杂度瓬

空间复杂度： O(n+k)

时间复杂度：