介绍
计数排序(Counting Sort)是一种非比较型的排序算法,核心思想是通过统计元素出现的次数进行排序,利用数组的索引来确定元素的正确位置。
计数排序特别适合于已知范围不大的整数序列排序,其时间复杂度为 O(n+k),其中 n 是待排序数组的长度,k 是整数的范围。当 k 不是很大时,计数排序可以实现线性时间排序,这是基于比较的排序算法(快速排序、归并排序等)无法达到的。
算法步骤
- 找出待排序数组中的最大值和最小值,确定计数数组的大小
- 创建一个计数数组,统计每个元素出现的次数
- 对计数数组进行累加,得到每个元素在排序后数组中的位置
- 创建一个临时数组,从后向前扫描原数组,根据计数数组确定元素位置
- 将临时数组复制回原数组


核心特性
- 非比较排序:不通过比较元素大小进行排序
- 稳定排序:相等元素的相对位置在排序后不会改变
- 时间复杂度:O(n+k),其中 k 是数据范围
...