首页 > 试题广场 >

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

[不定项选择题]

基于链式队列，关于计数排序的叙述中正确的是（）

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

```
计数排序的时间复杂度为O(n+k)
```
```
计数排序的空间复杂度为 O(k)
```
```
计数算法是原地排序算法
```

查看答案及解析

sgbs

哪位大神可以详细的解释下？？？

发表于 2017-06-21 09:21:00 回复(1)

江湖再见！

计数排序：取到待排序的长度为n的序列中的最大最小数（不妨假设都是非负数，若有负数，简单操作一下就可得到都是正数），这花费n的时间；

假设最大数为k，开辟一个数组大小为k的数组a[k]，若序列中有一个树为i，则把a[i]赋予标记，花费k的时间；

最后按顺序输出有标记的下标就可完成排序。

发表于 2019-03-14 20:03:42 回复(0)

EugeneZheng

A. 计数排序是一种基于统计的排序算法，错误。

B. 需要遍历所有数据，时间复杂度 O(N) ，但最后输出排序后的序列更合理，设 k 为数据范围（最大值 - 最小值），则遍历标记数组需要 O(k) ，总共 O(N+k) 。

C. 当数据范围是 k 时，空间复杂度 O(k) 。~~但是 BC 两个选项以及题干没有关联关系，没有描述 k 的上下文。~~

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

——07/24/17 修改了以上BD项的解答

——09/09/17 题目选项改了，现在的BC项是对的。

编辑于 2017-09-09 17:34:13 回复(2)

养生型爆肝

一句话，计数就是单趟桶排....

发表于 2018-09-30 11:53:31 回复(0)

奥卡姆的剃刀生锈了

空间复杂度不应该是O(N+K)吗

发表于 2021-09-03 16:30:58 回复(0)

隔壁小王_sh

计数排序也叫桶式排序假设N个整数，范围是1-M，则其时间复杂度为O(M+N) 如果M = θ（N）则桶式排序为O（N）
但是由于该算法是牺牲空间来成全时间的所以希望有大神能解释C

发表于 2017-07-25 15:17:51 回复(3)

JAVA开发区

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

发表于 2022-11-10 09:42:48 回复(0)

六娃lw

我觉得B选项有问题，如果不用额外的hashmap直接定位到链表节点，那么时间复杂度不应该是O(nk^2)吗

发表于 2020-11-18 09:01:15 回复(0)

John~117

对于A选项，计数排序应该是一种基于统计的排序算法

编辑于 2020-03-12 18:40:38 回复(0)

TTT爱吃糖

发表于 2018-10-11 17:51:14 回复(0)

ITliudehua

发表于 2017-06-08 17:44:49 回复(0)

提交观点

问题信息

C++工程师 2017 京东排序 Java工程师

上传者：齐小乐

难度：

11条回答 418收藏 3193浏览

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

问题信息

热门推荐

相关试题

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

问题信息

热门推荐

相关试题

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