首页 > 试题广场 >

关于计数排序的叙述中正确的是（）

[单选题]

关于计数排序的叙述中正确的是（）

计数排序是一种基于比较的排序算法

查看答案及解析

推荐

freewheel370

答案： A

计数排序的时间复杂度主要取决于被排序的数组的大小即O(n)

但是空间复杂度为主要取决于被排序数组的最大值与最小值的差值

计数排序需要借助额外的空间，所以不是原地排序

计数排序不是基于比较的排序算法

编辑于 2017-05-22 14:50:47 回复(0)

天尊墨宇

计数排序是一种基于统计的排序算法

基于链式队列计数排序的时间复杂度为O(n+k)

基于链式队列计数排序的空间复杂度为 O(k)（设 k 为数据范围（最大值 - 最小值））

原地排序是指不申请多余空间排序，松一点的说法是可以用很小的固定的辅助空间。但计数排序需要一个标记数组（或者 hash map）辅助统计，这个数组大小与数据范围大小相关，因此计数排序不是原地的。

所以，综上，本题应该选择A项

编辑于 2020-06-16 19:54:36 回复(0)

刘明宇

计数排序是基于桶排序思想的排序，时间复杂度为O(n)，空间复杂度取决于“桶”的数量。

发表于 2017-02-24 23:58:10 回复(0)

提交观点

问题信息

复杂度排序

上传者：牛100

难度：

3条回答 8收藏 2239浏览

扫一扫，把题目装进口袋