计数排序 #
1. 计数排序算法思想 #
计数排序(Counting Sort)基本思想:
使用一个额外的数组
counts
,其中第i
个元素counts[i]
是待排序数组arr
中值等于i
的元素个数。然后根据数组counts
来将arr
中的元素排到正确的位置。
2. 计数排序算法步骤 #
- 找出待排序数组中最大值元素和最小值元素。
- 统计数组中每个值为
i
的元素出现的次数,存入数组的第i
项。 - 对所有的计数累加(从
counts
中的第一个元素开始,每一项和前一项累加)。 - 反向填充目标数组:将每个元素
i
放在新数组的第counts[i]
项,每放一个元素就要将counts[i] -= 1
。
3. 计数排序动画演示 #
4. 计数排序算法分析 #
- 当输入元素是
n
个0 ~ k
之间的整数时,计数排序的时间复杂度为 $O(n + k)$。 - 由于用于计数的数组
counts
的长度取决于待排序数组中数据的范围(等于待排序数组最大值减去最小值再加1
)。所以计数排序对于数据范围很大的数组,需要大量的时间和内存。 - 计数排序一般用于排序整数,不适用于按字母顺序排序人名。
- 计数排序是 稳定排序算法。
5. 计数排序代码实现 #
|
|