排序-计数排序 计数排序
基本知识
稳定性：稳定
存储方式：外排序
空间复杂度：O(k)
最坏时间复杂度：O(n+k)
最好时间复杂度：O(n+k)
平均时间复杂度：O(n+k)
基本思想
- 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中
- 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
实现步骤
- 找出待排序数组中最大和最小的元素
- 定义一个新的计数数组，大小为max-min+1(依然可能有多余的数据)
- 遍历带排序数组，每遍历一个数据，就在计数数组的相应位置加一
- 遍历完成之后，用计数数组，反向填充目标数组