计数排序
计数排序是一种非比较排序算法，它通过统计每个元素出现的次数，然后根据统计结果重建有序数组。它适用于整数排序，特别是当元素范围较小时效率很高。
算法原理
计数排序的基本思想是：首先找到数组中的最大值和最小值，确定元素的范围。然后创建一个计数数组，统计每个元素出现的次数。最后根据计数数组重建有序数组。
算法步骤
- 找到数组中的最大值和最小值
- 创建计数数组，大小为最大值减最小值加1
- 遍历原数组，统计每个元素出现的次数
- 根据计数数组重建有序数组
时间复杂度
- 最坏情况：O(n + k)，其中 n 是元素个数，k 是元素的范围
- 平均情况：O(n + k)
- 最好情况：O(n + k)
空间复杂度
O(n + k) - 计数排序需要额外的空间来存储计数数组和输出数组。
稳定性
计数排序是稳定的排序算法，相等元素的相对顺序不会改变。
适用场景
- 整数排序，特别是元素范围较小的情况
- 需要线性时间复杂度的排序
- 对稳定性有要求的排序
优缺点
- 优点：时间复杂度为 O(n + k)，在元素范围较小时效率很高；稳定排序
- 缺点：需要额外的空间；只适用于整数排序；当元素范围很大时效率低